FunctionsDefinition of a functionFunction terminologyMore functionsEven more functionsFunction arithmeticOne-to-one functionsMore on one-to-oneOnto functionsMore on ontoOnto vs. one-to-oneBijectionsIdentity functionsInverse functionsMore on inverse functionsCompositions of functionsSlide 17Slide 18Slide 19Graphs of functionsUseful functionsSample floor/ceiling questionsCeiling and floor propertiesCeiling property proofFactorialProving function problemsSlide 27Slide 28Slide 29Slide 301FunctionsCS 202Epp section ???Aaron Bloomfield2Definition of a function•A function takes an element from a set and maps it to a UNIQUE element in another set3Function terminologyR Zf4.34DomainCo-domainPre-image of 4Image of 4.3f maps R to Zf(4.3)4More functions12345“a”“bb““cccc”“dd”“e”A string length functionABCDFAliceBobChrisDaveEmmaA class grade functionDomain Co-domainA pre-imageof 1The imageof A5Even more functions12345“a”“bb““cccc”“dd”“e”Not a valid function!Also not a valid function!12345aeiouSome function…Range6Function arithmetic•Let f1(x) = 2x•Let f2(x) = x2•f1+f2 = (f1+f2)(x) = f1(x)+f2(x) = 2x+x2•f1*f2 = (f1*f2)(x) = f1(x)*f2(x) = 2x*x2 = 2x37One-to-one functions12345aeioA one-to-one function12345aeioA function that is not one-to-one•A function is one-to-one if each element in the co-domain has a unique pre-image–Meaning no 2 values map to the same result8More on one-to-one•Injective is synonymous with one-to-one–“A function is injective”•A function is an injection if it is one-to-one•Note that there can be un-used elements in the co-domain12345aeioA one-to-one function9Onto functions12345aeioA function that is not onto•A function is onto if each element in the co-domain is an image of some pre-image–Meaning all elements in the right are mapped to1234aeiouAn onto function101234aeiouAn onto functionMore on onto•Surjective is synonymous with onto–“A function is surjective”•A function is an surjection if it is onto•Note that there can be multiply used elements in the co-domain11Onto vs. one-to-one•Are the following functions onto, one-to-one, both, or neither?1234abc123abcd1234abcd1234abcd1234abc1-to-1, not ontoOnto, not 1-to-1Both 1-to-1 and onto Not a valid functionNeither 1-to-1 nor onto12Bijections•Consider a function that isboth one-to-one and onto:•Such a function is a one-to-one correspondence, or a bijection1234abcd13Identity functions•A function such that the image and the pre-image are ALWAYS equal•f(x) = 1*x•f(x) = x + 0•The domain and the co-domain must be the same set14Inverse functionsR Rf4.38.6Let f(x) = 2*xf-1f(4.3)f-1(8.6)Then f-1(x) = x/215More on inverse functions•Can we define the inverse of the following functions?•An inverse function can ONLY be done defined on a bijection1234abc123abcdWhat is f-1(2)?Not onto!What is f-1(2)?Not 1-to-1!16Compositions of functions•Let (f ○ g)(x) = f(g(x))•Let f(x) = 2x+3 Let g(x) = 3x+2•g(1) = 5, f(5) = 13•Thus, (f ○ g)(1) = f(g(1)) = 1317Compositions of functionsg ff ○ gg(a)f(a)(f ○ g)(a)g(a)f(g(a))aAB C18Compositions of functionsg ff ○ gg(1)f(5)(f ○ g)(1)g(1)=5f(g(1))=131RR RLet f(x) = 2x+3 Let g(x) = 3x+2f(g(x)) = 2(3x+2)+3 = 6x+719Compositions of functionsDoes f(g(x)) = g(f(x))?Let f(x) = 2x+3 Let g(x) = 3x+2f(g(x)) = 2(3x+2)+3 = 6x+7g(f(x)) = 3(2x+3)+2 = 6x+11Function composition is not commutative!Not equal!20Graphs of functionsLet f(x)=2x+1Plot (x, f(x))This is a plotof f(x)x=1f(x)=3x=2f(x )=521Useful functions•Floor: x means take the greatest integer less than or equal to the number•Ceiling: x means take the lowest integer greater than or equal to the number•round(x) = floor(x+0.5)22Sample floor/ceiling questions•Find these values1.11.1-0.1-0.12.99-2.99½+½½ + ½ + ½12-103-2½+1 = 3/2 = 10 + 1 + ½ =  3/2 = 223Ceiling and floor propertiesLet n be an integer(1a) x = n if and only if n ≤ x < n+1(1b) x = n if and only if n-1 < x ≤ n(1c) x = n if and only if x-1 < n ≤ x(1d) x = n if and only if x ≤ n < x+1(2) x-1 < x ≤ x ≤ = x < x+1 (3a) -x = - x(3b) -x = - x(4a) x+n = x+n (4b) x+n = x+n24Ceiling property proof•Prove rule 4a: x+n = x+n–Where n is an integer–Will use rule 1a: x = n if and only if n ≤ x < n+1•Direct proof!–Let m =  x–Thus, m ≤ x < m+1 (by rule 1a)–Add n to both sides: m+n ≤ x+n < m+n+1–By rule 4a, m+n = x+n–Since m = x, m+n also equals x+n–Thus, x+n = m+n = x+n25Factorial•Factorial is denoted by n!•n! = n * (n-1) * (n-2) * … * 2 * 1•Thus, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720•Note that 0! is defined to equal 126Proving function problems•Let f be a function from A to B, and let S and T be subsets of A. Show that)()()( ))()()( )TfSfTSfbTfSfTSfa27Proving function problems•f(SUT) = f(S) U f(T)•Will show that each side is a subset of the other•Two cases!•Show that f(SUT)  f(S) U f(T)–Let b  f(SUT). Thus, b=f(a) for some aS U T–Either aS, in which case bf(S)–Or aT, in which case bf(T)–Thus, bf(S) U f(T)•Show that f(S) U f(T)  f(S U T)–Let b  f(S) U f(T)–Either b  f(S) or b  f(T) (or both!)–Thus, b = f(a) for some a  S or some a  T–In either case, b = f(a) for some a  S U T28Proving function problems•f(S∩T)  f(S) ∩ f(T)•Let b  f(S∩T). Then b = f(a) for some a  S∩T•This implies that a  S and a  T•Thus, b  f(S) and b  f(T)•Therefore, b  f(S) ∩ f(T)29Proving function problems•Let f be an invertible function from Y to Z•Let g be an invertible function from X to Y•Show that the inverse of f○g is:–(f○g)-1 = g-1 ○ f-130Proving function problems•Thus, we want to show, for all zZ and xX•The second equality is similar      xxgffgzzfggf)()(1111            