FunctionsA function is a special type of relation. In particular, here arethe rules for a relation to be a function, for an arbitraryrelation R A x B :For each element in a A, we must have EXACTLY 1 elementin R such that a is the first term of the ordered pair. In Englishthat means for each element in the set A it MUST BE related toexactly one element in the set B.Note that this means we must have |A| |B|, when the sets Aand B are finite. Typically, we call the set A the domain and theset B the co-domain.It is possible that all of the possible values of f(a) (when a A)form only a proper subset of B. Thus the set of possible valuesof the function, which can be more formally written as follows:f(A) = { f(a) | a A } is known as the range of the function.Here is an example of a function :Let the set A = { the set of words in the English language }For all a A, define f(a) as follows:f(a) = the number of letters in the word a.Thus, we have that the domain is the set of all English words,the co-domain is the set of all positive integers, and the range isall positive integers less than 29, (assuming thatantidisestablishmentarianism is the longest word in the Englishlanguage).However, recall the relation I showed you in an earlier lecture:Cocktails = {(Orange Juice, Vodka), (Cranberry Juice, Vodka), (Coke, Rum), (Orange Juice, Peach Schnapps) }This is not a function because Orange Juice is related to morethan one element of the range.Note that you can define functions on multiple sets, just as youcan define relations on multiple sets. Consider the following:f(a,b) = a+b.This is a function of two real number variables. Notice thatdifferent ordered pairs of this function map to the sameelement in the range. For example, f(2,3) = f(4,1).We have already talked about composing relations together.Now we will introduce function composition.Consider the following example, which uses the first functionfrom this lecture:f(a) = the number of letters in the word a.g(b) = the sum of the digits in the integer b.Consider inputting the output from f(a) into the function g.Pictorially, we get something like this:Composing Functions produces a functionLet f: A B and g: B C be two functions. The composition off and g as relations defines a function g f : A C, such that g f (a) = g(f(a)).We need to show that for each element a A, the expression(or formula) g(f(a)) assigns the unique element of C related to abased on the composition of f and g considered as relations. Bythe definition of relation composition,g f = {(a, c) | a A c C (b B | (a, b) f (b, c) g)}.However, (a, b) f means b = f (a) using the function notation,and (b, c) g means c = g(b) by the function notation. Thus,the relation g f contains pairs (a, c) with a A and c C,such that c = g(b) = g(f(a)), by substitutions. Further, thiselement c that is related to element a via the composed relationg f is unique; thus, the relation g f defines a function g f :A C.Consider an example from math class. Let f(x) = x3 and g(x) =2x – 1. We have the following function compositions :f g(x) = f(g(x)) = f(2x – 1) = (2x – 1)3g f(x) = g(f(x)) = g(x3) = 2x3 – 1As can be seen from this example, typically, f(g(x)) g(f(x))Injection, Surjection and BijectionThese definitions are often confusing, but I think some pictureswill help... A function f is injective, or is one-to-one, if for all a, b A, a b f(a) f(b). Equivalently, this means if f(a) = f(b) then a = b.We also say f is an injection in this case. f is surjective, or is onto, if f(A) = B. That is, if for every b Bthere exists a A such that f(a) = b. We also say f is asurjection in this case.f is bijective if it is both injective and surjective. We also say fis a bijection in this case.Consider these questions :Is the function f(x) = x2 injective, where the domain and co-domain are all real numbers?Is the function f(x) = sin x surjective, where the co-domain isthe set of real numbers in the interval [-1,1].Is the function f(x) = x3 a bijection?Consider functions f: A B and g: B C, and the compositiong f : A C.(a) If both f and g are injective, then g f is injective.(b) If both f and g are surjective, then g f is surjective.(c) If both f and g are bijective, then g f is bijective.To prove g f is injective, we need to prove that for a, b A,if g f (a) = g f (b) then a = b, by the definition of injection. g(f(a)) = g(f(b))Since g is injective, that means for these two to be equal, wemust have f(a) = f(b).However, we also know that f is injective, thus, this impliesthat a=b.Inverse FunctionsA bijection f: A B maps each element of A to a uniqueelement of B, and conversely, each element of B has a uniqueelement of A as its pre-image. The following theorem makes aprecise statement of this relationship.Let f: A B be a bijection. Then the inverse relation of f,defined from B to A as {(b, a) | b B and a A, and f (a) = b},is a function from B to A such that g f(a) = a for all a A, andf g(b) = b for all b B. The function g is called the inversefunction of f, denoted f–1.Note that since f: A B is a bijection, for each b B thereexists one and only one element a A, such that f (a) = b.Thus, the relation from B to A, relating b B to its pre-image a A under f, is a function by the definition of function. That is,we have defined a function g: B A such that for b B, g(b) = a iff f (a) = b g f (a) = g(f(a)), = g(b) = a. f g(b) = f(g(b)) = f(a) = b.Let f: A B and g: B A be two functions. If g f(a) = a for alla A, and f g(b) = b for all b B, then both f and g arebijections, and they are inverse functions of each other, that is,g = f–1 and f = g–1.First, we will show that if g f(a) = a, for all a A and f g(b)= b, for all b B, then f is a bijection and g = f–1 We first prove that f is an injection. That is, suppose f(a) = f(a’), for …
View Full Document
Unlocking...