IntroductionDefinitionsOne-To-One & OntoExamplesExercisesInverses and CompositionsImportant FunctionsFunctionsCSE235IntroductionOne-To-One& OntoInverses andCompositionsImportantFunctionsFunctionsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueiryFall 2007Computer Science & Engineering 235Introduction to Discrete MathematicsSection 2.3 of [email protected] / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsIntroductionYou’ve already encountered functions throughout youreducation.f(x, y) = x + yf(x) = xf(x) = sin xHere, however, we will study functions on discrete domains andranges. Moreover, we generalize functions to m appings. Thus,there may not always be a “nice” way of writing functions likeabove.2 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionFunctionDefinitionA function f from a set A to a set B is an assignment ofexactly one element of B to each element of A. We writef(a) = b if b is the unique element of B assigned by thefunction f to the element a ∈ A. If f is a function from A toB, we writef : A → BThis 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 elementsin A or not at all.3 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsTerminologyDefinitionLet f : A → B and let f(a) = b. Then we use the followingterminology:A is the domain of f, denoted dom(f ).B is the codomain of f.b is the image of a.a is the preimage (antece dent) of b.The range of f is the set of all images of elements of A,denoted rng(f ).4 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomainCodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.5 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinition IMore DefinitionsDefinitionLet f1and f2be functions from a set A to R. Then f1+ f2and f1f2are also functions from A to R defined by(f1+ f2)(x) = f1(x) + f2(x)(f1f2)(x) = f1(x)f2(x)ExampleLet f1(x) = x4+ 2x2+ 1 and f2(x) = 2 − x2then(f1+ f2)(x) = (x4+ 2x2+ 1) + (2 − x2)= x4+ x2+ 3(f1f2)(x) = (x4+ 2x2+ 1) · (2 − x2)= −x6+ 3x2+ 26 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinition IIMore DefinitionsDefinitionLet f : A → B and let S ⊆ A. The image of S is the subset ofB that consists of all the images of the elements of S. Wedenote the image of S by f (S), so thatf(S) = {f(s) | s ∈ S}Note that here, an image is a set rather than an element.7 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinition IIIMore DefinitionsExampleLetA = {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 / 47FunctionsCSE235IntroductionDefinitionsOne-To-One& OntoInverses andCompositionsImportantFunctionsDefinition IVMore DefinitionsDefinitionA function f whose domain and codomain are subsets of theset 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 . Afunction f is called strictly decreasing if f(x) > f(y) wheneverx < y and x and y are in the domain of f.9 / 47FunctionsCSE235IntroductionOne-To-One& OntoExamplesExercisesInverses andCompositionsImportantFunctionsInjections, Surjections, Bijections IDefinitionsDefinitionA function f is said to be one-to-one (or injective) iff(x) = f(y) ⇒ x = yfor all x and y in the domain of f. A function is an injection ifit is one-to-one.Intuitively, an injection simply means that each element in Bhas at most one preimage (antece dent).It may be use ful to think of the contrapositive of this definition:x 6= y ⇒ f (x) 6= f(y)10 / 47FunctionsCSE235IntroductionOne-To-One& OntoExamplesExercisesInverses andCompositionsImportantFunctionsInjections, Surjections, Bijections IIDefinitionsDefinitionA function f : A → B is called onto (or surjective) if for everyelement b ∈ B there is an element a ∈ A with f(a) = b. Afunction is called a surjection if it is onto.Again, intuitively, a surjection means that every element in thecodomain is mapped. This implies that the range is the sameas the codomain.11 / 47FunctionsCSE235IntroductionOne-To-One& OntoExamplesExercisesInverses andCompositionsImportantFunctionsInjections, Surjections, Bijections IIIDefinitionsDefinitionA function f is a one-to-one correspondence (or a bijection, ifit is both one-to-one and onto.One-to-one correspondences are important bec ause they endowa function with an inverse. They also allow us to have aconcept of cardinality for infinite se ts!Let’s take a look at a few general examples to get the feel forthese definitions.12 / 47FunctionsCSE235IntroductionOne-To-One& OntoExamplesExercisesInverses andCompositionsImportantFunctionsFunction ExamplesA Non-functionA Ba1a2a3a4b1b2b3b4This is not a function: Both a1and a2map to more than oneelement in B.13 / 47FunctionsCSE235IntroductionOne-To-One& OntoExamplesExercisesInverses andCompositionsImportantFunctionsFunction ExamplesA Function; Neither One-To-One Nor OntoABa1a2a3a4b1b2b3b4This function not one-to-one since a1and a3both map to b1.It is not onto either since b4is not
View Full Document