Report

Functions Goals • Introduce the concept of function • Introduce injective, surjective, & bijective functions Definition • Let D & C be nonempty sets. • Function f from D to C assigns elements of D to elements of C: For each d D, f assigns d to exactly 1 element c C, denoted f( d ) = c. d D c C ( f( d ) = c c’ C ( f( d ) = c’ c = c’ ) ) d D !c C f( d ) = c. Copyright © Peter Cappello 2 • If f is a function from D to C, we write f : D C. • Functions also are known as: Mappings Transformations. • Functions pass the vertical line test. Copyright © Peter Cappello 3 Definition • A function is a subset of a Cartesian product: If f : D C then f D x C. • If f : D C then: D is f’s domain C is f’s codomain. • If f( d ) = c then: c is the image of d d is a pre-image of c. • f’s range is { c | d f( d ) = c }. Copyright © Peter Cappello 4 Example • Let f : Z N be f( x ) = x2. • What is f’s domain? • What is f’s codomain? • What is the image of 4? • What is the pre-image of 4? • What is f’s range? Copyright © Peter Cappello 5 When are functions equal? Let f1: D C & f2: D C. Since – A function is a subset of a Cartesian product. – A Cartesian product is a set. when does f1 = f2 ? Copyright © Peter Cappello 6 Declaring a function’s domain & codomain The Java statement long square( int x ) { … } The domain of square is? Its codomain is? Copyright © Peter Cappello 7 The Image of a Set • Let f : D C and S D. • The image of S under f, denoted f( S ) is { c | s S, f( s ) = c }. • If S is finite, can | S | be <, =, or > | f( S ) | ? • Let f : N N , f( n ) = n mod 5. – What is f’s range? – Let O = { n N | n is odd } . – What is f( O ) ? Copyright © Peter Cappello 8 One-to-One (Injective) Functions • Let f : D C. • f is one-to-one (injective) when a D b D ( a b f (a ) f( b ) ). Different domain elements have different images. • Example – Let n: { T, F } { T, F }, such that n( p ) = p. – Is n injective? • Is f : Z Z, f( z ) = z2 injective? • Injective functions pass the horizontal line test. Copyright © Peter Cappello 9 Onto (Surjective) Functions • Let f : D C. f is onto (surjective) when c C d D ( f( d ) = c ). f’s range equals its codomain. • Example – Let or : { T, F } { T, F } { T, F }, such that or( p, q ) = p q. – Is or surjective? • Is f : Z Z, f( z ) = z2 surjective? • Is f : Z Z, f( z ) = z mod 5 surjective? • Is f : Z { 0, 1, 2, 3, 4}, f( z ) = z mod 5 surjective? Copyright © Peter Cappello 10 One-to-One Correspondence (Bijection) • Function f is a one-to-one correspondence (bijection) when it is both: one-to-one (injective) onto (surjective). • Let f : R R, f( x ) = 2x – 7. Is f a bijection? • Let f : D C be a bijection, where D, C are finite. – Can |D| > |C|? – Can |D| < |C|? Copyright © Peter Cappello 11 Inverse Functions • Let g : D C be a bijection. • The inverse function of g, denoted g-1, is the function : C D such that if g( d ) = c, then g-1( c ) = d. • If g is bijective, g-1 is a function because g is: – onto: c C ( c is the image of some element in D ) – 1-to-1: c C (c is the image of at most 1 element in D ) – Diagram this. • If g : D C is not a bijection, does g-1 exist (as a function)? Always? Sometimes? Never? Copyright © Peter Cappello 12 Composition of Functions • Let functions f : B C & g: A B. • The composition of f & g, denoted f g, is defined as f g( a ) = f( g( a ) ), for a A a g( a ) f(g( a )) A B C Copyright © Peter Cappello 13 Example • Let f : Q Q, f( x ) = 2x + 1. • Let g : Q Q, g( x ) = ( x – 1 ) / 2. • What is ( g f )( 17 )? • In general, what is g-1 g ( x ) ? Copyright © Peter Cappello 14 Exercise Let S U. The characteristic function of S fS : U { 0, 1 } is such that x S fS ( x ) = 1 A x S fS ( x ) = 0. 3 B 4 2 Show that: f A B (x) = fA( x )fB( x ) 1 f A B (x) = fA( x ) + fB( x ) - f A B ( x ) Copyright © Peter Cappello 15 End of Lecture Copyright © Peter Cappello 2011 16 • The Java statement long square( int x ) { … } square’s domain is int; its codomain is long. • Let f & g be functions from A to R. (f + g)( x ) = f( x ) + g( x ), ( fg )( x ) = f( x )g( x ). • Let f( x ) = x2 and g( x ) = x – x2. • What is f + g? gf? Copyright © Peter Cappello 2011 17 Graphs of Functions • Let f : A B. • The graph of f = { (a, b) | a A and f( a ) = b }. • Example: Let the domain of f be N. Draw: f( x ) = x2 f( x ) = x mod 2. Copyright © Peter Cappello 2011 18