FunctionsSP22 MATH/CS 240: Discrete MathematicsUW-MadisonReference: zyBook chapter 4SP22 MATH/CS 240: Discrete Mathematics Functions 1 / 20Learning objectivesBe familiar with the following notions and the interactions between them:1Domain, target/codomain, range2Onto/surjective, one-to-one/injective, bijective3Inverses of functions4Composition of functionsSP22 MATH/CS 240: Discrete Mathematics Functions 2 / 20What is a function?DefinitionLet A and B be sets. A function f : A → B is an assignment of exactly one element ofB to each element of A. If f assigns b ∈ B to a ∈ A, we write f (a) = b and say that fmaps/sends a to b.A and B are called the domain and target/codomain of f , respectively.Examples:1Define f : N → N by f (x) = x + 1.2Define g : N → R by g(x) = x + 1.3At the end of the semester, every student earns a grade. That defines a functionfrom the set of students to the set of grades.When defining a function, remember to specify its domain and target/codomain!SP22 MATH/CS 240: Discrete Mathematics Functions 3 / 20Functions as subsets of a Cartesian productA function f : A → B can be thought of as a set Gfwhich is a subset of A × B andsatisfies the following special property:For every a ∈ A, there is exactly one b ∈ B such that (a, b) ∈ Gf.We call Gfthe graph of f .CaveatEquality as functions differs from equality as sets! For example, the functions f and gfrom the previous slide have the same graph even though they are not equal asfunctions (because they have different targets).SP22 MATH/CS 240: Discrete Mathematics Functions 4 / 20Well-definedDefinitionIf f maps an element of the domain to zero elements or more than one element of thetarget, then f is not well-defined.The reason we have such terminology is because it is quite easy to write downdefinitions of objects which “look like” functions but are not functions:Examples1Define f : R → R by f (x) = 1/x. Then f is not well-defined because f (0) is notdefined.2Define g : R+→ R by (g(x))2= x. Then g is not well-defined because g(1)could be either 1 or −1.3Define h : R → N by h(x) = x + 1. Then h is not well-defined becauseh(−1/2) = 1/2 and 1/2 is not in the target of h.SP22 MATH/CS 240: Discrete Mathematics Functions 5 / 20Range of a function, surjective functionsDefinitionThe range of a function f : A → B is the set {b ∈ B : (∃a ∈ A)(f (a) = b)}.The range of a function is always a subset of its target/codomain. (Otherwise thefunction is not well-defined.)The range of f : A → B is often written as {f (a) : a ∈ A}. (This is a variant ofset-builder notation.)DefinitionA function is surjective or onto, if its range is the same as its target/codomain.Examples1Define f : N → N by f (x) = x + 1. Is f onto?2Define g : R → R by g(x) = x + 1. Is g onto?SP22 MATH/CS 240: Discrete Mathematics Functions 6 / 20Injective functionsAnother useful property that some functions enjoy isDefinitionA function f : A → B is injective or one-to-one if no two distinct elements in A aremapped to the same element in B.How can we express “f is one-to-one” as a predicate?Examples1Define f : N → N by f (x) = x + 1. Is this one-to-one?2Consider the function which maps each UW-Madison student to their GPA. Is thisone-to-one?SP22 MATH/CS 240: Discrete Mathematics Functions 7 / 20Bijective functionsDefinitionA function is a bijection or a one-to-one correspondence, if it is one-to-one and onto.Later in the semester, bijections will be useful for counting the size of sets. In the nextslide, we see why this is the case.SP22 MATH/CS 240: Discrete Mathematics Functions 8 / 20One-to-one functions, onto functions, bijections and sizeFactLet A and B be finite sets. Then:1If there is some one-to-one function f : A → B, then |A| ≤ |B|.2If there is some onto function f : A → B, then |A| ≥ |B|.Therefore, if there is some bijection f : A → B, then |A| = |B|.The above facts underline the technique of combinatorial proof, which entails countingthe cardinality of a set A by constructing two objects:a set B whose cardinality is easy to determine;a bijection f : A → B.We will see examples of this method later in the semester.SP22 MATH/CS 240: Discrete Mathematics Functions 9 / 20Cardinality of infinite sets (not in the scope of our course)Can we define a useful notion of cardinality for infinite sets?How should we compare the cardinality of the following sets?Z = {. . . , −1,0, 1, . . . } andN = {0, 1, . . . }How about the set of even numbers and the set of odd numbers? How does theircardinality compare?Such questions have been contemplated since ancient Greece. A monumental advancewas:Theorem (Cantor, late 19thcentury)The set of real numbers R cannot be “listed”, i.e., there is no bijection between R andthe set of natural numbers N.SP22 MATH/CS 240: Discrete Mathematics Functions 10 / 20Cardinality of infinite sets (not in the scope of our course)Theorem (Cantor, late 19thcentury)The set of real numbers R cannot be “listed”, i.e., there is no bijection between R andthe set of natural numbers N.Cantor’s proof of the above theorem is now known as Cantor’s diagonal argument.DefinitionTwo sets A and B have the same cardinality, written |A| = |B|, if there is a bijectionbetween A and B.Observe that for finite sets, this definition agrees with our earlier definition ofcardinality for finite sets: There is a bijection between finite sets A and B if and only ifthey have the same number of elements.SP22 MATH/CS 240: Discrete Mathematics Functions 11 / 20Cardinality of infinite sets (not in the scope of our course)Note that our intuition for finite sets doesn’t always transfer to infinite sets:An infinite set can have the same cardinality as a proper subset of it!Proof sketch: We prove that Z and N have the same cardinality. The following listdefines a bijection from N to Z (map each n ∈ N to the nthelement of the list):0, 1, −1, 2, −2, 3, −3, . . .SP22 MATH/CS 240: Discrete Mathematics Functions 12 / 20Inverse functionsDefinitionLet f : A → B be a bijection. The inverse of f , denoted f−1: B → A, is the functiondefined by f−1(b) = a whenever f (a) = b.Example: Consider the exponential function with domain [0, ∞) and target [1, ∞). Itsinverse is the logarithm function.We will use logarithms later in the semester, when we discuss complexity of algorithms.A refresher on logarithms can be found in zybook 4.6.Think about why the inverse actually is a function. Since f is a