Class Note for MATH 300 at UMass(1)
Class Note for MATH 300 at UMass(1)
Popular in Course
Popular in Department
This 5 page Class Notes was uploaded by an elite notetaker on Friday February 6, 2015. The Class Notes belongs to a course at University of Massachusetts taught by a professor in Fall. Since its upload, it has received 12 views.
Reviews for Class Note for MATH 300 at UMass(1)
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 02/06/15
Math 300 Fall 2008 Note 6 Zhigang Han Umass at Amherst 1 Functions and Bijections 11 Functions Def 1 Let X and Y be sets A function 1 from X to Y denoted by f X a Y is a rule that assigns to each element x E X a unique element y E Y We write y x and call it the value of the function f at x The set X is called the domain of f and Y is called the codomain of f The set of values of f is called the image of f and is denoted by imf That is imf y E Yly x for some x E X Note that imf is a subset of the codomain Y Rmk ln calculus we often write 1 R a R such that x xxi 2 Note that by our de nition 1 is not a function since the domain for f is not equal to R However if we denote X x 2 2 then f X a R is a function Note also that it s OK to keep the codomain as R although 11110 yly Z 0 Def 2 Two functions f and g are equal if they have the same domain the same codomain and x gx for all x in the domain Eg 1 Let f R a R be a function such that x x2 and g ZH Z be another function such that gx x2 1 and g are not equal since they have different domain and different codomain Eg 2 Let f and G be functions from N to N de ned by n lcm2n and gn 3 7 71 712 Then 1 and g are equal since they have the same domain and the same codomain and n gn for all n E N Check this Def 3 Let f X a Y and g Y a Z are two functions such that the codomain of f is equal to the domain of 9 De ne the composite of f and g7 denoted by g o f as the function with domain X and codomain Z such that 9 O f 90 Eg 3 Let X be the set of nonnegative numbers Let f X a R be de ned by x Let g R a R be de ned by gz 2x 1 Are the composite f o g and g o f de ned Theorem Associativity Let f X a Y7 g Y a Z and h Z a W be three functions Then hogof homo Xew Rmk Because of the associativity7 it makes sense to write the composite of three functions as h o g o f Def 4 The identity function on X7 denoted by 1X7 is de ned to be the function 1X X a X such that 1Xm z for all zEX Prop 1 Let f XHYbeafunctionThenf01X f and 1yof f Def 5 Let f X HY and g Y a X be two functions If fog 1X and 901 1Y7 then 9 is called an inverse of f and f is called an inverse of 9 We write 9 f 1 and f g l Prop 2 Uniqueness of the inverse If a function f X a Y has an inverse7 then the inverse is unique Proof Assume f has two inverses g and h By the de nition of inverse7 g and h both have the domain Y and codomain X Also from the de nition of inverse we have 9 o f 1X and f o h 1y We also have the other two equalities but we don t need them for our proof F romgof1Xwegetgofoh1Xohhandfrom foh1ywe get 9 o f o h g 0 1y 9 Hence 9 h This proves the uniqueness Rink Since the inverse is unique we can write 9 f 1 and also 1 g l We also have f 1 of 1X and fo f l 1y Rink about interchanging z and y There s no need to interchange z and y especially when the variables x and y represent have their speci c meanings Eg 4 Let f R a R and g R a R be two functions de ned by x 3 1 and gy y 7 Show that g is the inverse function of f 12 The Inversion Theorem Def 6 A function f X a Y is called injective or onetoone if HM Hm x1 m2 That means distinct elements in the domain must have distinct images An injective function is called an injection Def 7 A function f X a Y is called surjective or onto if 1mm Y That means the image is the whole of the codomain An surjective function is called an surjection Def 8 A function f X a Y is called bijective or onetoone cor respondence if it is both injective and surjective A bijective function is called a bijection Rink 1 A function is injective if for each y E Y there is at most one element x E X such that y 2 A function is surjective if for each y E Y there is at least one element x E X such that y 3 A function is bijective if 7 for each y 6 Y7 there is precisely one element x E X such that y Inversion Theorem A function has an inverse if and only if it is bijective Eg 5 Does the function f R a R de ned by x 5 7 z have an inverse Prop 3 Let f X a Y and g Y a Z be two functions 1 If f and g are both injections7 then 9 o f is an injection 2 If f and g are both surjections7 then 9 o f is an surjection 3 If f and g are both loijections7 then 9 o f is an bijection 13 Cardinality Def 9 We say a set X has the same cardinality as a set Y7 and we write le lYl7 if there exists a bijection from X to Y We write le 7 lYl ifX does not have the same cardinality as Y Rmk le lYl implies lYl le since if there exists a bijection 1 from X to Y7 then there exists a bijection from Y to X7 namely the inverse of 1 From now on7 it makes sense to say that X and Y have the same cardinality Def 10 We say the cardinality of a set Y is greater than or equal to the cardinality of a set X7 and we write lYl 2 le or le lYl7 if there exists an injection from X to Y Def 11 We say the cardinality of a set Y is strictly greater than the cardinality ofa set X7 and we write lYl gt le or le lt lYl7 if lYl 2 le and le 7 Rmk To show lYl gt le one needs to show there exists an injection from X to Y which is often easy and by a direct construction7 but there exists no bijection from X to Y which is usually harder and by contradiction Eg 6 De ne a relation R on the set A of all sets such that ARB if and only if A has the same cardinality as B Show that R is an equivalence relation Eg 7 Show that ifA Q B7 then lAl ls it true that ifA C B7 then 1A1 lt 1317 Prop 4 HA and B are nite sets7 that is7 sets with nitely many elements7 then lAl B if and only if A and B have the same number of elements Rmk That s why we often write X Y for le Prop 5 l2 Prop 6 Q Theorem R gt Rmk This theorem was proved by Georg Cantor in 1874 The proof is called Cantor7s diagonal argument Def 12 A set is said to be countable if it s nite or it has the same cardinality as N is uncountable otherwise Rmk So N Z and Q are countable7 while R is uncountable Eg 8 Show that A mlO x g 1 and B yl3 y g 5 have the same cardinality Eg 9 Prove that any two closed intervals have the same cardinality Eg 10 Prove that A 0 lt z lt 1 and R have the same cardinality Eg 11 Prove that any two open intervals have the same cardinality A Challenge Problem Show that A mlO lt z lt 1 and B le y g 1 have the same cardinality
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'