FunctionsSlides by Christopher M. BourkeInstructor: Berthe Y. ChoueirySpring 2006Computer Science & Engineering 235Introduction to Discrete MathematicsSections 1.8 of [email protected]’ve already encountered functions throughout your education.f(x, y) = x + yf(x) = xf(x) = sin xHere, however, we will study functions on discrete domains andranges. Moreover, we generalize functions to mappings. Thus,there may not always be a “nice” way of writing functions likeabove.NotesDefinitionFunctionDefinitionA function f from a set A to a set B is an assignment of exactlyone element of B to each element of A. We write f (a) = b if b isthe unique element of B assigned by the function f to the elementa ∈ A. If f is a function from A to B, we writef : A → BThis can be read as “f maps A to B”.Note the subtlety:IEach and every element in A has a single mapping.IEach element in B may be mapped to by several elements inA or not at all.NotesDefinitionsTerminologyDefinitionLet f : A → B and let f(a) = b. Then we use the followingterminology:IA is the domain of f, denoted dom(f).IB is the codomain of f .Ib is the image of a.Ia is the preimage of b.IThe range of f is the set of all images of elements of A,denoted rng(f ).NotesDefinitionsVisualizationA BabfDomain CodomainPreimageImage, f(a) = bRangeA function, f : A → B.NotesDefinition IMore DefinitionsDefinitionLet f1and f2be functions from a set A to R. Then f1+ f2andf1f2are also functions from A to R defined by(f1+ f2)(x) = f1(x) + f2(x)(f1f2)(x) = f1(x)f2(x)ExampleNotesDefinition IIMore DefinitionsLet 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+ 2DefinitionLet f : A → B and let S ⊆ A. The image of S is the subset of Bthat consists of all the images of the elements of S. We denote theimage of S by f(S), so thatf(S) = {f (s) | s ∈ S}NotesDefinition IIIMore DefinitionsNote that here, an image is a set rather than an element.ExampleLetIA = {a1, a2, a3, a4, a5}IB = {b1, b2, b3, b4}If = {(a1, b2), (a2, b3), (a3, b3), (a4, b1), (a5, b4)}IS = {a1, a3}Draw a diagram for f.The image of S is f (S) = {b2, b3}DefinitionNotesDefinition IVMore DefinitionsA function f whose domain and codomain are subsets of the set ofreal numbers is called strictly increasing if f (x) < f(y) wheneverx < y and x and y are in the domain of f. A function f is calledstrictly decreasing if f(x) > f(y) whenever x < y and x and y arein the domain of f.NotesInjections, 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 if it isone-to-one.Intuitively, an injection simply means that each element in Auniquely maps to an element in b.It may be useful to think of the contrapositive of this definition:x 6= y ⇒ f(x) 6= f (y)NotesInjections, 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 same asthe codomain.NotesInjections, Surjections, Bijections IIIDefinitionsDefinitionA function f is a one-to-one correspondence (or a bijection, if it isboth one-to-one and onto.One-to-one correspondences are important because they endow afunction with an inverse. They also allow us to have a concept ofcardinality for infinite sets!Let’s take a look at a few general examples to get the feel forthese definitions.NotesFunction ExamplesA Non-functionA Ba1a2a3a4b1b2b3b4This is not a function: Both a1and a2map to more than oneelement in B.NotesFunction ExamplesA Function; Neither One-To-One Nor OntoA Ba1a2a3a4b1b2b3b4This function not one-to-one since a1and a3both map to b1. It isnot onto either since b4is not mapped to by any element in A.NotesFunction ExamplesOne-To-One, Not OntoA Ba1a2a3b1b2b3b4This function is one-to-one since every ai∈ A maps to a uniqueelement in B. However, it is not onto since b4is not mapped to byany element in A.NotesFunction ExamplesOnto, Not One-To-OneA Ba1a2a3a4b1b2b3This function is onto since every element bi∈ B is mapped to bysome element in A. H owever, it is not one-to-one since b3ismapped to more than one element in A.NotesFunction ExamplesA BijectionA Ba1a2a3a4b1b2b3b4This function is a bijection because it is both one-to-one and onto;every element in A maps to a unique element in B and everyelement in B is mapped by some element in A.NotesExercises IExercise IExampleLet f : Z → Z be defined byf(x) = 2x − 3What is the domain and range of f? Is it onto? One-to-one?Clearly, dom(f ) = Z. To see what the range is, note thatb ∈ rng(f ) ⇐⇒ b = 2a −3 a ∈ Z⇐⇒ b = 2(a −2) + 1⇐⇒ b is oddNotesExercises IIExercise ITherefore, the range is the set of all odd integers. Since the rangeand codomain are different, (i.e. rng(f) 6= Z) we can alsoconclude that f is not onto.However, f is one-to-one. To prove this, note thatf(x1) = f(x2) ⇒ 2x1− 3 = 2x2− 3⇒ x1= x2follows from simple algebra.NotesExercisesExercise IIExampleLet f be as before,f(x) = 2x − 3but now define f : N → N. What is the domain and range of f ? Isit onto? One-to-one?By changing the domain/codomain in this example, f is not even afunction anymore. Consider f(1) = 2 · 1 − 3 = −1 6∈ N.NotesExercises IExercise IIIExampleDefine f : Z → Z byf(x) = x2− 5x + 5Is this function one-to-one? Onto?It is not one-to-one since forf(x1) = f(x2) ⇒ x21− 5x1+ 5 = x22− 5x2+ 5⇒ x21− 5x1= x22− 5x2⇒ x21− x22= 5x1− 5x2⇒ (x1− x2)(x1+ x2) = 5(x1− x2)⇒ (x1+ x2) = 5NotesExercises IIExercise IIITherefore, any x1, x2∈ Z satisfies the equality (i.e. there are aninfinite number of solutions). In particular f (2) = f (3) = −1.It is also not onto. The function is a parabola with a globalminimum (calculus exercise) at (52, −54). Therefore, the functionfails to map to any integer less than −1.What would happen if we changed the domain/codomain?NotesExercises IExercise IVExampleDefine f : Z → Z byf(x) = 2x2+ 7xIs this function one-to-one? Onto?Again, since this is a parabola, it cannot be onto (where is theglobal minimum?).NotesExercises IIExercise IVHowever, it is one-to-one. We follow a similar argument as
View Full Document
Unlocking...