Functions CSE235 Functions Introduction One To One Onto Inverses and Compositions Slides by Christopher M Bourke Instructor Berthe Y Choueiry Important Functions Fall 2007 Computer Science Engineering 235 Introduction to Discrete Mathematics Section 2 3 of Rosen 1 47 Introduction Functions CSE235 Introduction Definitions You ve already encountered functions throughout your education One To One Onto Inverses and Compositions Important Functions f x y x y f x x f x sin x Here however we will study functions on discrete domains and ranges Moreover we generalize functions to mappings Thus there may not always be a nice way of writing functions like above 2 47 Definition Function Functions CSE235 Introduction Definitions One To One Onto Inverses and Compositions Important Functions Definition A function f from a set A to a set B is an assignment of exactly one element of B to each element of A We write f a b if b is the unique element of B assigned by the function f to the element a A If f is a function from A to B we write f A B This can be read as f maps A to B Note the subtlety Each and every element in A has a single mapping Each element in B may be mapped to by several elements in A or not at all 3 47 Definitions Terminology Functions CSE235 Introduction Definitions One To One Onto Definition Let f A B and let f a b Then we use the following terminology Inverses and Compositions A is the domain of f denoted dom f Important Functions B is the codomain of f b is the image of a a is the preimage antecedent of b The range of f is the set of all images of elements of A denoted rng f 4 47 Definitions Visualization Functions CSE235 Introduction Definitions f One To One Onto Inverses and Compositions a b A B Important Functions A function f A B 5 47 Definitions Visualization Functions CSE235 Introduction Definitions f One To One Onto Inverses and Compositions a b A B Important Functions Domain A function f A B 5 47 Definitions Visualization Functions CSE235 Introduction Definitions f One To One Onto Inverses and Compositions a b A B Domain Codomain Important Functions A function f A B 5 47 Definitions Visualization Functions CSE235 Introduction Preimage Definitions f One To One Onto Inverses and Compositions a b A B Domain Codomain Important Functions A function f A B 5 47 Definitions Visualization Functions CSE235 Introduction Image f a b Preimage Definitions f One To One Onto Inverses and Compositions a b A B Domain Codomain Important Functions A function f A B 5 47 Definitions Visualization Functions CSE235 Introduction Preimage Range Image f a b Definitions f One To One Onto Inverses and Compositions a b A B Domain Codomain Important Functions A function f A B 5 47 Definition I More Definitions Functions CSE235 Introduction Definitions Definition Let f1 and f2 be functions from a set A to R Then f1 f2 and f1 f2 are also functions from A to R defined by One To One Onto f1 f2 x f1 x f2 x f1 f2 x f1 x f2 x Inverses and Compositions Important Functions Example Let f1 x x4 2x2 1 and f2 x 2 x2 then f1 f2 x f1 f2 x 6 47 x4 2x2 1 2 x2 x4 x2 3 x4 2x2 1 2 x2 x6 3x2 2 Definition II More Definitions Functions CSE235 Introduction Definitions One To One Onto Inverses and Compositions Important Functions Definition Let f A B and let S A The image of S is the subset of B that consists of all the images of the elements of S We denote the image of S by f S so that f S f s s S Note that here an image is a set rather than an element 7 47 Definition III More Definitions Functions CSE235 Introduction Definitions One To One Onto Inverses and Compositions Important Functions Example Let A a1 a2 a3 a4 a5 B b1 b2 b3 b4 f a1 b2 a2 b3 a3 b3 a4 b1 a5 b4 S a1 a3 Draw a diagram for f The image of S is f S b2 b3 8 47 Definition IV More Definitions Functions CSE235 Introduction Definitions One To One Onto Inverses and Compositions Important Functions 9 47 Definition A function f whose domain and codomain are subsets of the set of real numbers is called strictly increasing if f x f y whenever x y and x and y are in the domain of f A function f is called strictly decreasing if f x f y whenever x y and x and y are in the domain of f Injections Surjections Bijections I Definitions Functions CSE235 Introduction One To One Onto Definition A function f is said to be one to one or injective if f x f y x y Examples Exercises Inverses and Compositions for all x and y in the domain of f A function is an injection if it is one to one Important Functions Intuitively an injection simply means that each element in B has at most one preimage antecedent It may be useful to think of the contrapositive of this definition x 6 y f x 6 f y 10 47 Injections Surjections Bijections II Definitions Functions CSE235 Introduction One To One Onto Examples Exercises Inverses and Compositions Important Functions 11 47 Definition A function f A B is called onto or surjective if for every element b B there is an element a A with f a b A function is called a surjection if it is onto Again intuitively a surjection means that every element in the codomain is mapped This implies that the range is the same as the codomain Injections Surjections Bijections III Definitions Functions CSE235 Introduction One To One Onto Examples Exercises Inverses and Compositions Important Functions Definition A function f is a one to one correspondence or a bijection if it is both one to one and onto One to one correspondences are important because they endow a function with an inverse They also allow us to have a concept of cardinality for infinite sets Let s take a look at a few general examples to get the feel for these definitions 12 47 Function Examples A Non function Functions CSE235 A Introduction B One To One Onto a1 b1 Inverses and Compositions a2 b2 Important Functions a3 b3 a4 b4 Examples Exercises This is not a function Both a1 and a2 map to more than one element in B 13 47 Function Examples A Function Neither One To One Nor Onto Functions CSE235 A Introduction One To One Onto Examples Exercises Inverses and Compositions Important Functions B a1 b1 a2 b2 a3 b3 a4 b4 This function not one to one since a1 and a3 both map to b1 It is not onto either since b4 is not mapped to by any element in A 14 47 Function Examples One To One Not Onto Functions CSE235 A Introduction One To One Onto Examples Exercises …
View Full Document
Unlocking...