Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 191Today’s topics:• Proof that a given function is injective or surjective. • Composite functions • Properties of the composite functions. • Inverse functions. • Proofs with functions.211)(xxxfLet A =R{1} and f : A A be defined by the formula:Prove that f is injective and surjective. 1) injective: Let x and y be arbitrary elements of A such that f (x) = f (y ), (1). We must show that (1) implies x = y yxyxxyyxyxxyxyxyyxyyxx111)1)((1)1)((1111by assumptionsince (x 1)0 and (y 1)0 by algebra32) surjective: for any y there exists x A , such that f (x)=y .Take arbitrary y A and find x A from f (x)=y 11xxy11)( xxy1 xyyx11)( yyxAyyx 114Composition of functions---a A f B f (a)=b gCg (b)=cgf (Note, that in the context of function composition, the order in which the functions appear is backward, i. e. the rightmost function is applied first)Theorem. Let f : AB and g: BC be two functions. The composition of f and g as relations defines a function gf : A C, such that gf (a)= g(f(a)).5Proof. We need to prove that composite relation gf is a function. For this we must prove two things: 1) the composition gf relates each element aA to some c C. 2) an element c C assigned to a by gf is unique, so we can denote it c= g(f (a)). 1) existence: Let b=f (a) B. Let c=g(b) C. So, by the definition of composition of relations, (a, c)gf . Thus, cC [(a, c)gf ]-a A- gCg (b)=c- f B f (a)=bgf62) uniqueness: Suppose (a, c1)gf and (a, c2)gf . Then by the definition of composition, b1B, such that (a, b1)f and (b1, c1)g,and b2B, such that (a, b2)f and (b2, c2)g. Since f is a function, there may be only one b B, such that (a, b)f, so b1= b2. Since g is a function, (b, c1)g and (b, c2)g imply that c1= c2.Thus, (gf )(a)= c= g (b) = g (f (a)). a c1c2b1 f gb27Properties of the composite function• How the injective (surjective) property of gf depends on properties of f and g f g g f • g f • f g8Theorem. Consider functions f : AB and g: B C, and the composition gf : AC. a) If both f and g are injective, then gf is injective. b) If both f and g are surjective, then gf is surjective. c) If both f and g are bijective, then gf is bijective.Proof. a) Let a1 and a2 be arbitrary elements of A such that (gf )(a1) = (gf )(a2). By the previous Theorem, it implies that g (f (a1)) = g (f (a2)). Since g is injective it implies that f (a1) = f (a2), and since f is injective by assumption, a1 = a2. a1a2g(f (a1))=g(f (a2)). f g f (a1) f (a2) A BC9b) Take an arbitrary element cC. Since g is surjective, there exists bB such that g(b)=c. Similarly, since f is surjective,there exists aA such that f (a)=b. Then (gf )(a) = g(f(a)) = g(b) = c. So, gf is surjective. g surjective: c, b (g(b)=c) f surjective: b, a (f (a)=b)Cc- gB-b f Aa- gf10c) If both f and g are bijective, then both f and g are injective andsurjective. By parts a) and b) gf is injective and surjective, so gf is bijective. So, injective (surjective) properties of two functions, f and g are sufficient condition for injective (surjective) property of the composite function. The question arises whether both conditions are necessary as well. Let f : AB and g: B C be two functions and the composition gf : AC is injective. What properties of of f and g can be implied? What properties of f and g can be implied if gf is surjective?11Example. Let f : AB and g: B C be two functions such thatthe composite function gf : AC is injective. Prove or disprove that both f and g are injective. Injective property of gf : AC impliesif (gf )(x)=(gf )(y), then x = y. Let’s prove by contradiction that f must be injective. For this assume that gf is injective, but f is not injective. Then we can find x, y A such that x y and f (x)=f (y). By taking composite function for these x and y we have that g(f (x)) = g(f (y)) while x y. But this results to contradiction with injective property of composite function. gf injective f injective g( f (x))= g( f (y)) x y f gx y(gf )(y)(gf )(x)12What about gf injective g injective ? This implication can be disproved by the followingcounterexample: f g g is not injective, but gf is! If f was surjective, then we would not be able to disprove that gf injective g injective!13Example: f : [0, ] [0, ], f (x)=x/2. g : [0, ] [0, 1], g (y)=sin(y), not injective gf =sin(x/2): [0, ] [0, 1], is injective, but g is not. g(y) = sin(y): [0, ] [0, 1] gf =sin(x/2): [0, ] [0, 1]14Let’s prove that if gf is surjective then g is surjective. Surjective property of gf implies that for any zC there exists x A such that (gf )(x)=z. It means that g(f (x))=z. Since f is a function, there exists a unique element y B such that y=f (x). But g(f (x))= g(y)= z. zx gf -- y=f (x)Thus, for any zC there exists y B such that g(y)= z.Than means that g is surjective. Example. Let f : AB and g: B C be two functions such thatthe composite function gf : AC is surjective. Prove or disprove that both f and g are surjective.15The following example shows that gf is surjective f is surjective/ f gIf we knew that g were injective, we could prove thatgf is surjective f is surjective !16Example. Let f : RR, and g : RR denote two functions, where R is the set of real numbers. Suppose gf (x)=2x+1 forall x R ( i. e. the composite function is both surjective and injective).a) Prove that the function f is injection. Let f (x)= f (y), we need to show that x = y. Since g is a function on a set of real numbers, f (x)= f (y) implies g(f (x))= g (f (y)), i. e. 2x+1 = 2y+1 (by assumption gf (x)=2x+1).So, it yields x = y . QED.b) Prove the function g is a surjection. Take arbitrary z R, we need to show that y R such that g(y)=z.But for any z R there always exist x, y R, x = (z1)/2 and y=f (x), so that g(y) = g (f
View Full Document
Unlocking...