CS计算机代考程序代写 discrete mathematics Queen’s University

Queen’s University
School of Computing

CISC 203: Discrete Mathematics for Computing II
Module 6: Functions

Fall 2021

This module corresponds to the following sections from your textbook:

24. Functions

25. The Pigeonhole Principle

26. Composition

27. Permutations

1 Functions
Definition 1 (Function). A relation f : A −→ B is called a function if (a, b) ∈ f and (a, c) ∈ f implies
b = c.

Intuitively, a function is a “machine” that transforms one quantity into another, but each input quantity can
not have more than one output quantity.

Example 2. Let
f = {(1, 2), (2, 3), (3, 1), (4, 7)} and g = {(1, 2), (1, 3), (4, 7)}.

The relation f is a function but the relation g is not a function because (1, 2), (1, 3) ∈ g and 2 6= 3.

If f is a function whose output value is y when the input is x, we write f(x) = y. We say that f maps x to
y.

For example, we can can express function f(x) = x2 on the integers as a set of ordered pairs, as

f = {. . . , (−3, 9), (−2, 4), (−1, 1), (0, 0), (1, 1), (2, 4), (3, 9), . . .}.

We can also express it in set-builder notation as

f = {(x, y) : x, y ∈ Z, y = x2}.

As another example, the absolute value function abs takes an integer x as input and returns x if x is positive
and returns −x if x is negative, i.e.,

f(x) = abs(x) = |x| =

{
x if x ≥ 0
−x if x < 0. Similarly, abs can also be expressed as a set of ordered pairs, or in set-builder notation as f = {(x, y) : x, y ∈ Z, y = |x|}. Definition 3 (Domain and Image). The domain of a relation or function g is the set of all the first elements of the ordered pairs in g. We denote this as dom g = {a ∈ A : ∃b ∈ B, (a, b) ∈ g}, CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 2 or alternatively, dom g = {a ∈ A : g(a) is defined}. The image of a relation or function g is the set of all the second elements of the ordered pairs in g. We denote this as im g = {b ∈ B : ∃a ∈ A, (a, b) ∈ g}, or alternatively, im g = {b ∈ B : b = g(a) for some a}. Definition 4 (f : A −→ B). A function from set A to set B, denoted f : A −→ B, is a rule that assigns to each element a ∈ A a unique element f(a) ∈ B. The domain of f is the set A, i.e., dom f = A. In other words, for every element a ∈ A there is a pair (a, b) in f . The image of f is a subset of B, i.e., im f ⊆ B. In the abs function above, the argument of the function is an integer and the value is a non-negative integer so we may write abs : Z −→ N. Definition 5 (One-to-one, Onto, Bijection). Consider a function f : A −→ B. • The function f is called one-to-one (or injective) if whenever (a1, b), (a2, b) ∈ f, we must have a1 = a2. In other words, if a1 6= a2, then f(a1) 6= f(a2). • The function f is called onto B (or surjective) if for every b ∈ B, there exists an a ∈ A such that f(a) = b. • The function f is a bijection if it is both one-to-one and onto. Exercise Let A = {1, 2} and B = {3, 4}. Write down all functions f : A −→ B. Indicate which are one-to-one and which are onto B. To prove that a function is one-to-one, it must be shown that when f(a1) = f(a2), we have a1 = a2. This can also be done by contrapositive or by contradiction (see Proof Template 20, p. 172). To prove that a function f : A −→ B is onto B, show that for every element b ∈ B there must be an element a ∈ A such that f(a) = b. Alternatively, show that the set B is equal to im f (see Proof Template 21, p. 173). Example 6. Let A be the set of even integers and B be the set of odd integers. The function f : A −→ B defined by f(x) = x+ 1 is a bijection. Proof. We must prove that f is both one-to-one and onto. To show that f is one-to-one, suppose f(a1) = f(a2), where a1 and a2 are even integers: f(a1) = f(a2) =⇒ a1 + 1 = a2 + 1 =⇒ a1 = a2 So, f is one-to-one. To show that f is onto B, let b be any element from B (i.e., an odd integer). By definition, b = 2k + 1 for some integer k. Let a = 2k; since a is clearly even, we have a ∈ A. Then, f(a) = a+ 1 = 2k + 1 = b. So, f is onto. Since f is both one-to-one and onto, it is a bijection. CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 3 Example 7. The function f : Z −→ Z defined by f(x) = x2 is not one-to-one and not onto Z. Proof. f(3) = f(−3) = 9, but 3 6= −3, so f is not one-to-one. It is not onto Z either, since f(x) can never be a negative integer, so im f 6= Z. Example 8. The function f : R −→ Z defined by the floor function f(x) = bxc is onto Z but not one-to-one. Proof. To show that f is onto Z, let b be any integer. We take a = b, which is clearly in R. Then, f(a) = bac = bbc = b. So, f is onto. f(3.1) = f(3.3) = 3, but 3.1 6= 3.3, so f is not one-to-one. Exercise Show that the function f : Z −→ Z defined by f(x) = 2x is one-to-one but not onto. 1.1 Inverse functions Any relation R ⊆ A × B has a unique inverse relation R−1 ⊆ B × A. However, the inverse relation of a function f need not be a function, as shown in the following counterexample. Example 9. Let A = {0, 1, 2, 3, 4} and B = {5, 6, 7, 8, 9}. Let f : A→ B be defined by f = {(0, 5), (1, 7), (2, 8), (3, 9), (4, 7)}, so f−1 = {(5, 0), (7, 1), (8, 2), (9, 3), (7, 4)}. f−1 is not a function from B to A, for two reasons: 1. f−1 is not a function, since (7, 1) and (7, 4) are in f−1. This violates Definition 1. 2. dom f−1 6= B. This violates Definition 4. See Example 24.12 in the textbook for an illustration. Theorem 10. Let A and B be sets and let f : A→ B. The inverse relation f−1 is a function from B to A if and only if f is one-to-one and onto. Note that if f is one-to-one, but not onto, the inverse relation f−1 is still a function, but dom f−1 (which is equal to im f) will be a proper subset of B (and thus f−1 would not be a function from B to A, by Definition 4). 2 The Pigeonhole Principle The Pigeonhole Principle states that: If n pigeons are put into m holes, where n > m, then at least one
hole will contain more than one pigeon. To illustrate, suppose there are nine holes in a pigeon coop, and ten
pigeons fly to the coop to roost. If each of the ten pigeons is in a hole, then it must be the case that at least
one hole contains more than one pigeon.

The following two propositions follow from the Pigeonhole Principle.

Proposition 11. For a function f : A −→ B where A and B are finite sets:

i. if |A| > |B|, then f is not one-to-one; and

CISC 203: Discrete Mathematics for Computing II
Module 6, Fall 2021 Page 4

ii. if |A| < |B|, then f is not onto. We illustrate this with two examples. Example 12. Let A = {1, 2, 3} and B = {4, 5}. Since |A| > |B|, there is no function f : A −→ B that is
one-to-one.

Let A = {1, 2} and B = {3, 4, 5}. Since |B| > |A|, there is no function f : A −→ B that is onto.

The next proposition follows from the above proposition.

Proposition 13. Let A and B be finite sets and let f : A −→ B. If f is a bijection, then |A| = |B|.

Exercise

Let A = {1, 2, 3} and B = {4, 5}. Give a function f : A −→ B that is onto.

Let A = {1, 2} and B = {3, 4, 5}. Give a function f : A −→ B that is one-to-one.

The following is a generalized version of the Pigeonhole Principle.

Proposition 14. If n elements are partitioned into m subsets, then at least one subset must contain dn/me
or more elements.

Proof. Suppose we have n elements partitioned into m subsets. For the sake of contradiction, suppose that
no subset contains more than dn/me − 1 elements. Then the total number of elements is at most

m
(⌈ n
m


− 1
)
< m (( n m + 1 ) − 1 ) = n. Thus, we must have fewer than n elements. However, we assumed we had exactly n elements. Therefore, our assumption was incorrect and at least one subset must contain at least dn/me elements. � Example 15. In the 2017–2018 academic year, there were 11 783 students enrolled in the Faculty of Arts and Science at Queen’s University. Assume that each of these students was born in the same four-year period of 1996–1999. The given four-year period consisted of 1 461 days. Therefore, by the pigeonhole principle, at least d11 783/1 461e = 9 students in the Faculty of Arts and Science were born on the same day. Note that Proposition 11 and Proposition 13 are meaningful only for finite sets. For example, consider the set A of all positive integers {1, 2, 3, . . .} and the set B of all nonnegative integers {0, 1, 2, 3, . . .}. But the function f : A −→ B defined by f(x) = x − 1 is a bijection, even though A is a proper subset of B. Refer to p. 180 of your textbook for another bijection from N to Z. 3 Composition The composition of functions f : A −→ B and g : B −→ C is the function g ◦ f : A→ C defined by (g ◦ f)(a) = g(f(a)) for every a ∈ A. Note that the composition is defined only if the image of f equals the domain of g. When dealing with a function composition g ◦ f it is important to remember that the function f is applied first, and then apply function g to the resulting value. Example 16. Let A = {1, 2, 3, 4, 5}, B = {6, 7, 8, 9}, and C = {10, 11, 12, 13, 14}. Let f : A −→ B and g : B −→ C be defined by f = {(1, 6), (2, 6), (3, 9), (4, 7), (5, 7)} CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 5 and g = {(6, 10), (7, 11), (8, 12), (9, 13)}. Then (g ◦ f) = {(1, 10), (2, 10), (3, 13), (4, 11), (5, 11)}. For example, we can calculate (g ◦ f)(3) as follows. (g ◦ f)(3) = g(f(3)) = g(9) = 13. Which means (3, 13) ∈ g ◦ f . Example 17. Let f : Z −→ Z by f(x) = x2 + 1 and g : Z −→ Z by g(x) = 2x− 3. For example, we can calculate (g ◦ f)(3) as follows. (g ◦ f)(3) = g(f(3)) = g(32 + 1) = g(10) = 2× 10− 3 = 17. In general, (g ◦ f)(x) = g(f(x)) = g(x2 + 1) = 2(x2 + 1)− 3 = 2x2 + 2− 3 = 2x2 − 1 Note that you may verify the value of (g◦f)(3) by plugging 3 into the general expression for (g◦f)(x). We also note that the composition of functions is not commutative. For this example, we see that (g◦f)(3) 6= (f◦g)(3): (f ◦ g)(3) = f(g(3)) = f(2× 3− 3) = f(3) = 32 + 1 = 10. To prove that two functions f and g are equal, we must show that: 1. The domain of f equals the domain of g; and 2. For every x in their common domain, f(x) = g(x). Refer to Proof Template 22 on p. 185 of your textbook. So in the previous example, g ◦ f 6= f ◦ g since we showed that (g ◦ f)(3) 6= (f ◦ g)(3) (which violates the second condition above). The composition of functions is associative. For f : A −→ B, g : B −→ C and h : C −→ D we have h ◦ (g ◦ f) = (h ◦ g) ◦ f. This is proved in Proposition 26.6 (p. 185) of your textbook. Definition 18 (Identity function). The identity function on a set A, idA : A→ A, is defined as idA(a) = a for all a ∈ A. The identity function is a bijection. For example, the identify function on N, denoted as a set of ordered pairs, is idN = {(0, 0), (1, 1), (2, 2), (3, 3), . . .}. Example 19. Let A and B be sets, and let f : A −→ B. We will prove that f ◦ idA = idB ◦ f = f , using Proof Template 22. CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 6 Proof. The first condition of Proof Template 22 is satisfied, since we have: dom (f ◦ idA) = dom (idA) = A = dom (f) and dom (idB ◦ f) = dom (f) The second condition of Proof Template 22 is satisfied, since we have: (f ◦ idA)(a) = f(idA(a)) = f(a) and (idB ◦ f)(a) = idB(f(a)) = f(a). So, we have shown that f ◦ idA = idB ◦ f = f . Proposition 20. Let A and B be sets and suppose f : A −→ B is one-to-one and onto. Then, f−1 ◦ f = idA and f ◦ f−1 = idB , where f−1 is the inverse of f . Exercise Prove the above proposition, using the same technique (i.e., with Proof Template 22). 4 Permutations Definition 21 (Permutation). Given a set A, a permutation of A is a bijective function π : A→ A. A permutation is a function that maps elements of a set A to elements of the same set A. In other words, if our informal definition of a permutation is an arrangement of elements, then the permutation π itself is what performs the rearranging of elements. Example 22. Suppose we have a set A = {1, 2, 3, 4, 5, 6}. Let π : A −→ A be a function given by: π(1) = 3; π(4) = 2; π(2) = 4; π(5) = 1; π(3) = 5; π(6) = 6. We see that π is a bijection from A to A. We can more compactly represent the permutation π from the previous example using certain notations. The two-line notation uses a two-line matrix; the first line lists the elements of the set A, and the second line lists the permuted elements π(1) through π(6). Thus, π = [ 1 2 3 4 5 6 3 4 5 2 1 6 ] . What happens if we compose π with itself? Let’s trace what happens to the element 1. We are going to apply π twice: The first application maps 1 to 3, and the second application maps 3 to 5. If we apply π a third time, 5 is mapped back to 1. Treating π as a function, we see that π(1) = 3, (π ◦ π)(1) = 5, and CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 7 (π ◦ π ◦ π)(1) = 1. We can write this cycle as (1, 3, 5). Repeating the same process by tracing the elements 2 and 6 gives us the two cycles (2, 4) and (6), respectively. So in cycle notation, we can write π = (1, 3, 5)(2, 4)(6). In this notation, each set of parentheses represents a cycle, where the first element is mapped to the second element, the second element is mapped to the third element, and so on, and the last element is mapped back to the first element. Since the element 6 is always mapped to 6, we can leave that cycle out, giving us π = (1, 3, 5)(2, 4). Note that we can write π ◦ π as π2, π ◦ π ◦ π as π3, and so on. Composing permutations is just like composing other functions. If π and σ are permutations on a set, we can write π ◦ σ to represent the result of applying σ (as a function) and then applying π. Example 23. Let π = [ 1 2 3 4 4 1 3 2 ] and σ = [ 1 2 3 4 2 3 4 1 ] . We calculate π ◦ σ as follows: π ◦ σ(1) = π(σ(1)) = π(2) = 1 π ◦ σ(2) = π(σ(2)) = π(3) = 3 π ◦ σ(3) = π(σ(3)) = π(4) = 2 π ◦ σ(4) = π(σ(4)) = π(1) = 4 The result is in fact another permutation. This follows from the fact that the composition of two bijections will always be a bijection. We can create a diagram to visualize the composition of these two permutations, as follows. Figure 1: Visual representation of the composition of π and σ in Example 23. We can also just think of the operation of a permutation as “turns x into y”, so we can interpret π ◦ σ(3) as “σ turns 3 into 4, then π turns 4 into 2”. Exercise Write π, σ, π ◦ σ, σ ◦ π from the previous example in cycle notation. Theorem 24. Every permutation can be expressed as a collection of pairwise disjoint cycles. Furthermore, this representation is unique up to rearranging the cycles and cyclic order of the elements within cycles. CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 8 Definition 25 (Sn). The set of all permutations on the set {1, 2, . . . , n} is denoted Sn. Sn is called the symmetric group on n elements—we will revisit this when we cover Groups later in the course. Example 26. Here, we list all permutations on the set {1, 2} and on the set {1, 2, 3}. S2 = {[ 1 2 1 2 ] , [ 1 2 2 1 ]} = {(1)(2), (1, 2)} S3 = {[ 1 2 3 1 2 3 ] , [ 1 2 3 2 1 3 ] , [ 1 2 3 3 2 1 ] , [ 1 2 3 1 3 2 ] , [ 1 2 3 2 3 1 ] , [ 1 2 3 3 1 2 ]} = {(1)(2)(3), (1, 2)(3), (1, 3)(2), (1)(2, 3), (1, 2, 3), (1, 3, 2)} Note that in S2, (1)(2) = id{1,2} is the identity function on the set {1, 2}. In S3, (1)(2)(3) = id{1,2,3} is the identity function on the set {1, 2, 3}. For the identity function, we typically simplify the cycle notation to (1), so we can write id{1,2} = (1) and id{1,2,3} = (1) without any confusion. We denote the identity function with the Greek letter ι. In fact we almost always use Greek letters to name permutations: π, σ, and τ are among the favourites. Example 27. Let π ∈ S9 be given by π = [ 1 2 3 4 5 6 7 8 9 1 2 6 4 5 3 7 8 9 ] . In cycle notation, π = (1)(2)(3, 6)(4)(5)(7)(8)(9) = (3, 6). We write ι ∈ S9 as ι = (1). Proposition 28. There are n! permutations in Sn. The set Sn satisfies the following properties. 1. Closure: If π ∈ Sn and σ ∈ Sn, then π ◦ σ ∈ Sn. 2. Associativity: If π ∈ Sn and σ ∈ Sn and τ ∈ Sn, then π ◦ (σ ◦ τ) = (π ◦ σ) ◦ τ . 3. Identity element: There is a permutation ι such that π ◦ ι = ι ◦ π = π,∀π ∈ Sn. 4. Inverse: If π ∈ Sn, then π−1 ∈ Sn and π ◦ π−1 = π−1 ◦ π = ι. Each of the above properties follow from the definition of permutations and the properties of functions. Property 1 says that the composition of two permutations is another permutation. This sounds trivial but it is our first look at a very important concept: closure. When we apply an operation to two elements of a set and always get another element of the same set, we say that set is closed under that operation. Not all sets are closed under all operations. For example, N is not closed under the operation of subtraction (for instance, 3 ∈ N and 4 ∈ N, but 3 − 4 = −1, and −1 /∈ N). However, N is closed under addition and multiplication. This concept is vital to us as computer scientists because we frequently work with strongly typed programming languages, where each variable has a specific type that cannot change. If we are dealing with integer variables, we need to be sure the operations we perform will only produce integer values. Property 2 is called the associative property. It says that if we are composing a sequence of permutations we can group them with parentheses in different ways without changing the result. Property 3 asserts that the identity permutation ι can be composed with any permutation without changing it. Once again, we can draw a parallel to other sets and operations. For example, in the set N and the operation of multiplication, we know that for all x ∈ N, x× 1 = 1× x = x. Property 4 asserts that every permutation has an inverse. This property is also true for some sets and operations but not all. For example, in the set Z and the operation of addition, the identity element is 0 and every element has an inverse (for instance, the inverse of 7 is -7). However in the set N and the operation of CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 9 addition, the identity element is still 0 but the non-zero values do not have inverses (for instance there is no integer x ∈ N such that 8 + x = 0). Property 4 is particularly important when we use permutations in cryptography—there’s not much point encoding information with a permutation if there is not some other permutation that will do the decoding. Side note: A set and an operation that satisfy these four properties are called a group. Group theory is one of the most important branches of mathematics, with applications in communications, theoretical physics, applied physics, biology, chemistry, robotics and many other fields. We will learn about groups in Chapter 8. Note that there is a property possessed by many operations that is not true of the composition of permu- tations: commutativity. Commutativity holds when we can switch the left-to-right order of the operands without changing the result. For example, when we are adding integers, we know that x + y = y + x and the same is true for multiplication. Not all operations are commutative. For example, subtraction is not commutative: x− y 6= y − x except when x = y. Composition of permutations is not commutative. In general, π ◦ σ 6= σ ◦ π (but they can be equal in some special cases). Example 29. Given permutations π and σ in Sn, we can always find a permutation α such that π ◦α = σ: π ◦ α = σ π−1 ◦ (π ◦ α) = π−1 ◦ σ (π−1 ◦ π) ◦ α = π−1 ◦ σ ι ◦ α = π−1 ◦ σ α = π−1 ◦ σ It’s easy to check that this is correct: If we take π ◦ α and replace α by π−1 ◦ σ, we get: π ◦ α = π ◦ (π−1 ◦ σ) = (π ◦ π−1) ◦ σ = ι ◦ σ = σ But this means that to find α we need to know π−1. We will see that there are at least two simple ways to calculate π−1 when we are given π. 4.1 Computing the Inverse of a Permutation Suppose we have a permutation π and we need to compute π−1. We could do it from the standard matrix representation. Example 30. Consider π = [ 1 2 3 4 5 6 7 4 1 5 2 7 3 6 ] . To compute π−1, we can see that π(1) = 4, so we know that π−1(4) = 1. Similarly, we see that π(4) = 2, so we know that π−1(2) = 4, and so on. Then, we obtain π−1 = [ 1 2 3 4 5 6 7 2 4 6 1 3 7 5 ] . But with the permutation expressed in cycle notation, computing π−1 is simpler: we just reverse each cycle. The cycle notation of π is (1, 4, 2)(3, 5, 7, 6), so π−1 is simply (2, 4, 1)(6, 7, 5, 3). CISC 203: Discrete Mathematics for Computing II Module 6, Fall 2021 Page 10 Note that reversing a cycle is very different from rotating a cycle: if we consider the (a, b, c, d), the cycle (c, d, a, b) is equivalent, but the cycle (d, c, b, a) is the inverse. It is a common practice to start each cycle with the lowest number within the cycle, and to order the cycles so that the initial values are in ascending order. So, we can rewrite π−1 in this example as (1, 2, 4)(3, 6, 7, 5). 4.2 Transpositions Definition 31 (Transposition). A permutation τ ∈ Sn is called a transposition, provided • there exist i, j ∈ {1, 2, . . . , n} with i 6= j so that τ(i) = j and τ(j) = i, and • for all k ∈ {1, 2, . . . , n) with k 6= i and k 6= j, we have τ(k) = k. Trapositions exchange one pair of elements, and map each of the remaining elements to themselves. We have already encountered a transposition in Example 27. We now give two examples that show how to write any permutation as a composition of transpositions. Observe that there is a nice trick for converting a cycle into a composition of transpositions. Example 32. Let π = (1, 2, 3, 4, 5). We write π as the composition of transpositions as (1, 2, 3, 4, 5) = (1, 5) ◦ (1, 4) ◦ (1, 3) ◦ (1, 2). Example 33. Let π = (1, 4, 2)(3, 5, 7, 6). We write π as the composition of transpositions as (1, 4, 2)(3, 5, 7, 6) = (1, 2) ◦ (1, 4) ◦ (3, 6) ◦ (3, 7) ◦ (3, 5). Exercise Write the permutation π = [ 1 2 3 4 5 6 7 8 9 2 4 1 6 5 3 8 9 7 ] as (i) in cycle notation (i.e., as a composition of disjoint cycles), and (ii) as a composition of transpositions. Note that the decomposition of a permutation into transpositions is not unique, e.g., (1, 2, 3, 4) = (1, 4) ◦ (1, 3) ◦ (1, 2) = (1, 2) ◦ (2, 3) ◦ (3, 4) = (1, 2) ◦ (1, 4) ◦ (2, 3) ◦ (1, 4) ◦ (3, 4). However, note that each decomposition has an odd number of transpositions. More generally, we have the following theorem. Theorem 34. Let π ∈ Sn. Consider any two decompositions of π that we denote as π = τ1 ◦ τ2 ◦ · · · ◦ τa, and π = σ1 ◦ σ2 ◦ · · · ◦ σb. Then, a and b must have the same parity, i.e., they are both odd or both even. Proof. See the proof of Theorem 27.12 on p. 193 of the textbook. This theorem allows us to give the following definition, which we will revisit when we study groups. Definition 35 (Even and odd permutations). Let π be a permutation on a finite set. We call π even provided it can be written as the composition of an even number of transpositions. Otherwise, it can be written as the composition of an odd number of transpositions, in which case we call π odd. Functions Inverse functions The Pigeonhole Principle Composition Permutations Computing the Inverse of a Permutation Transpositions