SOLUTIONS MANUAL for Abstract Algebra Structures and Applications, 1e Stephen Lovet by digitaldownload87

1 | Set Theory 1.1 – Sets and Functions Exercise: 1 Section 1.1 Question: Let U = {n ∈ N | n ≤ 10} and consider the subsets A = {1, 3, 5, 7, 9}, B = {1, 2, 3, 4, 5}, and C = {1, 2, 5, 7, 8}. Calculate the following operations. a) A ∩ B b) (B ∪ C) − A c) (A ∩ B) ∩ (A ∩ C) ∩ (B ∩ C) d) ((A − B) − C) ∩ (A − (B − C)) Solution: We apply the definitions of set operations: a) A ∩ B = {1, 3, 5} b) (B ∪ C) − A = {1, 2, 3, 4, 5, 7, 8} − {1, 3, 5, 7, 9} = {2, 4, 8} c) A ∩ B∩A ∩ C∩B ∩ C = {1, 3, 5}∩{1, 5, 7}∩{1, 2, 5} = {2, 4, 6, 7, 8, 9, 10}∩{2, 3, 4, 6, 8, 9, 10}∩{4, 6, 8, 9, 10} d) ((A − B) − C) ∩ (A − (B − C)) = ({7, 9} − C) ∩ (A − {3, 4}) = {9} ∩ {1, 5, 7, 9} = {9} Exercise: 2 Section 1.1 Question: Let U = {a, b, c, d, e, f, g} and consider the subsets A = {a, b, d}, B = {b, c, e}, and C = {c, d, f }. Calculate the following operations. a) C ∩ (A ∪ B) b) (A ∪ C) − B c) (A ∪ B ∪ C) − (A ∩ B ∩ C) d) (A − B) ∪ (B − C) Solution: We apply the definitions of set operations: a) C ∩ (A ∪ B) = C ∩ {a, b, c, d, e} = {c, d} b) (A ∪ C) − B = {a, b, c, d, f } − B = {a, d, f } c) (A ∪ B ∪ C) − (A ∩ B ∩ C) = {a, b, c, d, e, f } − ∅ = {a, b, c, d, e, f } d) (A − B) ∪ (B − C) = {a, d} ∪ {b, e} = {a, b, d, e} Exercise: 3 Section 1.1 Question: As subsets of the reals, describe the differences between the sets {3, 5}, [3, 5] and (3, 5). Solution: The set {3, 5} contains the integers 3 and 5. The closed interval [3, 5] contains all real numbers between 3 and 5 including 3 and 5, while the open interval (3, 5) contains all real numbers between 3 and 5 not including 3 and 5. Exercise: 4 Section 1.1 Question: Prove that the following are true for all sets A and B. a) A ∩ B ⊆ A. b) A ⊆ A ∪ B. Solution: We use the definitions of subsets and the intersection and union of sets. a) Let x ∈ A ∩ B. Then x ∈ A and x ∈ B =⇒ x ∈ A, so A ∩ B ⊆ A. b) Let x ∈ A. We know that A ∪ B = {y | y ∈ A or y ∈ B}, so x ∈ A =⇒ x ∈ A ∪ B. Hence A ⊆ A ∪ B. Exercise: 5 Section 1.1 Question: Let A and B be subsets of a set S. a) Prove that A ⊆ B if and only if P(A) ⊆ P(B) b) Prove that P(A ∩ B) = P(A) ∩ P(B). c) Show that P(A ∪ B) = P(A) ∪ P(B) if and only if A ⊆ B or B ⊆ A. Solution: 1

CHAPTER 1. SET THEORY a) (=⇒): Suppose A ⊆ B. Then, ∀a ∈ A, a ∈ B. Since P(B) contains all the possible subsets of B, all the possible subsets of A must be in P(B) because A ⊆ B. Therefore, P(A) ⊆ P(B). (⇐=): Suppose P(A) ⊆ P(B). Then ∀{a} ∈ P(A), {a} ∈ P(B). Therefore, there must exist a subset C of P(B) that contains every {a} from P(A). The subset C leads to the conclusion that every a ∈ A must also be in B. Therefore, A ⊆ B. b) By definition, P(A ∩ B) = {{t1 , t2 , ..., tn } | ti ∈ A, ti ∈ B}. This implies {ti } ∈ P(A) and {ti } ∈ P(B). Therefore, by definition of intersection, P(A ∩ B) = P(A) ∩ P(B). c) (=⇒): Suppose there are two sets A and B such that neither A ⊆ B nor B ⊆ A. Let a ∈ A − B and b ∈ B − A. Then the set {a, b} is in P(A ∪ B) but not in P(A) or in P(B). Therefore by the contrapositive, P(A ∪ B) = P(A) ∪ P(B) if A ⊆ B or B ⊆ A. (⇐=): Suppose A ⊆ B. Then, A ∪ B = B so P(A ∪ B) = P(B). Now suppose B ⊆ A. Then A ∪ B = A so P(A ∪ B) = P(A). Either way, P(A ∪ B) = P(A) ∪ P(B).

Exercise: 6 Section 1.1 Question: Give the list description of P({1, 2, 3, 4}). Solution: Using the definition of a power set, P({1, 2, 3, 4}) ={∅, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}, {1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}}.

Exercise: 7 Section 1.1 Question: Give the list description of {{a1 , a2 , . . . , ak } ∈ P({1, 2, 3, 4, 5}) a1 + a2 + · · · + ak = 8}. Solution: We need to find all the subsets of {1, 2, 3, 4, 5} whose elements add to a total of 8. Recall that no subset has repeated elements so {4, 4, } does not make sense. The set is {{1, 2, 5}, {1, 3, 4}, {3, 5}} .

Exercise: 8 Section 1.1 Question: Let A, B, and C be subsets of a set S. a) Prove that (A − B) − C = (A − C) − (B − C). b) Find and prove a similar formula for A − (B − C). Solution: S

a) In the first Venn diagram, the lighter shade represents (A − B), and the darker shade, which overlaps some of (A − B), represents (A − B) − C. In the second Venn diagram, the lighter shade represents (A − C), while the darker shade represents (A − C) − (B − C). We observe from the diagrams that the darker regions are equal.

1.1. SETS AND FUNCTIONS

3 S

b) In the Venn diagram above, the lighter shade represents B −C, and the darker shade represents A−(B −C). In the second diagram, the lighter region represents A − B, and the darker region represents A − C, which overlaps some of A − B. Thus, (A − B) ∪ (A − C) = A − (B − C). Exercise: 9 Section 1.1 Question: Let A, B, and C be subsets of a set S. a) Prove that A4B = ∅ if and only if A = B. b) Prove that A ∩ (B4C) = (A ∩ B)4(A ∩ C). Solution: Let A, B, and C be subsets of a set S. a) Suppose that A4B = ∅. Then by definition of the symmetric difference (A − B) ∪ (B − A) = ∅. If the union of two sets is the empty set, then each of the two sets must be empty. Hence we deduce that A − B = ∅ and B − A = ∅. Now for and two sets U and T , the identity U − T = ∅ is equivalent to U ⊆ T . Hence we deduce that A ⊆ B and B ⊆ A. Consequently, A = B. The argument of the opposite direction is identical. Suppose that A = B. Then A ⊆ B and B ⊆ A. Thus A − B = ∅ and B − A = ∅. We deduce that A4B = (A − B) ∪ (B − A) = ∅. b) There are a variety of ways to prove the identity A ∩ (B4C) = (A ∩ B)4(A ∩ C). We could use a well designed Venn diagram. We could also use a membership table which lists all possibilities of an element whether it is in or not in one √ of the given three sets. Here is a membership table for both side of the equality. In this table, we put an in a column to indicate membership and nothing to indicate non-membership. √ Hence if there is a in the A and C column and nothing in the B column, that refers to the situations of an element in A, not in B and in C. A √ √ √ √

B √ √

C √ √

√ √

(B4C)

A ∩ (B4C)

√ √

(A ∩ B) √ √

(A ∩ C) √ √

(A ∩ B)4(A ∩ C) √ √

√ √

Since the A ∩ (B4C) and column and the (A ∩ B)4(A ∩ C) of this membership table are the same, then the sets are equal. Exercise: 10 Section 1.1 Question: Let S be a set and let {Ai }i∈I be a collection of subsets of S. Prove the following. [ \ a) Ai . Ai = i∈I

\ i∈I

i∈I

Ai =

[

Ai .

i∈I

Solution: Let S be a set and let {Ai }i∈I be a collection of subsets of S.

CHAPTER 1. SET THEORY a) We will prove the equation by proving set inclusion in both directions. [ [ (=⇒) Let a ∈ Ai . Then a ∈ / Ai or a ∈ / Ai for every i ∈ I. And this implies that a ∈ Ai for every i∈I

i∈I

i ∈ I. So then a ∈

[

Ai . And so

i∈I

(⇐=) Let a ∈

Ai ⊆

i∈I

Ai .

i∈I

Ai . Then a ∈ Ai for every i ∈ I. Which implies that a ∈ / Ai for eversy i ∈ I. And so

i∈I

a∈ /

[ i∈I

And so

[

Ai . Which implies a ∈

Ai . So

i∈I

[

Ai =

i∈I

Ai ⊆

i∈I

[

Ai .

i∈I

Ai .

i∈I

b) We will prove this equation by proving set inclusion in both directions. \ \ (=⇒) Let a ∈ Ai . So a ∈ / Ai . So a ∈ / Ai for at least one i ∈ I. So a ∈ Ai for at least one i ∈ I. So i∈I

a∈

[

i∈I

Ai . Which implies that

i∈I

Ai ⊆

i∈I

(⇐=) Let a ∈

[

Ai .

i∈I

Ai . Then a ∈ Ai for at least one i ∈ I. This implies that a ∈ / Ai for at least one i ∈ I.

i∈I

It follows that a ∈ /

Ai . Which implies that a ∈

i∈I

\ i∈I

Ai =

[

Ai . So

[

Ai ⊆

i∈I

Ai .

i∈I

Ai .

i∈I

Exercise: 11 Section 1.1 Question: Let P be the parabola in the plane whose equation is y = x2S . Let {Aq }q∈P be the collection of subsets of R2 where Aq is the tangent line to P at q. Determine with proof q∈P Aq . Solution: Sketching a picture of the standard parabola, we see that all the tangent lines are in some sense beneath the parabola. Also, taking the (infinite, uncountable) union of all the tangent lines to the parabola, we might guess that we would get all points (a, b) in the plane such that b ≤ a2 . We need to prove this hypothesis. Label the coordinates of a point q ∈ P as q = (x0 , x20 ). From calculus, the tangent line to P at q has the equation y = x20 + 2x0 (x − x0 ) =⇒ y = 2x0 x − x20 . Now suppose that some point (a, b) in the plane is on a tangent line. Then, for some x0 , we have b = 2x0 a − x20 . Since a, b are given and x0 is unknown, this is an equation in x0 . The quadratic formula gives for x0 x0 =

2a ±

√

p 4a2 − 4b = a ± a2 − b. 2

In particular, we note that there exists an x0 if and only if a2 − b ≥ 0, confirming the hypothesis that b ≤ a2 .

Exercise: 12 Section 1.1 3 3 Question: Let {AT k }k∈N be the collection of subsets of R such that Ak = {(x, y, z) ∈ R | z ≥ ky}. Determine S both k∈N Ak and k∈N Ak . Solution: Each subset Ak represents all points greater than the plane that is bound on the line z = ky. In the diagram below, imagine the x-axis is coming out of the page, and let k1 , k2 , and k3 represent the bounds of the subsets A1 , A2 , and A3 respectively. We note that the larger k gets, S the more steep the plane becomes. However, the condition does not hold true for z < 0 when y is 0. Therefore, k∈N Ak = {(x, y, z) | z ≥ y}∪{(x, y, z) | x < 0}, T and k∈N Ak = {(x, y, z) | z ≥ y} ∩ {(x, y, z) | x ≤ 0}.

1.1. SETS AND FUNCTIONS

5 z

k3 k2

Exercise: 13 Section 1.1 Question: In geometry of the plane, a subset S of the plane is called convex if for all p, q ∈ S the line segment pq connecting p and q is a subset of S. Prove that the intersection of two convex sets is a convex set. Solution: Let S and R both be convex sets. Consider S ∩ R. Case 1: If S ∩ R is empty, than it is trivially a convex set. Case 2: If it is non-empty, for any p, q ∈ S ∩ R, consider the line segment pq. Since p, q ∈ S and S is convex, we know that pq ⊆ S. By the same reasoning, since p, q ∈ R and R is convex, this implies that pq ⊆ R. Since pq is a subset of both S and R, we have pq ⊆ S ∩ R. So S ∩ R is convex. This proves that S ∩ R is convex. Exercise: 14 Section 1.1 Question: Inclusion-Exclusion Principle. Let A, B, and C be finite subsets of a set S. a) Prove that |A ∪ B| = |A| + |B| − |A ∩ B|. b) (*) Prove that |A ∪ B ∪ C| = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Solution: a) Let |A| = n and |B| = m. Now A ∪ B is all of the elements that are either in A or B. If we say that |A ∪ B| = |A| + |B| = n + m, for any element c that exists in both A and B, or equivalently A ∩ B, we account for that element twice, once in |A| and the second in |B|. So we must subtract 1 for the |A ∩ B| elements we account for twice. So |A ∪ B| = |A| + |B| − 1(|A ∩ B|) = |A| + |B| − |A ∩ B|. b) Let D = A∪B and consider |D∪C|. By applying the first result of this exercise, |D∪C| = |D|+|C|−|D∩C|. And if we put A ∪ B back in for D and apply the first result again we get |A ∪ B| + |C| − |(A ∪ B) ∩ C| = |A| + |B| − |A ∩ B| + |C| − |(A ∪ B) ∩ C|. Now we will consider |(A ∪ B) ∩ C|. (A ∪ B) ∩ C contains all the elements that are in (A or B) and C. If A and C have n elements in common, or equivalently |A ∩ C| = n, and likewise |B ∩C| = m, then |(A∪B)∩C| is certainly at most m+n. However, we should not double count whatever elements are in both A∩C and B ∩C, or A∩B ∩C. So we must subtract out that amount, and we arrive at |(A ∪ B) ∩ C| = |A ∩ C| + |B ∩ C| − |A ∩ B ∩ C|. Plugging this result back into our original equation we get |A| + |B| − |A ∩ B| + |C| − |(A ∪ B) ∩ C| = |A| + |B| + |C| − |A ∩ B| − (|A ∩ C| + |B ∩ C| − |A ∩ B ∩ C|) = |A| + |B| + |C| − |A ∩ B| − |A ∩ C| − |B ∩ C| + |A ∩ B ∩ C|. Exercise: 15 Section 1.1 Question: Let U be a set and A, B ⊆ U . a) Show by any means that A ∩ B = A ∪ B. b) Show by any means that A ∪ B = A ∩ B. Solution:

CHAPTER 1. SET THEORY a) Observe the Venn diagrams below: U

In the above diagrams, the left diagram represents A ∩ B, and the right diagram represents A ∪ B. In the A ∪ B diagram, represents A, represents B, and represents where they overlap. A ∪ B is represented by the union of these shaded regions. We can observe the shaded regions from both diagrams describes the same set, thus A ∩ B = A ∪ B. b) Observe the Venn diagrams below: U

In the above diagrams, the left diagram represents A ∪ B, and the right diagram represents A ∩ B. In the A ∩ B diagram, represents A, represents B, and represents A ∩ B. Notice, the shaded region describes the same set that is shaded in the A ∪ B diagram, hence A ∪ B = A ∩ B.

Exercise: 16 Section 1.1 Question: (*) Let n be a positive integer. Describe an algorithm (a finite list of well-defined instructions to accomplish a task) to list all the subsets of {1, 2, 3, . . . , n}. Solution: Let S = {{∅}} and k = 1. For every set in S, add a new set to S representing the union of {k} and the set in S. Once this process is completed union {k} to S. Increase k by 1. Repeat this process until k = n. In other words, while k < n, S = S ∪ {s | t ∪ {k}, ∀t ∈ S} ∪ {k}.

Exercise: 17 Section 1.1 Question: For each of these real-valued functions determine the largest possible domain D as a subset of R and then prove whether f : D → R is an injection, surjection, both, or neither. a) f (x) = −3x + 4 b) f (x) = −3x2 + 7 c) f (x) = (x + 1)/(x + 2) d) f (x) = x5 + 1 Solution: We decide if the function is an injection, surjection, both, or neither. a) Let f (x) = −3x + 4. This function can be defined over the whole domain R. Suppose that f (x1 ) = f (x2 ). Then −3x1 + 4 = −3x2 + 4. This implies that −3x1 = −3x2 so x1 = x2 . This shows that f (x) is injective. To prove surjectivity, we attempt to solve for x in the expression y = f (x) for an arbitrary y. We get x = 4−y 3 . Since there is a solution in x for any y, then f is surjective. (f is bijective.) b) Let f (x) = −3x2 + 7. The largest possible domain of definition is R. Note that f (−1) = 4 = f (1). This shows that f is not injective. To p test for surjectivity, we attempt to solve for x in y = f (x). The equation y = −3x2 + 7 leads to x = ± (7 − y)/3. However, if y > 7 there is no solution for x. Hence, since the codomain of f is R, f is not surjective. (f is neither.) c) Let f (x) = (x+1)/(x+2). This function is defined on R−{−2}. This is the domain. To test for injectivity,

1.1. SETS AND FUNCTIONS

suppose that f (x1 ) = f (x2 ). Then we have x1 + 1 x1 + 1 = =⇒ (x1 + 1)(x2 + 2) = (x1 + 2)(x2 + 1) x1 + 2 x1 + 2 =⇒ x1 x2 + 2x1 + x2 + 2 = x1 x2 + x1 + 2x2 + 2 =⇒ 2x1 + x2 = x1 + 2x2 =⇒ x1 = x2 . This shows that f is injective. To test for surjectivity, we attempt to solve y = f (x) for x given arbitrary y. We have 1 − 2y x+1 =⇒ yx + 2y = x + 1 =⇒ xy − x = 1 − 2y =⇒ x = . y= x+2 y−1 We see that there is no solution for x if y = 1. Hence f (x) is not surjective. d) Consider the function f (x) = x5 + 1. This is defined over all R so this is the largest possible domain in R. To check for injectivity, consider the equality f (x1 ) = f (x2 ). This gives x51 + 1 = x52 + 1 =⇒ x51 − x52 = 0 =⇒ (x1 − x2 )(x41 + x31 x2 + x21 x22 + x1 x32 + x42 ) = 0. Obviously the equation holds if x1 = x2 . Now we look for solutions of the second term. Note that if x2 = 0, then the quartic equation implies that x1 = 0. But then x1 = x2 , which we already know to be a possibility. Assuming that x1 6= x2 , after division by x42 the quartic term implies

x1 x2

+1=0

A graph of the function g(x) = x4 + x3 + x2 + x + 1 shows that g(x) has no solutions. Thus, the only solution to √ f (x1 ) = f (x2 ) is x1 = x2 . Thus f is injective. For surjectivity, we see that y = f (x) implies that x = 5 y − 1, which is defined for all y. Hence f is surjective. (f is bijective.) Exercise: 18 Section 1.1 Question: Given an explicit example of a function f : Z → Z that is a) bijective; b) surjective but not injective; c) injective but not surjective; d) neither injective nor surjective. Solution: Recall that bxc takes x and returns the nearest integer less than or equal to x. The solutions presented here are not the only options! a) f (x) = −x. b) f (x) = bx/2c. c) f (x) = x ∗ 2. d) f (x) = x2 . Exercise: 19 Section 1.1 Question: Given an explicit example of a function f : N → N that is a) bijective; b) surjective but not injective; c) injective but not surjective; d) neither injective nor surjective. Solution: Recall that bxc takes x and returns the nearest integer less than or equal to x. The answers presented here are not the only options! a) f (x) = x. b) f (x) = bx/2c. c) f (x) = 2 ∗ x.

CHAPTER 1. SET THEORY d) f (x) = 2 ∗ (bx/2c).

Exercise: 20 Section 1.1 Question: Let f : A → B and g : B → C be functions. Prove that if f and g are bijective, then g ◦ f is bijective and (g ◦ f )−1 = f −1 ◦ g −1 . Solution: Assume g ◦ f is not injective. Then there would exist a1 , a2 ∈ A such that a1 6= a2 and g ◦ f (a1 ) = g ◦ f (a2 ). Let b1 = f (a1 ) and b2 = f (a2 ). We know that b1 6= b2 because f is bijective. Using substitution, we notice that g(b1 ) = g(b2 ), but b1 6= b2 . This creates a contradiction since g is bijective. Thus, g ◦ f is injective. Now assume that g ◦ f is not surjective. Then there would exist at least one c ∈ C such that ∀a ∈ A, g(f (a)) 6= c. By substituting we observe ∀b ∈ B, g(b) 6= c. However, since g is bijective, this creates a contradiction. Therefore g ◦ f is surjective. Hence, g ◦ f is bijective. Let f (a) = b and g(b) = c. Then g(f (a)) = c so (g ◦ f )−1 (c) = a. Therefore, (g ◦ f )−1 (c) = a = f −1 (b) = f −1 (g −1 (c)) so (g ◦ f )−1 = f −1 ◦ g −1 . Exercise: 21 Section 1.1 Question: Suppose that f and g are functions and that f ◦ g is injective. a) Prove that g is injective. b) Does it also follow that f is injective? Justify your answer (with a proof or counter-example). Solution: a) For the sake of contradiction, we assume g is not injective. Then for some a, b that exist in the domain of g, g(a) = g(b). However, then f (g(a)) = f (g(b)) as well. This contradicts the injectivity of f ◦ g. Therefore g must be injective. b) No it does not. Consider the following functions f, g : Z −→ Z: ( 2x if x ≥ 0 g(x) = 2|x| + 1 if x < 0. f (x) = x2 . Now, g sends non-negative numbers to a unique, non-negative, even number and negative numbers to a unique, positive, odd number. However, f is injective on non-negative numbers so that f ◦ g is injective, but is not injective on all of Z. (Note: What is necessary is that f be injective on the range of g (in our case, the nonnegative numbers) but not necessarily the codomain of g(in our case, all of Z)) Exercise: 22 Section 1.1 Question: Suppose that f and g are functions and that f ◦ g is surjective. a) Prove that f is surjective. b) Does it also follow that g is surjective? Justify your answer (with a proof or counter-example). Solution: a) Consider any a in the codomain of f . Since a is also in the codomain of f ◦ g and f ◦ g is a surjective function, there must exist some b in the domain of f ◦ g so that a = (f ◦ g)(b). Set c = g(b). Then (f ◦ g)(b) = f (g(b)) = f (c) = a. So every element of the codomain is hit by f and f is surjective. b) No it does not. Consider the functions f, g : N −→ N where f (x) = bx/2c and g(x) = 2x. Then for any y ∈ N, (f ◦ g)(y) = f (g(y)) = f (2 ∗ y) = b(2 ∗ y)/2c = byc = y. So f ◦ g is surjective, but g is certainly not since no odd, positive numbers will be hit. Exercise: 23 Section 1.1 Question: Restate the definition of (a) injective and (b) surjective as applied to a function f : A → B in terms of properties of the sets f −1 ({b}). Solution:

1.1. SETS AND FUNCTIONS

a) For injectivity, |f −1 ({b})| ≤ 1. b) For surjectivity, |f −1 {b})| ≥ 1. Exercise: 24 Section 1.1 Question: For the following functions f , find the pre-image (or fiber) f −1 (T ) of the given set T in the codomain. √ a) f : R → R with f (x) = sin x and T = { 3/2}. b) f : R → R with g(x) = x2 − 2 and T = [1, 2]. c) f : R → R with h(x) = x3 − 2x and T = [−1, 0]. Solution: Note that the pre-image of f −1 (T ) represents all of the domain values that map to the elements of T. √ a) f −1 (T ) = sin−1 ( 23 ) = { π3 , 2π 3 } b) f −1 (T ) = g −1 ([1, 2]) √ x2 − 2 = 1 ⇒ x = ± 3 x2 − 2 = 2 ⇒ x = ±2 f (x) x2 − 2

2 1

x −2

−1

−1 −2 √ √ Therefore, the pre-image of g −1 ([1, 2]) is {[−2, − 3], [ 3, 2]}. c) f −1 (T ) = h−1 ([−1, 0]) Notice that 1 is a zero of the polynomial x3 − 2x + 1. This allows us to find the x-values that satisfy x3 − 2x = −1. x3 − 2x + 1 = (x − 1)(x2 + x − 1) √ −1 ± 5 x = 1, 2 √ x3 − 2x = 0 ⇒ x = 0, ± 2 f (x) x3 − 2x

2 1 −2

−1

−1 −2 √ √ √ √ Therefore, the pre-image of h−1 ([−1, 0]) is {[ −1−2 5 , − 2], [0, −1+2 5 ], [1, 2]}.

CHAPTER 1. SET THEORY

Exercise: 25 Section 1.1 Question: Let f : A −→ B be a function from the set A to the set B. Let S and T be subsets of the domain A. 1. Show that f (S ∪ T ) = f (S) ∪ f (T ). 2. Show that f (S ∩ T ) ⊆ f (S) ∩ f (T ). 3. Find an example of a function f : A → B and subsets S and T in A such that f (S ∩ T ) 6= f (S) ∩ f (T ). Solution: a) We prove first that f (S ∪ T ) ⊆ f (S) ∪ f (T ). Suppose that y ∈ f (S ∪ T ). Then there exists x ∈ S ∪ T such that f (x) = y. We have x ∈ S or x ∈ T , so y = f (x) ∈ f (S) or y = f (x) ∈ f (T ). Hence y ∈ f (S) ∪ f (T ), so we deduce that f (S ∪ T ) ⊆ f (S) ∪ f (T ). Conversely, suppose that y ∈ f (S) ∪ f (T ). This y ∈ f (S) or y ∈ f (T ). We deduce that there exists x ∈ S with f (x) = y or there exists x0 ∈ T with f (x0 ) = y. Thus, there exists an x ∈ S ∪ T such that x = f (y) and we deduce that f (S) ∪ f (T ) ⊆ f (S ∪ T ). With these two set inclusions, we conclude that f (S ∪ T ) = f (S) ∪ f (T ). b) Let y ∈ f (S ∩ T ). By definition, there exists x ∈ S ∩ T such that y = f (x). Then x ∈ S and x ∈ T so y = f (x) ∈ f (S) and y = f (x) ∈ f (T ). Thus y ∈ f (S) ∩ f (T ). We conclude that f (S ∩ T ) ⊆ f (S) ∩ f (T ). c) Consider the function f : R → R with f (x) = x2 . Setting S = [−2, −1] and T = [1, 2], we find that f (S ∩ T ) = f (∅) = ∅ f (S) ∩ f (T ) = [1, 4] ∩ [1, 4] = [1, 4] Obviously, these are not equal sets. Note that if we attempted to prove that f (S) ∩ f (T ) ⊆ f (S ∩ T ), the reasoning would go as follows. Let y ∈ f (S) ∩ f (T ). Then y ∈ f (S) and y ∈ f (T ). Then there exists x ∈ S with f (x) = y and there exists x0 ∈ T with f (x0 ) = y. However, since x does not have to be equal to x0 , there does not have to exist an element x00 ∈ S ∩ T such that f (x00 ) = y. Exercise: 26 Section 1.1 Question: Let f : A −→ B be a function from the set A to the set B. Let V and W be subsets of the codomain B. Show the following. a) f −1 (V ∪ W ) = f −1 (V ) ∪ f −1 (W ). b) f −1 (V ∩ W ) = f −1 (V ) ∩ f −1 (W ). Solution: a) We will prove the equality by showing set inclusion in both directions. (=⇒) Consider any element a ∈ f −1 (V ∪ W ). Then f (a) ∈ V ∪ W so that f (a) exists in V or W . Then a ∈ f −1 (V ) or f −1 (W ). Which implies a ∈ f −1 (V ) ∪ f −1 (W ). This shows that f −1 (V ∪ W ) ⊆ f −1 (V ) ∪ f −1 (W ). (⇐=) Consider any element b ∈ f −1 (V ) ∪ f −1 (W ). So b exists in at least one of f −1 (V ) or f −1 (W ). Then f (b) exists in V or W . Which implies f (b) ∈ V ∪ W . So then b ∈ f −1 (V ∪ W ). This shows that f −1 (V ) ∪ f −1 (W ) ⊆ f −1 (V ∪ W ). This proves the equality f −1 (V ∪ W ) = f −1 (V ) ∪ f −1 (W ). b) We will prove the equality by showing set inclusion in both directions. (=⇒) Consider any element a ∈ f −1 (V ∩ W ). So f (a) exists in both V and W . Then a exists in both f −1 (V ) and f −1 (W ). Which implies that a ∈ f −1 (V ) ∩ f −1 (W ). This shows that f −1 (V ∩ W ) ⊆ f −1 (V ) ∩ f −1 (W ). (⇐=) Consider any element a ∈ f −1 (V ) ∩ f −1 (W ). So a exists in both f −1 (V ) and f −1 (W ). Then f (a) exists in both V and W . Then, by definition, f (a) ∈ V ∩ W . Which implies that a ∈ f −1 (V ∩ W ). This shows that f −1 (V ) ∩ f −1 (W ) ⊆ f −1 (V ∩ W ). This proves the equality f −1 (V ∩ W ) = f −1 (V ) ∩ f −1 (W ).

1.1. SETS AND FUNCTIONS

Exercise: 27 Section 1.1 Question: Let S and T be finite sets with |S| = |T |. Prove that a function f : S → T is injective if and only if it is surjective. Solution: (=⇒): Suppose f : S → T is injective. Then ∀s1 , s2 ∈ S such that f (s1 ) = f (s2 ) implies s1 = s2 . Therefore, every s ∈ S maps to a unique t ∈ T . Since |S| = |T |, there does not exist t ∈ T such that t is not associated with a unique s ∈ S. Thus f is surjective. (⇐=): Suppose f : S → T is surjective. This means that there are at least |T | elements in S that map to T . Assume there exists f (s1 ) = f (s2 ) such that s1 = s2 . Then f implies that |S| elements are mapped to at most |S| − 1 elements in T . Thus there exists at least one t1 ∈ T where there does not exist s ∈ S such that f (s) = t1 . This creates a contradiction because f is surjective. Therefore f is injective.

Exercise: 28 Section 1.1 Question: Let S be a set. For each subset A ⊆ S we define the characteristic function of A as the function χA : S → {0, 1} such that ( 1 if s ∈ A χA (s) = 0 if s ∈ / A. Prove the following. a) The association A 7→ χA is a bijection between P(S) and the set of functions from S to {0, 1}. b) χA∩B (s) = χA (s) · χB (s) for all s ∈ S. c) χA∪B (s) = χA (s) + χB (s) − χA (s) · χB (s) for all s ∈ S. d) χA (s) = 1 − χA (s) for all s ∈ S. e) χA−B (s) = χA (s)(1 − χB (s)) for all s ∈ S. Solution: a) First, notice that each distinct characteristic function represents a unique subset of S. From proposition 1.1.11 we know that there are 2n unique characteristic functions of S. We can write these subsets as n-tuples where each entry contains either a 1 or a 0. We can also picture any function from S to {0, 1} as a n-tuple (f (s1 ), f (s2 ), ..., f (sn )) where |S| = n. Note that each n-tuple will represent a distinct function from S to {0, 1}. In comparing n-tuples, we observe that every function from S to {0, 1} represents a unique characteristic function of S implying that the association is injective. Since each entry has two options, and there are n entries, there are 2n distinct functions from S to {0, 1}. Thus the cardinalities of the functions of S to {0, 1} and P(S) are equal. Using the result in exercise 1.1.27, the association must be surjective as well. Hence, the association from A 7→ χA is a bijection between P(S) and the set of functions from S to {0, 1}. b) Suppose s ∈ A ∩ B. Then, s ∈ A and s ∈ B. This implies χA (s) = 1 and χB (s) = 1. From here we deduce that χA∩B (s) = 1 = χA (s) · χB (s). Now suppose s ∈ / A ∩ B. Then s 6∈ A or s 6∈ B, so χA (s) = 0 or χB (s) = 0. Either way, χA∩B (s) = 0 = χA (s) · χB (s). Therefore, χA∩B (s) = χA (s) · χB (s) for all s ∈ S. c) Suppose s ∈ A ∪ B. Then s ∈ A or s ∈ B. If s ∈ A ∩ B or if s ∈ B ∩ A then we deduce that χA (s) + χB (s) works for both cases. If s ∈ A ∩ B, then we need to account for counting an element twice so we subtract χA∩B (s) which we know to be χA (s) · χB (s) from above. Hence χA∪B (s) = χA (s) + χB (s) − χA (s) · χB (s) for all s ∈ S. d) Suppose s ∈ A. Then s 6∈ A, so χA (s) = 0 and χA (s) = 1. If s ∈ A then s 6∈ A and we get the opposite result. Notice to reverse the results of χA (s) we subtract it from 1. Therefore χA (s) = 1 − χA (s). e) Note that A − B = A ∩ B and χB (s) = 1 − χB (s). Thus χA−B (s) = χA (s)(1 − χB (s)) for all s ∈ S.

Exercise: 29 Section 1.1 Question: Provide all the details in the proof of Proposition 1.1.23. Solution: We start with f (n) = 2n + 21 where f : Z → N. Plugging in some points such as −2, −1, 0, 1, 2

CHAPTER 1. SET THEORY

we observe the following: f (−2) = 3 f (−1) = 1 f (0) = 0 f (1) = 2 f (2) = 4

Noticing the negative integers point to odd natural numbers and the positive integers point to even natural numbers, we can describe any integer n in terms of any natural number m by using the definition of even and odd numbers ( m if m is even n = 2 m+1 − 2 if m is odd. Since every integer n is represented by a different natural number m we can quickly deduce that the association is by definition. Assume that there are two integers a and b such that a 6= b but f (a) = f (b). Then, surjective 2a + 21 = 2b + 12 which implies that 2a + 12 = 2b + 12 ⇒ a = b. This creates a contradiction, hence the association is injective as well. Thus since there exists a bijection between Z and N. Therefore, Z is countable.

Exercise: 30 Section 1.1 Question: Let A, B, and C be sets. Prove that if |A| ≤ |B| and |B| ≤ |C|, then |A| ≤ |C|. Solution: Let A, B, and C be sets such that |A| ≤ |B| and |B| ≤ |C|. Also let a be an any element in A, f : A → B, and g : B → C. There exists a unique element in B such that f (a) = b, ∀a ∈ A. Also, there is a unique c ∈ C such that g(b) = c, ∀b ∈ B. By using substitution and composition we find g(f (a)) = c, ∀a ∈ A. This establishes a injective function f : A → C therefore |A| ≤ |C|. Exercise: 31 Section 1.1 Question: Let A and B be finite sets. Prove that the number of distinct functions A → B is |B||A| . Solution: Let the n-tuple, (f (a1 ), f (a2 ), f (a3 ), ..., f (an )), represent a distinct function f : A → B where |A| = n. Each entry in the n-tuple can be mapped to a different element in B resulting in m possibilities where |B| = m. Since every entry has m options and there are n entries, the total number of possible distinct n-tuples is m1 × m2 × m3 × ... × mn = mn . By substituting we observe that the number of distinct functions is equal to |B||A| .

1.2 – The Cartesian Product; Operations; Relations Exercise: 1 Section 1.2 Question: Let A, B, C be sets. Explain why A × B × C is not the same set as A × (B × C). Solution: The set A × B × C contains 3-tuples with the components (a, b, c), however, the set A × (B × C) contains pairs with the components (a, (b, c)). Exercise: 2 Section 1.2 Question: Let A, B, C, D be sets. Explain why A × (B × C) × D is not the same set as (A × B) × (C × D). Solution: The elements of the set A × (B × C) × D contains 3-tuples with three components, (a, (b, c), d), whereas the elements of the set (A × B) × (C × D) contains pairs with two components, ((a, b), (c, d)). Exercise: 3 Section 1.2 Question: Let A = {1, 2, 3, 4} and B = {a, b}. Write out as a list a) A × B; b) A × A; c) B × B × A. Solution: a) {(1, a), (2, a), (3, a), (4, a), (1, b), (2, b), (3, b), (4, b)} b) {(1, 1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)}

1.2. THE CARTESIAN PRODUCT; OPERATIONS; RELATIONS

c) {(a, a, 1), (a, a, 2), (a, a, 3), (a, a, 4), (a, b, 1), (a, b, 2), (a, b, 3), (a, b, 4), (b, a, 1), (b, a, 2), (b, a, 3), (b, a, 4), (b, b, 1), (b, b, 2), (b, b, 3), (b, b, 4)} Exercise: 4 Section 1.2 Question: Write in list form {1, 3} × {2, 4} × {3, 5}. Solution: {(1, 2, 3), (1, 2, 5), (1, 4, 3), (1, 4, 5), (3, 2, 3), (3, 2, 5), (3, 4, 3), (3, 4, 5)} Exercise: 5 Section 1.2 Question: Write in list form {1} × {1, 2} × {1, 2, 3}. Solution: The elements in {1} × {1, 2} × {1, 2, 3} are triples. The Cartesian product set is {(1, 1, 1), (1, 1, 2), (1, 1, 3), (1, 2, 1), (1, 2, 2), (1, 2, 3)}.

Exercise: 6 Section 1.2 Question: Justify the statement that A × ∅ = ∅ for all sets A. Solution: By definition of the Cartesian product, A × ∅ = {(a, b)| a ∈ A and b ∈ ∅}. Since ∅ has no elements, A × ∅ has no elements and therefore is equal to ∅. Exercise: 7 Section 1.2 Question: (*) This exercise offers a proof that if A and B are countable sets, then A × B is countable. a) Find a bijection between N∗ and N∗ × N∗ . [Hint: Count through the pairs (x, y) ∈ N∗ × N∗ by successively going through the lines of the form x + y = n for n = 2, 3, 4, . . ..] b) Use the bijection in the previous part to prove that if A and B are countable sets, then A × B is countable. Solution: a) Note that N∗ × N∗ represents all the pairs of natural numbers which can be represented on a graph in the first quadrant. Using the hint, we establish a series of lines following the pattern x + y = n + 1 where n = 1, 2, 3, .... Observe the intersections of the first couple of lines: n = 1 ⇒ (1, 1) n = 2 ⇒ (1, 2), (2, 1) n = 3 ⇒ (1, 3), (2, 2), (3, 1)

As the pattern continues, we quickly observe that as n increases, every element in N∗ × N∗ is mapped to once and only once. This establishes a bijection between N∗ × N∗ and N∗ . b) Suppose A and B are countable sets. Then both A and B have a bijection with N∗ . It follows that there exists a bijection between A × B and N∗ × N∗ . Since we have already established a bijection between N∗ × N∗ and N∗ , there exists a bijection between A × B and N∗ . Therefore, A × B is countable. Exercise: 8 Section 1.2 Question: The operation ∗ on vectors of Rn defined by ~u ∗ ~v = proj~u ~v , i.e., projection of ~v onto ~u. Solution: Associative: Find any counter-example. Let ~a, ~b, and ~c be vectors in R2 such that ~a =< 1, 1 >, ~b =< 2, 1 >, a. Therefore, ∗ is not associative. and ~c =< 3, 1 >. Then (~a ∗ ~b) ∗ ~c = 34 ~a and ~a ∗ (~b ∗ ~c) = 21 10 ~ Commutative: Find any counter-example. Using the same vectors above, observe that ~a ∗~b = 23 ~a and ~b∗~a = 35~b. Since ~a ∗ ~b 6= ~b ∗ ~a, ∗ is not commutative. Identity: Note that in order for ~a ∗~e = ~a, proj~a ~e = ~a which is only possible when ~e = ~a since proj~a ~a = ~a. Thus it is impossible to have a unique identity. Inverse: Since ∗ does not have an identity, it cannot be closed under inverses.

CHAPTER 1. SET THEORY

Idempotent: As shown earlier, proj~a ~a = ~a therefore, ∗ is idempotent.

Exercise: 9 Section 1.2 Question: For the operation ? on the open interval [0, 1) described by a ? b = a + b − ba + bc where bxc is the greatest integer less than or equal to x, determine whether it is associative, commutative, has an identity, has inverses or is idempotent. Solution: Associative: Let a, b, c ∈ [0, 1). Then (a ? b) ? c = (a + b − ba + bc) ? c = a + b − ba + bc + c − ba + b − ba + bc + cc since bx + nc = bxc + n for all x ∈ R and all n ∈ Z = a + b + c − ba + bc + ba + bc − ba + b + cc = a + b + c − ba + b + cc. Furthermore a ? (b ? c) = a ? (b + c − bb + cc) = a + b + c − bb + cc − ba + b + c − bb + ccc = a + b + c − bb + cc + bb + cc − ba + b + cc = a + b + c − ba + b + cc. We conclude that (a ? b) ? c = a ? (b ? c). Hence ? is associative. Commutative: For all a, b ∈ [0, 1) we do have a ? b = a + b − ba + bc = b + a − bb + ac = b ? a. So ? is commutative. Identity: The element 0 ∈ [0, 1) serves as the identity. Has Inverses: Let a ∈ [0, 1). If a = 0, then a is its own inverse. If a > 0, then the element b = 1 − a, which is also in [0, 1), satisfies a ? b = a + (1 − a) − ba + 1 − ac = 1 − b1c = 0. Hence, every element in [0, 1) has an inverse. Idempotent: Consider the element 0.5. We have 0.5 ? 0.5 = 0, so 0.5 gives one counter example to idempotence.

Exercise: 10 Section 1.2 Question: The operation 4 on nonnegative integers N defined by n4m = |m − n|. Solution: Associative: Let a = 1, b = 2, and c = 3. Observe a 4 (b 4 c) = ||c−b|−a| = 0 while (a 4 b) 4 c = |c−|b−a|| = 2. Therefore 4 is not associative. Commutative: a 4 b = |b − a| = |a − b| = b 4 a. Therefore 4 is commutative. Identity: a 4 e = |e − a| = |a − e| = e 4 a = a. Hence e = 0. Inverse: Every element is it’s own inverse. a 4 a = |a − a| = 0. Idempotent: a 4 a = 0 hence 4 is not idempotent.

1.2. THE CARTESIAN PRODUCT; OPERATIONS; RELATIONS

Exercise: 11 Section 1.2 Question: The operation ~ on points in the plane R2 where A ~ B is the midpoint of A and B. Solution: Associative: Let A = (a1 , a2 ), B = (b1 , b2 ), and C = (c1 , c2 ). A ~ (B ~ C) = 2a1 +b41 +c1 and (A ~ B) ~ C = a2 +b2 +2c2 . Thus, if A 6= C then A ~ (B ~ C) 6= (A ~ B) ~ C. Hence, ~ is not associative. 4 Commutative: The midpoint between A and B is the same as the midpoint between B and A, so ~ is commutative. Identity: Note that A ~ E = A if A = E. Since E is dependent on A, there does not exist an identity for ~. Inverse: Because there is no identity for ~, there cannot be any inverses. 1 a2 +a2 , 2 ) = (a1 , a2 ) = A. Therefore ~ is idempotent. Idempotent: A ~ A = ( a1 +a 2

Exercise: 12 Section 1.2 Question: The operation × + on C defined by a+ ×b = a + b + ab. Solution: Associative: Consider a, b, and c ∈ C. a+ ×(b+ ×c) = a + b + c + bc + ab + ac + abc = a + b + ab + c + ac + bc + abc = (a+ ×b)+ ×c Therefore × + is associative. Commutative: a+ ×b = a + b + ab = b + a + ba = b+ ×a. Therefore × + is commutative. Identity: Consider any q ∈ C. q+ ×0 = 0+ ×q = q so 0 is the identity. Inverse: Let b be the inverse of any a ∈ C. Then a+ ×b = 0 which implies a + b(1 + a) = 0. We can quickly −a deduce b = 1+a . From this observation we find that there exists an inverse for all values in C except −1. Thus, × + is not closed under inverses. Idempotent: Let a = 1. Then a+ ×a = 1 + 1 + 1 = 3 which is not equal to a. Hence, × + is not idempotent.

Exercise: 13 Section 1.2 Question: The operation 4 on P(S), where S is any set. Solution: Associative: S

Note in the above diagrams, the darker shading represents the operation within the parenthesis. We observe through the Venn diagrams that a 4 (b 4 c) = (a 4 b) 4 c. Thus, 4 is associative. Commutative:

CHAPTER 1. SET THEORY S

Observing the Venn diagram, A 4 B = B 4 A therefore 4 is commutative. Identity: A 4 ∅ = ∅ 4 A = A hence, ∅ is the identity of A. Inverse: Each set is it’s own inverse as A 4 A = ∅. Idempotent: A 4 A = ∅ implying 4 is not idempotent. Exercise: 14 Section 1.2 Question: The cross product on R3 Solution: Associative: Find any counter-example. Let ~a =< 1, 2, 3 >, ~b =< 1, 1, 1 >, and ~c =< 1, 2, 1 >. Then (~a × ~b) × ~c =< 4, 0, −4 > and ~a × (~b × ~c) =< 2, −4, 2 >. Since (~a × ~b) × ~c 6= ~a × (~b × ~c), the cross product is not associative over R3 . Commutative: For any two vectors in R3 , ~a × ~b = −~b × ~a. Hence the cross product is not commutative. Identity: The cross product is perpendicular to the plane created by the two vectors being multiplied by definition, therefore, there cannot exist a vector that satisfies ~a × ~e = ~a. Thus the cross product does not have an identity. Inverse: Because the cross product does not have an identity, it cannot be closed under inverses. Idempotent: Note, ~b × ~b =< 0, 0, 0 > which does not equal ~b in every case therefore the cross product is not idempotent. Exercise: 15 Section 1.2 Question: For the power operator a∧ b = ab on the set N∗ of positive integers determine whether it is associative, commutative, has an identity, has inverses or is idempotent. Solution: Associative: The following give a counter example 2∧ (3∧ 4) = 2∧ 81 = 281

while

(2∧ 3)∧ 4 = (23 )∧ 4 = 212

Hence ∧ is not associative. Commutative : Since 2∧ 3 = 8 and 3∧ 2 = 9, the operation ∧ is not commutative. Identity : Assume that ∧ has an identity e. Then ae = a for all a ∈ N∗ . Hence e = 1. However, by definition, we must also have ea = 1a = a for all a ∈ N∗ , which leads to a contradiction. Hence ∧ does not have an idenity element. Inverses: The operation cannot have an inverse since it does not have an identity. Idempotent: Since 2∧ 2 = 4 6= 2, then ∧ is not idempotent. Exercise: 16 Section 1.2 Question: The composition operator ◦ on the set F(A, A) of functions from a set A to A (where A is any set). Solution:

1.2. THE CARTESIAN PRODUCT; OPERATIONS; RELATIONS

Associative: Let f , g, and h be functions in F(A, A). Then (h ◦ g) ◦ f = h(g(f (a))) = h ◦ (g ◦ f ) where a ∈ A. Therefore, ◦ is associative. Commutative: Consider the function j where j(a) = a1 or in other words, every input gives the same output a1 . Now let k be a function such that k(a1 ) 6= a1 . Then j ◦ k(a) = a1 , but k ◦ j(a) 6= a1 . Therefore, ◦ is not commutative. Identity: Consider the function e where e(a) = a. Let q be any function in F(A, A). Then q ◦ e = q and e ◦ q = q. Therefore, e is the identity. Inverse: Let q be any function in F(A, A). Then q ◦ q −1 = q(q −1 (a)) = a and q −1 ◦ q = q −1 (q(a)) = a where a ∈ A. However, not every function from A to A is bijective, for example, the function j as described above. Therefore, ◦ is not closed under inverses. Idempotent: Let l be a function such that l(a1 ) = a2 and l(a2 ) = a3 . Then l(l(a1 )) = a3 which is not equal to l(a1 ). Thus, ◦ is not idempotent. Exercise: 17 Section 1.2 Question: Prove that for all A, B, C ∈ P(S), A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).

Solution: Let x be in A ∩ (B ∪ C). Then, x ∈ A and x ∈ (B ∪ C) by the definition of the intersection of sets. So, x ∈ A and x ∈ B, or x ∈ A and x ∈ C. By the definitions of the union and intersection of sets, x ∈ (A ∩ B) ∪ (A ∩ C). Therefore, A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C). Exercise: 18 Section 1.2 Question: Let S be a set with a binary operation ∗. Assume that (a ∗ b) ∗ a = b for all a, b ∈ S. Prove that a ∗ (b ∗ a) = b for all a, b ∈ S. Solution: Assume (a ∗ b) ∗ a = b for all a, b ∈ S. (a ∗ b) ∗ a = b (a ∗ b) ∗ a ∗ a = (b ∗ a) a ∗ (a ∗ b) ∗ a ∗ a = a ∗ (b ∗ a) (a ∗ b) ∗ a = a ∗ (b ∗ a) b = a ∗ (b ∗ a) Therefore, a ∗ (b ∗ a) = b for all a, b ∈ S. Exercise: 19 Section 1.2 Question: Consider the operations a∧ b = ab and a × b on N∗ . Prove that ∧ is right-distributive over × but not left-distributive over ×. Solution: Let a, b, c ∈ N∗ . For right-distributivity, we observe that (a × b)∧ c = (ab)c = ac bc = (a∧ c) × (b∧ c), so ∧ is right-distributive over ×. In contrast, as a counter example to left-distributivity 2∧ (3 × 4) = 212

while

2∧ 3 × 2∧ 4 = 23 · 24 = 27 .

Exercise: 20 Section 1.2 Question: Let S be a finite set with |S| = n. How many binary operations exist on S? Solution: Let S be a finite set with |S| = n. By proposition 1.2.4 we know that the size of S × S is |S| · |S|. By definiton of a function, we know that for every tuple in S × S there exists an element in S that is mapped

CHAPTER 1. SET THEORY

to. Therefore, every element in S × S has |S| possible associations. Since there are |S| · |S| elements, each with |S| possibilities, then there are |S||S|·|S| distinct functions possible from S × S to S. By substitution, there are 2 nn possible binary operators on S. Exercise: 21 Section 1.2 Question: Let S = {1, 2}. How many binary operations on S are associative? Solution: We observe that S × S = {(1, 1), (1, 2), (2, 1), (2, 2)}. Since each element maps to either 1 or 2, there are 24 binary operations on S. We can represent the binary operations as 4-tuples, (s1 , s2 , s3 , s4 ), where (1, 1) = s1 , (1, 2) = s2 , (2, 1) = s3 , and (2, 2) = s4 . Therefore, by checking each of the sixteen binary operations, the following upheld associativity: (1, 1, 1, 1), (1, 2, 2, 1), (2, 2, 2, 2), (2, 1, 1, 2), (1, 1, 1, 2), (1, 1, 2, 2), (1, 2, 1, 2), (1, 2, 2, 2) Hence, there are eight binary operations on S that are associative. Exercise: 22 Section 1.2 Question: Let A and B be finite sets. Find the number of distinct relations from A to B. Solution: Let A and B be finite sets. By definition, a distinct relation is a distinct subset of A × B. Recall, according to Proposition 1.2.4 that |A × B| = |A| · |B|. By Proposition 1.1.11, we know that |P(A × B)| = 2|A|·|B| . Therefore there are 2|A|·|B| distinct relations from A to B. Exercise: 23 Section 1.2 2 Question: Let A be a finite set with n elements. Prove that the number of reflexive relations on A is 2n −n and that the number of symmetric relations on A is 2n(n+1)/2 Solution: Let A be a finite set with n elements. Define S to be the set of all possible reflexive elements in A2 . Note, the smallest reflexive relation, which we will call B, is of size n such that B = {(a, a) | a ∈ A, ∀a}. Thus, we define S = {s | s ∈ A2 − B and B ∪ {s} is a reflexive relation}. We observe that S = A2 − B so |S| = n2 − n. With the union of P(S) and B we find all possible reflexive relations. By proposition 1.1.11 we 2 2 know that the size of P(S) is 2n −n . Therefore, there are 2n −n possible reflexive relations on A. Similar to the reflexive relations, if we can find the set of possible symmetric elements, then its power set will result in the number of symmetric relations on A. n=2

n=3

A×A

n=4

A×A

Each graph above represents the total number of symmetric elements for a set A of size n. By definition, every pair in the form of (a, a) is a distinct symmetric element. These elements, contained in B as defined before, are represented by the squares shown in the graphs above. Let T be the set of symmetric pairs in A2 − B such that T = {{(a, b), (b, a)} | ∀ a, b ∈ A2 }.These pairs are represented by the circles on the graph. To illustrate, when n = 2, the only symmetric pair is {(a1 , a2 ), (a2 , a1 )} represented by the single dot on the graph. Thus when n = 2, |T | = 1 and |B| = 2. Let X = T ∪ B. X contains all the symmetric elements of A2 . Hence we see when |A| = 2, that there are 3 symmetric elements. We observe that every time n increases, n symmetric Pn elements are added to X. It follows that |X| = i=1 i. By substitution, |X| = n(n+1) . Thus, the cardinality of 2 its power set results in 2

n(n+1) 2

symmetric relations on A.

Exercise: 24 Section 1.2 Question: For any set S, consider the relation G on P(S) defined by A G B to mean that A ∩ B 6= ∅. Solution:

1.2. THE CARTESIAN PRODUCT; OPERATIONS; RELATIONS

Reflexive: Choose any subset A. Then, A G A implies A ∩ A = A 6= ∅ which is true for all cases except the empty set. However, ∅ ∈ P(S) so G is not reflexive. Symmetric: Let A and B be subsets of S. Then, A G B ⇒ A ∩ B 6= ∅ ⇒ B ∩ A 6= ∅ ⇒ B G A Therefore, G is symmetric. Antisymmetric: Consider the set S = {1, 2, 3, 4}. Let A = {1, 2} and B = {3, 4}. We observe that both A G B and B G A exist, however it does not imply that they are equal. Hence, G is not antisymmetric. Transitive: Consider the set S = {1, 2, 3, 4}. Let A = {1, 2}, B = {3}, and C = {2, 4}. Notice that while A G B and B G C satisfy the conditions of transitivity, A G C does not exist because A ∩ C = {2}. Hence, G is not transitive.

Exercise: 25 Section 1.2 Question: The relation % on S the set of people defined by p1 % p2 if p1 is taller than or the same height as p2 . Solution: Reflexive: Any person is the same height as himself, therefore % is reflexive. Symmetric: Consider the case where an individual p1 is taller than p2 . Then p1 % p2 but p2 6% p1 . Hence, % is not symmetric. Antisymmetric: Assume (p1 % p2 ) and (p2 % p1 ), but p1 6= p2 . This implies that either p1 is taller than p2 or vice versa. Without loss of generality, suppose p1 is taller than p2 . Then p1 % p2 but p2 6% p1 which is a contradiction. Therefore, if p1 % p2 and p2 % p1 , then p1 = p2 . Thus % is antisymmetric. Transitive: Assume that p1 6% p3 , but p1 % p2 and p2 % p3 where p2 6= p3 . This implies that p2 is taller than p3 and p1 is taller than or equal to p2 . Hence, p1 would have to be taller than p3 which is a contradiction. Therefore, if p1 % p2 and p2 % p3 , then p1 % p3 implying % is transitive. Exercise: 26 Section 1.2 Question: The relation R on Z defined by nRm if n ≥ m2 . Solution: Reflexive: Find any counter-example. Let n = 2. This creates a contradiction since 2 6≥ 4, therefore R is not reflexive. Symmetric: Find any counter-example. Let n = 9 and m = 2. It is clear to see that nRm but the reverse is not true. This creates a contradiction so R is not symmetric. Antisymmetric: Let n and m be integers such that nRm and mRn. This implies that n ≥ m2 and m ≥ n2 . By squaring both sides and substitution, we find that n ≥ n4 which is only true if n = 1. Applying the same method the other direction, we find that m = 1 as well. Therefore, the only case where nRm and mRn is when n = m = 1. Thus, R is antisymmetric. Transitive: Let a, b and c be integers. Assume a 6≥ c2 , but aRb and bRc. Using some substitution, this implies that a ≥ b2 ≥ c2 . This creates a contradiction, therefore R is transitive.

Exercise: 27 Section 1.2 Question: Consider the relation on S = R2 defined by (x1 , y1 ) (x2 , y2 ) to mean x21 + y12 ≤ x22 + y22 . Prove which of the properties reflexivity, symmetry, antisymmetry, and transitivity hold. Solution: Reflexivity: Let (x, y) ∈ R2 . Then x2 + y 2 ≤ x2 + y 2 , so (x, y) (x, y). Hence is reflexive.

CHAPTER 1. SET THEORY

Symmetry: Consider the elements (1, 1) and (1, 2). Then 12 + 12 ≤ 12 + 22 so (1, 1) (1, 2). However 12 + 22 6≤ 12 + 12 so (1, 2) 6 (1, 1). Hence is not symmetric. Antisymmetry: Note that (1, 2) (2, 1) and (2, 1) (1, 2) but since (1, 2) 6= (2, 1), then is not antisymmetric. Transitivity: Consider three points (x1 , y1 ), (x2 , y2 ), and (x3 , y3 ). Suppose that (x1 , y1 ) (x2 , y2 ) and (x2 , y2 ) (x3 , y3 ). Then x21 + y12 ≤ x22 + y22 and x22 + y22 ≤ x23 + y32 . Hence x21 + y12 ≤ x22 + y22 so (x1 , y1 ) (x3 , y3 ). Hence is transitive. Exercise: 28 Section 1.2 Question: The relation $ on R defined by a $ b to mean ab = 0. Solution: Reflexive: Consider the case where a ∈ R and a 6= 0. Then a $ a ⇒ a2 = 0. This creates a contradiction as this is not true in every case, thus $ is not reflexive. Symmetric: Suppose a $ b. By definition, ab = 0 implying that either a = 0 or b = 0. In either case, ba = 0. Hence, b $ a therefore $ is symmetric. Antisymmetric: Let a 6= 0 and b = 0. Then a $ b and b $ a, but a 6= b. Hence, $ is not antisymmetric. Transitive: Let a 6= 0, b = 0, and c 6= 0. Then a $ b and b $ c, but a 6$ c since a 6= 0 and c 6= 0. Thus, $ is not transitive.

Exercise: 29 Section 1.2 Question: For any set S, consider the relation

on P(S) defined by A

B to mean that A ∪ B = S.

Solution: Reflexive: Let A ∈ P(S) and A 6= S. Then, A ∪ A = A which is not equal to S, therefore Symmetric: Suppose A, B are in P(S) and A is symmetric.

is not reflexive.

B. Then A ∪ B = B ∪ A = S which implies B

Antisymmetric: Let A = ∅ and B = S. Then, A antisymmetric.

B and B

A, but A 6= B. Therefore,

A. Hence, cannot be

Transitive: Let A = ∅, B = S, and C 6= S such that A C. However, notice that A B and B A C implies A ∪ C = S which creates a contradiction since C 6= S. Thus, is not transitive.

Exercise: 30 Section 1.2 Question: The relation on the set of pairs of points in the plane S = R2 ×R2 defined by (P1 , Q1 ) if the segment [P1 , P2 ] intersects [Q1 , Q2 ].

C, but

(P2 , Q2 )

Solution: Reflexive: Let P1 , P2 be in S. It is not hard to see that (P1 , P1 ) itself. Hence, is reflexive.

(P2 , P2 ) because any line intersects with

Symmetric: Suppose (P1 , Q1 ) (P2 , Q2 ). Then [P1 , P2 ] intersects [Q1 , Q2 ] implying that [Q1 , Q2 ] intersects [P1 , P2 ] and (Q1 , P1 ) (Q2 , P2 ). Thus, is symmetric. Antisymmetric: Let (P1 , Q1 ) (P2 , Q2 ) such that [P1 , P2 ] is perpendicular to [Q1 , Q2 ]. It is not hard to show that (P1 , Q1 ) (P2 , Q2 ) and (Q1 , P1 ) (Q2 , P2 ), but it is impossible for [P1 , P2 ] to be equal to [Q1 , Q2 ]. Therefore, is not antisymmetric. Transitive: Let [P1 , P2 ], [Q1 , Q2 ], and [R1 , R2 ] be lines in S and let [P1 , P2 ] be parallel to [R1 , R2 ] and perpendicular to [Q1 , Q2 ]. Then (P1 , Q1 ) (P2 , Q2 ) and (Q1 , R1 ) (Q2 , R2 ), but it is impossible for (P1 , R1 ) (P2 , R2 ) since they are parallel to each other. Therefore, is not transitive.

1.2. THE CARTESIAN PRODUCT; OPERATIONS; RELATIONS

Exercise: 31 Section 1.2 Question: Let S be a set and let R be a relation on S. Prove that if a relation is reflexive, symmetric, and anti-symmetric, then it is the = relation on S. Solution: Let S be a set and let R be a relation on S such that R is reflexive, symmetric, and antisymmetric. By definition, R contains all elements of the form (s, s) ∀s ∈ S. Since R is symmetric, if s R t then t R s where s, t ∈ S. Moreover, R is antisymmetric implying that if there is a symmetric pair (s, t), (t, s) ∈ R, then s = t. Hence, it is impossible for R to contain an element of the form (s, t) where s 6= t. Therefore, R = {(s, s), ∀s ∈ S} which is the = relation.

Exercise: 32 Section 1.2 Question: Let P be the set of people who are living now. Let R be the relation on P defined by aRb if a and b are in the same nuclear family, i.e. if a is a self, child, parent, sibling, or spouse of b. a) Decide whether R is reflexive, symmetric, antisymmetric, or transitive. b) List all the family relations included in R(2) = R ◦ R. c) Give four commonly used family terms for relations in R(3) = R ◦ R ◦ R though not in R(2) . Solution: a) For any person p, p R p since ’self’ is included in the nuclear family, therefore R is reflexive. Assume there exists two people p1 and p2 such that p1 R p2 but p2 is not related to p1 . It is not hard to see that this creates a contradiction as any two people who are in the same nuclear family satisfy the relation R. Therefore R is symmetric. In regards to antisymmetry, consider any p1 R p2 where p1 is the child of p2 . We know that p1 R p2 and p2 R p1 , however p1 and p2 are not the same person. Hence, R is not antisymmetric. Let p1 be the child of p2 and p2 be the sibling of p3 . We can easily observe that p1 R p2 and p2 R p3 , yet p1 is not in the same nuclear family as p3 . Therefore R is not transitive. b) R2 = {self, child, parent, sibling, spouse, grandchild, child-in-law, grandparent, uncle / aunt, niece / nephew, sibling-in-law, parent-in-law} c) {cousin, great-grandchild, great-grandparent, great-uncle / aunt}

Exercise: 33 Section 1.2 Question: We can define the graph of a relation R from R to itself as the subset of R2 {(x, y) ∈ R2 | x R y}. a) Sketch the graph of the relation ≤. b) Sketch the graph of the relation l defined by x l y if |x − y| = 1. c) Provide defining geometric characteristics of a subset of R2 for a relations on R that are i) reflexive; ii) symmetric; iii) transitive; iv) antisymmetric. Solution: y

y=x

CHAPTER 1. SET THEORY y

y =x+1 y =x−1

b) c) i) A reflexive relation must contain the line y = x. ii) A symmetric relation must have a reflective mapping over the line y = x. iii) An antisymmetric relation cannot have a reflective mapping over the line y = x and must include points from the line y = x. iv) In a transitive relation, for any points (x, y) and (y, z) there exists a right triangle that contains the points (x, y), (y, z), and (x, z). Exercise: 34 Section 1.2 Question: Let S = {a, b, c, d, e} and consider the relation R on S described by R = {(a, a), (a, c), (a, d), (b, c), (b, e), (c, b), (c, d), (e, a), (e, b)}. Determine as a list in S × S, the composite relation R ◦ R. Solution: R ◦ R = {(a, a), (a, b), (a, c), (a, d), (b, a), (b, b), (b, d), (c, c), (c, e), (e, a), (e, c), (e, d), (e, e)} Exercise: 35 Section 1.2 Question: Let R be a relation on a set A. Denote by R(n) the n-composite relation of R with itself: n times

(n) def

z }| { = R ◦ R ◦ · · · ◦ R.

Prove that the relation R is transitive if and only if R(n) ⊆ R for all n = 1, 2, 3, . . .. Solution: (=⇒): Suppose R is transitive. Assume that R(n) contains an element (x, y) such that (x, y) 6∈ R. Then there exists some z ∈ A such that (x, z) and (z, y). This creates a contradiction by the definition of a transitive relation, thus ∀(x, y) ∈ R(n) , (x, y) ∈ R. Therefore, R(n) ⊆ R. (⇐=): Suppose R(n) ⊆ R. Assume that there exists a R b and b R c such that a is not related to c. By definition of relation composition, a R c exists in R(n) . If a R c exists in R(n) , then it must also exist in R by definition of a subset causing a contradiction. Hence, if a R b and b R c, then a R c. Therefore, R is transitive. Exercise: 36 Section 1.2 Question: Let R be a relation that is reflexive and transitive. Prove that Rn = R for all n ∈ N∗ . Solution: Let R be a relation that is reflexive and transitive. From exercise 1.2.35 we know that Rn ⊆ R. Consider the case when n = 2 and let (r1 , r2 ) be any pair in R. Then r1 R r1 and r1 R r2 , since R is reflexive, therefore r1 R r2 must be in R2 . We can easily observe that the same is true for R3 in that r1 R r1 and r1 R r1 and r1 R r2 , so (r1 , r2 ) must be in R3 . We can continue this process for any n to show that any (r1 , r2 ) in R must also be in Rn . This implies that R ⊆ Rn . Therefore, Rn = R for all n ∈ N∗ .

1.3 – Equivalence Relations Exercise: 1 Section 1.3 Question: Let S = Z × Z and let R be the relation on S defined by (a, b)R(c, d) means that a + d = b + c. Show that R is an equivalence relation. Concisely describe the equivalence classes of R. Solution: Let S = Z × Z and let R be the relation on S defined by (a, b)R(c, d) means that a + d = b + c. For any (a, b) in S it is not hard to see that (a, b) R (a, b) means a + b = a + b therefore R is reflexive. Suppose

1.3. EQUIVALENCE RELATIONS

(a, b) R (c, d). Then, a + d = b + c which is equivalent to c + b = d + a. This implies (c, d) R (a, b) therefore R is symmetric. Suppose (a, b) R (c, d) and (c, d) R (e, f ). Then a + d = b + c and c + f = d + e. Using subtraction and substitution we find that a − b = e − f . With some arranging we observe a + f = b + e implying (a, b) R (e, f ). Hence, R is transitive. Therefore, since R is reflexive, symmetric, and transitive it is an equivalence relation. Each distinct equivalence class describes the solutions to a function f : Z −→ Z where f (x) = x + c for c ∈ Z. Exercise: 2 Section 1.3 Question: Let C be the set of people in your abstract algebra class. Describe a “natural” relation satisfying each of the combination of properties listed below. 1. Reflexive and symmetric, but not transitive. 2. Reflexive and transitive, but not symmetric. 3. Symmetric and transitive, but not reflexive. 4. An equivalence relation. Solution: We describe relations for each of the following situations. a) Reflexive and symmetric, but not transitive. R, where a R b if a and b live within one kilometer (or one mile) of each other. b) Reflexive and transitive, but not symmetric. R, where a R b if a earns a final grade that is less than or equal to the final grade that b earns. c) Symmetric and transitive, but not reflexive. The simplest relation that satisfies these conditions is the empty relation. Symmetry and transitivity are satisfied trivially. (The hypothesis is always false so the conditional statement is always true.) Note that if a R b, where a 6= b, then by symmetry b R a and then by transitivity a R a. So for this combinations of properties to hold, there must be an element that is not in relation to any other element. d) An equivalence relation. R, where a R b if a and b entered college the same semester. Exercise: 3 Section 1.3 Question: Let P be the set of living people. For all a, b ∈ P , define the relation a R b if a and b have met. Solution: It is not hard to see that R is both reflexive and symmetric by definition. However, let a, b, and c be people such that a R b and b R c. It does not follow that person a has met person c in every case implying R is not transitive. Therefore, R is not an equivalence relation. Exercise: 4 Section 1.3 Question: Let P be the set of living people. For all a, b ∈ P , define the relation a R b if a and b live in a common town. Solution: Obviously, a R a exists for all people within the town. It quickly follows that if a R b then b R a and therefore is symmetric as well. Suppose a R b and b R c. Then a and b live in a common town, and b and c live in the same town. Hence, a and c live in the same town meaning a R c and R is transitive. Therefore, R is an equivalence relation. Exercise: 5 Section 1.3 Question: Let C be the set of circles in R2 and let R be the relation of concentric on C. Prove or disprove whether the described relation is an equivalence relation. If the relation is not an equivalence relation, determine which properties it lacks. Solution: Two circles are concentric if and only if they have the same center. Reflexivity: If C is a circle in C, then it has the same center as itself. Symmetry: If C1 , C2 ∈ C, then if C1 has the same center as C2 , then C2 has the same center as C1 . So symmetry holds. Transitivity: Let C1 , C2 , C3 ∈ C. Suppose that C1 is concentric with C2 and that C2 is concentric with C3 . Then C1 and C2 have the same center and C2 and C3 have the same center. Hence C1 and C3 have the same center, so C1 is concentric with C3 . Hence concentric is transitive.

CHAPTER 1. SET THEORY

So the concentric relation is an equivalence relation. Exercise: 6 Section 1.3 Question: Let S = Z × Z and define the relation R on S by (m1 , m2 ) R (n1 , n2 ) if m1 m2 = n1 n2 . Solution: Consider any (m1 , m2 ) ∈ S. We observe (m1 , m2 ) R (m1 , m2 ) implies m1 m2 = m1 m2 which is always true. Hence, R is reflexive. Suppose (m1 , m2 ) R (n1 , n2 ). We know m1 m2 = n1 n2 so n1 n2 = m1 m2 and therefore (n1 , n2 ) R (m1 , m2 ). Hence, R is symmetric. Suppose (m1 , m2 ) R (n1 , n2 ) and (n1 , n2 ) R (p1 , p2 ). Then, m1 m2 = n1 n2 and n1 n2 = p1 p2 . By substitution, we find m1 m2 = p1 p2 implying (m1 , m2 ) R (p1 , p2 ). Hence, R is transitive and therefore is an equivalence relation. Exercise: 7 Section 1.3 Question: Let S = Z × Z and define the relation R on S by (m1 , m2 ) R (n1 , n2 ) if m1 n1 = m2 n2 . Solution: Consider the relation (1, 2) R (1, 2). Since 1 × 1 6= 2 × 2, then R is not reflexive. Therefore, R is not an equivalence relation. Exercise: 8 Section 1.3 Question: Let S = Z × Z and define the relation R on S by (m1 , m2 ) R (n1 , n2 ) if m1 n2 = m2 n1 . Solution: Suppose m1 , m2 ∈ Z and (m1 , m2 ) R (m1 , m2 ). Then m1 m2 = m2 m1 for any (m1 , m2 ) ∈ S, thus R is reflexive. Suppose (m1 , m2 ) R (n1 , n2 ) where n1 , n2 ∈ Z. Then, m1 n2 = m2 n1 which can be easily rearranged to show n1 m2 = n2 m1 . This implies (n1 , n2 ) R (m1 , m2 ), and therefore R is symmetric. Suppose r1 , r2 , s1 , s2 , t1 , t2 ∈ Z such that (r1 , r2 ) R (s1 , s2 ) and (s1 , s2 ) R (t1 , t2 ). Then, r1 s2 = r2 s1 and s1 t2 = s2 t1 . Using some substitution we can arrive at the desired outcome as seen below, r1 s2 = s1 r2 r1 s2 t1 = s1 r2 t1 r1 s1 t2 = s1 r2 t1 r1 t2 = t1 r2 Therefore, since R is reflexive, symmetric, and transitive, R is an equivalence relation. Exercise: 9 Section 1.3 Question: Let P3 be the set of polynomials with real coefficients and of degree 3 or less. Define the relation R on P3 by p(x) R q(x) to mean that q(x) − p(x) has 5 as a root. Solution: Notice, 5 will always be a root of f (x) − f (x) so R is reflexive. Consider the case when p(x) = x − 12 and q(x) = 2x − 7. We observe that p(x) R q(x) since q(x) − p(x) = x − 5. However, because p(x) − q(x) = −x − 5, 5 is not a root of p(x) − q(x) therefore q(x) is not related to p(x). Since R is not symmetric it cannot be an equivalence relation. Exercise: 10 Section 1.3 Question: Consider the set C 0 (R) of continuous functions over R. Define the relation R on C 0 (R) by f R g if there exist some a, b ∈ R such that g(x) = f (x + a) + b

for all x ∈ R.

Prove or disprove whether the described relation is an equivalence relation. If the relation is not an equivalence relation, determine which properties it lacks. Solution: We check the defining properties for an equivalence relation. Reflexivity: Let f be any function in C 0 (R). Setting a = b = 0 we have f (x) = f (x + a) + b for all x. Hence R is reflexive. Symmetry: Suppose that f R g. Then there exists some a, b ∈ R such that g(x) = f (x + a) + b. Then g(x) − b = f (x + a) for all x ∈ R. Setting y = x + a, we have g(y − a) − b = f (y). This holds for all y ∈ R. Hence g R f . Thus, R is symmetric.

1.3. EQUIVALENCE RELATIONS

Transitivity: Let f, g, h ∈ C 0 (R) and suppose that f R g and g R h. There there exist a1 , a2 , b1 , b2 ∈ R such that g(x) = f (x + a1 ) + b1 and h(x) = g(x + a2 ) + b2 for all x ∈ R. Then h(x) = f (x + a + 2 + a1 ) + b1 + b2 for all x ∈ R. Hence f R h. Thus R is transitive. Exercise: 11 Section 1.3 Question: Let Pfin (R) be the set of finite subsets of R and define the relation ∼ on Pfin (R) by A ∼ B if the sum of elements in A is equal to the sum of elements in B. Prove that ∼ is an equivalence relation. Solution: It is not hard to see A ∼ A for all A ∈ R, so ∼ is reflexive. Similarly, if A ∼ B, then the sum of elements in A is equal to the sum of elements in B. Thus, we observe that this implies that B ∼ A. Therefore, ∼ is symmetric. Moreover, given any A, B, C ∈ R where A ∼ B and B ∼ C, it quickly follows that the sum of elements in A is equal to the sum of elements in C by substitution. Hence, ∼ is transitive and therefore is an equivalence relation. Exercise: 12 Section 1.3 Question: Let `∞ (R) be the set of sequences of real numbers. Define the relation R on `∞ (R) by (an ) R (bn ) if lim (bn − an ) = 0.

n→∞

Solution: It is not hard to see that R is reflexive since lim (an − an ) = lim (0) = 0

n→∞

Also, notice lim (bn − an ) = − lim (an − bn ) = 0

n→∞

therefore R is symmetric. For transitivity, suppose that (an )R(bn ) and (bn )R(cn ). Then lim (bn − cn ) = 0

n→∞

and

lim (an − bn ) = 0.

n→∞

Thus lim (an − cn ) = lim ((an − bn ) + (bn − cn )) = lim (an − bn ) + lim (bn − cn ) = 0 + 0 = 0,

n→∞

where the second equality holds by virtue of the addition law of limits. Note that we can apply the addition rule here because we know that each of the sequences involved in the sums converge (to 0). Exercise: 13 Section 1.3 Question: Let `∞ (R) be the set of sequences of real numbers. Define the relation R on `∞ (R) by (an ) R (bn ) if the sequence (an + bn )∞ n=1 converges. Solution: Using the properties of limits we can show limn→∞ (an + an ) = 2 limn→∞ (an ). Find any counterexample for reflexivity. Let an = 2n . Then, 2 limn→∞ (an ) = ∞ implying R cannot be reflexive. Therefore, R cannot be an equivalence relation. It should be noted, however, that R is both symmetric and transitive. Exercise: 14 Section 1.3 Question: Let S be the set of lines in R2 and let R be the relation of perpendicular. Solution: We observe that any given line cannot be perpendicular to itself, therefore R cannot be reflexive. Thus R is not an equivalence relation. Exercise: 15 Section 1.3 Question: Let W be the words in the English language (i.e., have an entry in the Oxford English Dictionary). Define the relation R on W by w1 R w2 is w1 comes before w2 in alphabetical order. Solution: This relation is not symmetric. Find any counter-example. Consider the two words, w1 =”ball” and w2 =”stick”. We observe that w1 R w2 , but the reverse is not true. Hence, R cannot be an equivalence relation.

CHAPTER 1. SET THEORY

Exercise: 16 Section 1.3 Question: Let C 0 ([0, 1]) be the set of continuous real-valued functions on [0, 1]. Define the relation ∼ on C 0 ([0, 1]) by Z 1 Z 1 g(x) dx. f (x) dx = f ∼ g ⇐⇒ 0

Show that ∼ is an equivalence relation and describe (with a precise rule) a complete set of distinct representatives of ∼. Solution: First show that ∼ is an equivalence relation. R1 R1 Reflexivity: For all f ∈ C 0 ([0, 1]), we have 0 f (x) dx = 0 f (x) dx so f ∼ f . Symmetry: Suppose that f, g ∈ C 0 ([0, 1]) with f ∼ g. Then Z 1

Z 1 f (x) dx =

g(x) dx. 0

Equality is reversible so g ∼ f . Hence ∼ is symmetric. Transitivity: Suppose that f, g, h ∈ C 0 ([0, 1]) with f ∼ g and g ∼ h. Then Z 1

Z 1 f (x) dx =

Hence

R1 0

f (x) dx =

R1 0

Z 1 g(x) dx

and

Z 1 g(x) dx =

h(x) dx. 0

h(x) dx. Thus f ∼ h. Hence ∼ is an equivalence relation.

R1 Every function f ∈ C 0 ([0, 1]) is in relation with the constant function g(x) = c, where c = 0 f (x) dx. However, constant functions that are not equal are not in relation with each other. Hence the constant functions are a complete set of distinct representatives.

Exercise: 17 Section 1.3 Question: Let C ∞ (R) be the set of all real-value functions on R such that all its derivatives exist and are continuous. Define the relation R on C ∞ (R) by f R g if f (n) (0) = g (n) (0) for all positive, even integers n. a) Prove that R is an equivalence relation. b) Describe concisely all the elements in the equivalence class [sin x]. Solution: a) It is not hard to see that for any f ∈ C ∞ (R), f R f implies f (n) (0) = f (n) (0). We conclude that R is reflexive. Similarly, for any f, g ∈ C ∞ (R) if f R g, then we observe g R f quickly follows since f (n) (0) = g (n) (0). Thus R is symmetric as well. Finally, for any given f, g, h ∈ C ∞ (R) such that f R g and g R h, we find f R h because f (n) (0) = g (n) (0) = h(n) (0) for all positive even integers n. Consequently, R is reflexive, symmetric, and transitive implying that R is an equivalence relation. b) If f (x) = sin x then for all positive and even integers n, we have f (n) (0) = 0, so this is the defining characteristic of functions in [sin x]. (If a function in [sin x] is equal to its power series in a neighborhood of 0, then [sin x] consists of functions that are a constant plus an odd function.) Exercise: 18 Section 1.3 Question: Let S = {1, 2, 3, 4} and the relation ∼ on P(S), defined by A ∼ B if and only if the sum of elements in A is equal to the sum of elements in B, is an equivalence relation. List the equivalence classes of ∼. Solution: [{1}], [{2}], [{3}] = {{1, 2}}, [{4}] = {{1, 3}}, [{1, 4}] = {{2, 3}}, [{2, 4}] = {{1, 2, 3}}, [{3, 4}] = {{1, 2, 4}}, [{1, 3, 4}], [{2, 3, 4}], [{1, 2, 3, 4}], [∅] Exercise: 19 Section 1.3 Question: Let T be the set of (non-degenerate) triangles in the plane. a) Prove that the relation ∼ of similarity on triangles in T is an equivalence relation. b) Concisely describe a complete set of distinct representatives of ∼. Solution:

1.3. EQUIVALENCE RELATIONS

a) Suppose you have any t ∈ T . Then, t ∼ t implies that triangle t has equal corresponding angles with itself. This is always true, thus ∼ is reflexive. Now suppose you have to triangles s, t ∈ mathcalT such that s ∼ t. Then the corresponding angles of triangle s are equal to the corresponding angles of t. It is not hard to see that the corresponding angles of triangle t are equal to the corresponding angles of triangle s implying that ∼ is symmetric. For transivity, suppose you have any r, s, t ∈ mathcalT such that r ∼ s and s ∼ t. Then the corresponding angles of triangle r are equal to the corresponding angles of triangle s which are also equal to the corresponding angles of t. Therefore the corresponding angles of triangle r are equal to those in triangle t. Hence, ∼ is transitive. Therefore, ∼ is an equivalence relation. b) The set of distinct representatives of ∼ will be equal to the unique combinations of the angles x, y, z of any triangle such that x, y, z ∈ R>0 and x + y + z = 180. For example, [30, 60, 90] is the distinct representative for all triangles with 30, 60, and 90 as their respective angles. Exercise: 20 Section 1.3 Question: Prove that the relation defined in Example 1.3.10 is an equivalence relation. Solution: Choose any (a, b) in S. We quickly observe that ab = ba which holds true for all a, b under multiplication. Thus, R is reflexive. Now suppose that R is symmetric and choose any (a, b), (c, d) ∈ S such that (a, b) ∼ (c, d). Then, ad = bc so we can show that cb = da implying that (c, d) ∼ (a, b). Hence, R is symmetric. Suppose R is also transitive. Let (a, b), (c, d), (e, f ) be in S such that (a, b) ∼ (c, d) and (c, d) ∼ (e, f ). Then ad = bc and df = ec. By multiplying both sides by ab we observe, abdf = abec af bd = beac af bd = bebd af = be Consequently, (a, b) ∼ (e, f ). Thus ∼ is transitive and therefore an equivalence relation. Exercise: 21 Section 1.3 Question: Let S = {1, 2, 3, 4, 5, 6}. For the partitions of S given below, write out the equivalence relation as a subset of S × S. a) {{1, 2}, {3, 4}, {5, 6}} b) {{1}, {2}, {3, 4, 5, 6}} c) {{1, 2}, {3}, {4, 5}, {6}} Solution: a) {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2), (2, 1), (3, 4), (4, 3), (5, 6), (6, 5)} b) {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (3, 4), (3, 5), (3, 6), (4, 3), (4, 5), (4, 6), (5, 3), (5, 4), (5, 6), (6, 3), (6, 4), (6, 5)} c) {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5), (6, 6), (1, 2), (2, 1), (4, 5), (5, 4)} Exercise: 22 Section 1.3 Question: Let S = {a, b, c, d, e}. For the partitions of S given below, write out the equivalence relation as a subset of S × S. a) {{a, d, e}, {b, c}} b) {{a}, {b}, {c}, {d}, {e}} c) {{a, b, d, e}, {c}} Solution: a) {(a, a), (b, b), (c, c), (d, d), (e, e), (a, d), (a, e), (d, a), (d, e), (e, a), (e, d), (b, c), (c, b)} b) {(a, a), (b, b), (c, c), (d, d), (e, e)}

CHAPTER 1. SET THEORY c) {(a, a), (b, b), (c, c), (d, d), (e, e), (a, b), (a, d), (a, e), (b, a), (b, d), (b, e), (d, a), (d, b), (d, e), (e, a), (e, b), (e, d)}

Exercise: 23 Section 1.3 Question: Let C 1 ([a, b]) be the set of continuously differentiable functions on the interval [a, b]. Define the relation ∼ on C 1 ([a, b]) as f ∼ g if and only if f 0 (x) = g 0 (x) for all x ∈ (a, b). Prove that ∼ is an equivalence relation on C 1 ([a, b]). Describe the elements in the equivalence class for a given f ∈ C 1 ([a, b]). Solution: First, we observe for any f ∈ C 1 ([a, b]) that f 0 (x) = f 0 (x) for all x ∈ (a, b). Hence, ∼ is reflexive. Similarly, given any f, g ∈ C 1 ([a, b]) we observe that if f ∼ g then f 0 (x) = g 0 (x) for all x ∈ (a, b). Thus we know g 0 (x) = f 0 (x) which establishes that ∼ is also symmetric. For transivity, consider any f, g, h ∈ C 1 ([a, b]) where f ∼ g and g ∼ h. Then f 0 (x) = g 0 (x) = h0 (x) for all x ∈ (a, b). Thus f 0 (x) = h0 (x) implying that ∼ is transitive. Therefore, ∼ is an equivalence relation. The elements of the equivalence class for a given f are the vertical translations of f . In other words, [f (x)] = {f (x) + k | k is some constant in R}. Exercise: 24 Section 1.3 Question: Let Mn×n (R) be the set of n × n matrices with real coefficients. For two matrices A, B ∈ Mn×n (R), we say that B is similar to A if there exists and invertible n × n matrix S such that B = SAS −1 . 1. Prove that similarity ∼ is an equivalence relation on Mn×n (R). 2. Prove that the function f : Mn×n (R)/ ∼ → R defined by f ([A]) = det A is a well-defined function on the quotient set Mn×n (R)/ ∼. 3. Determine with proof or counter-example whether the function g : Mn×n (R)/ ∼ → R defined by g([A]) = Tr A, the trace of A, is a well-defined function. Solution: Let Mn×n (R) be the set of n×n matrices with real coefficients and define the relation ∼ as similarity between matrices. a) We prove that ∼ is an equivalence relation. Reflexivity: For all matrices A ∈ Mn×n (R), since IAI −1 = A then A ∼ A. Symmetry: Let A, B ∈ Mn×n (R) such that A ∼ B. Then there exists an invertible matrix S such that B = SAS −1 . Hence A = S −1 BS. Thus B ∼ A so ∼ is symmetric. Transitivity: Let A, B, C ∈ Mn×n (R) such that A ∼ B and B ∼ C. Thus there exist invertible matrices A and T such that B = SAS −1 and C = T BT −1 . Then C = T (SAS −1 )T −1 = (T S)A(T S)−1 . Hence A ∼ C so ∼ is transitive. b) Suppose that B ∼ A. Then B = SAS −1 for some invertible matrix S. Then det B = (det S)(det A)(det S)−1 = det A. Therefore, the function det is well-defined on the set of ∼-equivalence classes on Mn×n (R). c) There is a property in the algebra of matrices that Tr(AB) = Tr(BA), even if the matrices do not commute. Suppose that B ∼ A with B = SAS −1 for some invertible matrix S. Then Tr(B) = Tr(SAS −1 ) = Tr(ASS −1 ) = Tr(A). Hence the function g is a well-defined function. Exercise: 25 Section 1.3 Question: Define the relation ∼ on R by a ∼ b if and only if b − a ∈ Q. a) Prove that all real x ∈ R, there exists y ∈ [x]∼ that is arbitrarily close to x. (In other words, for all ε > 0, there exists y with y ∼ x and |x − y| < ε.

1.3. EQUIVALENCE RELATIONS

b) (*) Prove that ∼ has an uncountable number of equivalence classes. Solution: a) Choose any q ∈ Q such that q < . Then, if |x − y| = q, y ∼ x and |x − y| < . Rearranging our equation we find, y =x+q y =x−q Notice that the domain of these functions spans R. Therefore for any x ∈ R there exists y ∈ R such that y ∼ x and |x − y| < . A graphical representation is shown below. y

y =x+ y =x+q y =x−q y =x− x

b) Since ∼ is reflexive, every value in R has its own equivalence class. Since R is uncountable, it follows that there are an uncountable amount of equivalence classes. Exercise: 26 Section 1.3 Question: Let R1 and R2 be equivalence relations on a set S. Determine (with a proof or counterexample) which of the following relations are also equivalence classes on S. (a) R1 ∩ R2 ; (b) R1 ∪ R2 ; (c) R1 4R2 . [Note that R1 ∪ R2 , and similarly for the others, is a relation as a subset of S × S.] Solution: Let R1 and R2 be equivalence relations on a set S. a) R1 ∩R2 is an equivalence relation. For all a ∈ S, the pair (a, a) is in both R1 and R2 . Hence (a, a) ∈ R1 ∩R2 . Thus R1 ∩R2 is reflexive. Suppose that (a, b) ∈ R1 ∩R2 . Then since R1 is an equivalence relation, (b, a) ∈ R1 and similarly for R2 . Hence (b, a) ∈ R1 ∩ R2 . Thus R1 ∩ R2 is symmetric. Finally, suppose that (a, b) and (b, c) are pairs in R1 ∩ R2 . Then since R1 is an equivalence relation (a, c) ∈ R1 and the same holds for R2 , so (a, c) ∈ R2 . Thus (a, c) ∈ R1 ∩ R2 and hence R1 ∩ R2 is transitive. b) R1 ∪ R2 is not an equivalence relation. Since R1 is reflexive, for all a ∈ S, the pair (a, a) ∈ R1 and thus (a, a ∈ R1 ∪ R2 . Hence, R1 ∪ R2 is reflexive. Suppose that (a, b) ∈ R1 ∪ R2 . Thus (a, b) ∈ R1 or (a, b) ∈ R2 . Both R1 and R2 are equivalence relations. If (a, b) ∈ Ri , then (b, a) ∈ Ri so (b, a) ∈ R1 ∪ R2 . Thus, R1 ∪ R2 is symmetric. Finally, suppose that (a, b) and (b, c) are in R1 ∪ R2 . In the case where (a, b) ∈ R1 and (b, c) ∈ R2 , it does not appear that transitivity would need to hold if (b, c) ∈ / R1 and (a, b) ∈ / R2 . For example, let S = P({1, 2, 3, 4, 5}) and let R1 be the equivalence relation on S of same cardinality and let R2 be the equivalence relation of elements summing to the same value. Then {1, 4} R1 ∪ R2 {5} because the elements in the set both add to the same value and {5}R1 ∪ R2 {2} because the sets are the same cardinality. However, {1, 4} is not in relation to {2} under R1 ∪ R2 . Hence, the union of two transitive relations is not necessarily transitive. c) R1 4R2 cannot be an equivalence relation since it is not reflexive. For all a ∈ S, the pair (a, a) is in both R1 and in R2 . Hence, the pair (a, a) does not occur in R1 4R2 . Exercise: 27 Section 1.3 Question: Which of the following collections of subsets of the integers for partitions? If it is not a partition, explain which properties fail. 1. {pZ | p is prime}, where kZ means all the multiples of k. 2. {{3n, 3n + 1, 3n + 2} | n ∈ Z}. 3. {{k | n2 ≤ k ≤ (n + 1)2 } |n ∈ N}.

CHAPTER 1. SET THEORY 4. {{n, −n} | n ∈ N}.

Solution: Testing to satisfy the properties of a partition. a) The set of subsets {pZ | p is prime} is not a partition of Z since for example 6 ∈ 2Z ∩ 3Z, so the subsets are not disjoint. Also, the union of all these sets is not all of Z but Z − {−1, 1}. b) The set of subsets {{3n, 3n + 1, 3n + 2} | n ∈ Z} is a partition of Z. Consider the function f : Z → Z defined by f (m) = bm/3c. It is easy to see that {3n, 3n + 1, 3n + 2} = f −1 (n). Since f is a function, the union of all f −1 (n) gives Z. Furthermore, since an element in Z does not map via f to distinct n values, these pre-image sets are disjoint. c) This is not a partition because for example {1, 2, 3, 4} is one set in the partition as is {4, 5, 6, 7, 8, 9} and these distinct sets are not mutually disjoint. The collection of subsets is not a partition of Z for the additional reason that it does not cover all of Z. In fact, [ {n2 , n2 + 1, . . . , (n + 1)2 } = N. n∈N

d) This collection of subsets is a partition. Consider the equivalence relation on Z defined by a ∼ b if and only if |a| = |b|. This is indeed an equivalence relation and the equivalence classes are precisely subsets of Z of the form {−n, n}. Exercise: 28 Section 1.3 Question: Let S be a set. Prove that there is a bijection between the set of partitions of S and the set of equivalence classes on S. Solution: Let f be a function from the set of partitions of S to the set of equivalence classes on S such that f (A) = R. Let R be an equivalence relation on S and assume there does not exist A over S such that f (A) = R. However, by proposition 1.3.12 we know all the distinct equivalence classes of R are disjoint and their union is equal to S. This creates a contradiction because it satisfies the definition of a partition. Hence, for every equivalence relation R on S, there must exist A where f (A) = R. Therefore, f is surjective. Now assume there exists partitions A = {Ai }i∈I and B = {Bj }j∈J such that A = 6 B and f (A) = f (B) = R. This would imply every Ai and Bj represents a distinct equivalence class of R by proposition 1.3.14. However, since A 6= B there must exist some Ai and Bj where Ai ∩ Bj 6= Ai and Ai ∩ Bj 6= ∅. This creates a contradiction by proposition 1.3.12 since the distinct equivalence classes of any equivalence relation are disjoint. Therefore, f must also be injective which establishes a bijection between the set of partitions of S and the set of equivalence classes on S.

Exercise: 29 Section 1.3 Question: Call p(n) the number of equivalence relations (equivalently, by Exercise 1.3.28, partitions) on a set of cardinality n. (The numbers p(n) are called the Bell numbers after the Scottish-born mathematician E. T. Bell.) a) (*) Prove that p(0) = 1 and that for all n ≥ 1, p(n) satisfies the condition n−1 X

n−1 p(n) = p(n − j − 1) . j j=0 b) Use the previous part to calculate p(n) for n = 1, 2, 3, 4, 5, 6, 7. Solution: Call p(n) the number of partitions that exist on the set {1, 2, . . . , n}. This will be the same number of partitions on any set of size n. a) The value p(0) = 1 comes from the comment that the empty set satisfies all the conditions for an equivalence relation on the empty set itself. Suppose that we know the value of p(k) for 0 ≤ k ≤ n − 1. To determine p(n), we count up the number of possible partitions based on how many elements are in the equivalence class of n besides n. In other words, let j = |[n]−{n}|. The index j = 0 corresponds to the equivalence class [n] being the singleton set {n} and the index j = n − 1, corresponds to the situation where the equivalence class [n] = {1, 2, . . . , n}. Now for any given j, there are n−1 ways to choose the remaining elements in the j

1.3. EQUIVALENCE RELATIONS

equivalence class of [n]. Furthermore, for each of those choices, there are n − 1 − j elements remaining in {1, 2, . . . , n} from which to create the remaining equivalence classes that make up the partition. Thus, for each j, there are p(n − 1 − j) n−1 partitions. Summing over j = 0 to n − 1 gives the number of possible j partitions (equivalence classes) on {1, 2, . . . , n}. b) Using this recursive formula, we get n p(n)

1 1

2 2

3 5

4 15

5 52

6 203

7 877

Exercise: 30 Section 1.3 Question: Consider the relation ∼ on R defined by x ∼ y if y − x ∈ Z. a) Prove that ∼ is an equivalence relation. b) Prove that if a ∼ b and c ∼ d, then (a + c) ∼ (b + d). c) Decide with a proof or counter-example whether ac ∼ bd, whenever a ∼ b and c ∼ d. Solution: a) First, we observe that x − x = 0 for any x ∈ R. Since 0 ∈ Z, ∼ is reflexive. Suppose ∼ is symmetric. Then for any x, y ∈ R if x ∼ y, then y − x = z where z ∈ Z. Rearranging we find that x − y = −z which establishes that ∼ is symmetric. For transivity, suppose that a, b, c ∈ R such that a ∼ b and b ∼ c. Then b − a = x and c − b = y where x, y ∈ Z. Setting c = b + y and solving we find, b−a=x b+y−a=x+y c−a=x+y Since x + y is always an integer, we conclude ∼ is transitive. Therefore, ∼ is an equivalence relation. b) Notice, b − a = x and d − c = y where x, y ∈ Z. b−a=x b−a+y =x+y b−a+d−c=x+y (b + d) − (a + c) = x + y Therefore, since x + y ∈ Z, (a + c) ∼ (b + d). c) Find any counter-example. Let a = π, b = π, c = 1, and d = 2. Then, a ∼ b and c ∼ d, yet ac ∼ bd = π. Since π 6∈ Z, ac 6∼ bd. Exercise: 31 Section1.3 Question: Let S be a set and let A = {Ai }i∈I be a partition of S. Another partition B = {Bj }j∈J is called a refinement of A if ∀j ∈ J , ∃i ∈ I, Bj ⊆ Ai . Let A and B be two partitions of a set S and let ∼A (resp. ∼B ) as the equivalence relation corresponding to A (resp. B). Prove that B is a refinement of A if and only if s1 ∼B s2 =⇒ s1 ∼A s2 . Solution: Suppose that B is a refinement of the partition A. Suppose that s1 ∼B s2 . This is equivalent to the statement that s1 and s2 are both in Bj for some index j ∈ J . Since B is a refinement of A, then Bj ⊆ Ai for some i ∈ I, and therefore, s1 and s2 are both in this Ai . Hence s1 ∼A s2 . Conversely, suppose that ∀s1 , s2 ∈ S, s1 ∼B s2 −→ s1 ∼A s2 . Consider a given subset Bj in the partition B and let s ∈ Bj . Since A is a partition of S, then s ∈ Ai for some index i ∈ I. For all s0 ∈ Bj , we have s ∼B s0 and so by our hypothesis, s ∼A s0 . Consequently, s0 ∈ Ai and this for all s0 ∈ Bj . Thus Bj ⊆ Ai . This establishes that B is a refinement of A. Exercise: 32 Section 1.3 Question: Let S be a set and let A = {Ai }i∈I and B = {Bj }j∈J be two partitions of S. Prove that the collection of sets {Ai ∩ Bj | i ∈ I and j ∈ J } − {∅}

CHAPTER 1. SET THEORY

is a partition of S. Solution: Call C the collection of subsets of S {Ai ∩ Bj | i ∈ I and j ∈ J } − {∅} Let s be any element in S. Since A and B are partitions of S, there exists a unique i0 ∈ I and a unique j0 ∈ J such that s ∈ Ai0 and s ∈ Bj0 . Then s ∈ Ai0 ∩ Bj0 and hence the union of subsets in C is all of S. Now consider Ai1 ∩ Bj1 and Ai2 ∩ Bj2 sets in C and suppose that (Ai1 ∩ Bj1 ) ∩ (Ai2 ∩ Bj2 ) 6= ∅. Then by associativity (Ai1 ∩ Ai2 ) ∩ (Bj1 ∩ Bj2 ) 6= ∅. However, Ai1 ∩ Ai2 6= ∅ if and only if i1 = i2 and similarly Bj1 ∩ Bj2 6= ∅ if and only if j1 = j2 . Hence, we have i1 = i2 and j1 = j2 . Thus sets in C are either equal or disjoint. Consequently, since C also covers S, C is a partition of S. Exercise: 33 Section 1.3 Question: Let S be a set and let R be any relation on S. Design an algorithm that determines the smallest equivalence relation on S that contains the relation R. Solution: There are a variety of ways to accomplish this depending on the context and, if working computationally with a finite set S, how we store the equivalence relation. From a purely theoretical standpoint, we can deduce that a smallest equivalence relation on S that contains S exists by referring to Exercise 1.3.26 and generalizing. It is not hard to prove that the intersection of any collection of equivalence relations on S is again an equivalence relation on S. Hence, we can define the smallest equivalence relation on S containing R as \ Re Re : R⊆Re

where the intersection is over all equivalence relations Re that contain R. We can call this relation the equivalence closure of R. From an algorithmic perspective, one of the challenges of this exercise is to realize that if we begin with the relation R as a subset of S × S, and adjoin pairs to force symmetry and then adjoin more pairs to force transitivity, we may need to go back and adjoin new pairs that are required for symmetry again and vice versa. It is not clear when this process will terminate. Suppose that |S| = n and label the elements of S by S = {s1 , s2 , . . . , sn }. For an n × n matrix M of nonnegative integers, we define M̃ as m̃ij = min(1, mij ). Hence, if mij ≥ 1, then m̃ij = 1 but if mij = 0, then m̃ij = 0. Here is an algorithm for determining the equivalence closure of R. • Let A = (aij ) be the n × n matrix defined by ( 1 aij = 0

if (si , sj ) ∈ R otherwise.

• Replace A with A + I. • Replace A with Ã. [These first two steps ensure reflexivity.] • While A 6= A2 ^ + (A2 )> , replace A with A2 ^ + (A2 )> . • Return A. The operation A2 will have a nonzero entry position (i, j), if there is some k such that aik and bkj are both nonzero. This process will add a nonzero entry corresponding to a pair that is required by transitivity. The operation A → A + A> adds a matrix to its transpose, which adds a nonzero entry to complete for symmetry reasons. Now if A is a matrix of 0s and 1s, then A2 ^ + (A2 )> will again be a matrix of 0s and 1s with new entries turned to 1 for transitivity or symmetry reasons.

1.4. PARTIAL ORDERS

The algorithm stops because if A = A2 ^ + (A2 )> then no transitivity requirement or symmetry requirement will add a new pair to the relation (nonzero entry to A). Hence, A will then correspond to an equivalence relation. Furthermore, the algorithm will terminate because before the while loop, A contains at most n2 − n entries that are 0 and at each stage of the while loop that changes A will change at least one 0 entry to a 1. Hence, the while loop can repeat at most n2 − n times.

1.4 – Partial Orders Exercise: 1 Section 1.4 Question: Let S = {a, b, c, d, e} (where we consider all the labels unique elements). In the following relations on S determine with explanation whether or not the relation is a partial order. If it fails antisymmetry then remove a least number of pairs and if it fails transitivity then add some pairs to make the relation a partial order. 1. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c)}. 2. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (a, d)}. 3. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (d, a)}. 4. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (b, c), (c, d), (d, e), (a, e)}. Solution: Consider each partial order. 1. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c)}. This relation is reflexive. The only pair in the relation not of the form (x, x) is (a, c). The pair (c, a) is not in the relation so the relation is antisymmetric. For the same reason, the relation is also transitive. 2. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (a, d)}. For the same reasons as the previous part, this relation is a partial order. 3. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (a, c), (d, a)}. In this example, the relation is again reflexive and antisymmetric but it is not transitive because of the pairs (d, a) and (a, c). In the modified relation R0 = R ∪ {(d, c)}, we now have transitivity and R0 still has antisymmetry. 4. R = {(a, a), (b, b), (c, c), (d, d), (e, e), (b, c), (c, d), (d, e), (a, e)}. This relation satisfies reflexivity and antisymmetry but fails transitivity. In order to get transitivity, we need add the pairs (b, d), (c, e), and (b, e). Then R ∪ {(b, d), (b, e), (c, e)} is a partial order. Exercise: 2 Section 1.4 Question: In microeconomics (the study of consumer behavior), one considers consumer’s utility (preference) in regards to pairs of commodities. Let (q1 , q2 ) ∈ N2 be a pair of nonnegative integers representing quantities of two commodities. Explain why, given two specific commodities and a given consumer, the relation of preferable (or equal) is a partial order. Solution: When a consumer prefers the pair of commodities in the quantities (q10 , q20 ) over (q1 , q2 ) (or these are equal), we write (q1 , q2 ) 4 (q10 , q20 ). Note that this is a partial order on N2 , where the ith entry represents the quantity of the ith commodity. By including the equality of pairs into the relation, the relation is reflexive. It is in people’s psychology that if (q1 , q2 ) 4 (q10 , q20 ) and (q10 , q20 ) 4 (q100 , q200 ), so the concept of preference is transitive. We do not have (q1 , q2 ) 4 (q10 , q20 ) and (q10 , q20 ) 4 (q1 , q2 ) at the same time unless forced by the requirement that the pairs are equal. So preference, with the additional assumption of including equality, is a partial order. Note that in the concept of preference, given two pairs (q1 , q2 ) and (q10 , q20 ) it is perfectly possible to not prefer one over the other. Such pairs would be incomparable. Exercise: 3 Section 1.4 Question: Let S = R>0 × R>0 be the positive first quadrant in the Cartesian plane. Consider the relation R on S defined by (x1 , y1 ) R (x2 , y2 ) =⇒ x1 y1 ≥ x2 y2 Prove or disprove that R is a partial order. Solution: We check the three axioms for a partial order.

CHAPTER 1. SET THEORY

Reflexivity: For all (x, y) ∈ S, we do have xy ≤ xy so the relation is reflexive. Antisymmetry: Consider the points (2, 1) and (1, 2). Then 1 × 2 ≤ 2 × 1 and 2 × 1 ≤ 1 × 2 so (1, 2) R (2, 1) and (2, 1) R (1, 2) even through (1, 2) 6= (2, 1) So the relation is not antisymmetric. Transitivity: We have already shown that the relation is not a partial order since it fails antisymmetry. The relation is transitive. Not a partial order. Exercise: 4 Section 1.4 √ √ Question: Prove that for any real x > 2, the inequality 2 < 12 x + x2 < x holds. √ √ Solution: Since 2 < x, then x1 < √12 , which implies x2 < 2 < x. So 1 2 Also, from x 6=

√

2, we have (x −

√

2 x

1 (x + x) = x. 2

2)2 > 0, which is equivalent to

√ √ 1 x − 2 2x + 2 > 0 ⇐⇒ x2 + 2 > 2 2x ⇐⇒ 2 2

√ 2 x+ > 2. x

The result follows. Exercise: 5 Section 1.4 Question: Let (S, 4) be a partial order in which every element has an immediate successor. Prove that it is not necessarily true that for any two elements a 4 b that any chain between a and b has finite length. n o n o Solution: Consider the subset of (Q, ≤) with the set S = 1 − n1 n ∈ N∗ ∪ 1 + n1 n ∈ N∗ . In the poset 1 (S, ≤), every element has an immediate successor: the immediate successor of 1− n1 is 1− n+1 , and the immediate 1 1 successor of an element of the form 1 + n is 1 + n−1 . By construction S is a chain since it is a total order. Furthermore, 0, 2 ∈ S, so it is an infinite chain between 0 and 2, such that every element has an immediate successor.

Exercise: 6 Section 1.4 Question: Prove the three claims about properties of 4 in Example 1.4.8. Prove that Q≥0 is countable. Conclude that Q is countable. Solution: Consider the sets described in Example 1.4.8. Since |An | ≤ n, each set is finite. Also, the collection of sets An is countable. Furthermore, we claim that the sets An partition Q>0 . Indeed for all fractions xy , expressed in reduced form, we have xy ∈ Ax+y−1 . We can set up a bijection f : N∗ → Q>0 as follows. Define `1 = 1 and then for all positive integers k, set `k = |A1 | + · · · + |Ak |. Set f (1) = 1 and then for all integers m with `k < m ≤ `k+1 , define f (m) as the (m − `k )th element (ordered by ≤) in Ak . This function is injective since the Ak are mutually disjoint and is surjective since {Ak } cover Q>0 . We can now define a bijection between F : N → Q by F (0) = 0 and m+1 m F (m) = (−1) f . 2

Exercise: 7 Section 1.4 Question: Let S be a set. Show that the relation of refinement is a partial order on the set of partitions of S. Solution: Let S be a set. Recall that a refinement of a partition A = {Ai }i∈I of S is another partition B = {Bj }j∈J such that for all j ∈ J, there exists an i ∈ I such that Bj ⊆ Ai . We will write B 4 A if B is a refinement of A. 1. For a partition A = {Ai }i∈I of S, for each i ∈ I we have Ai ⊆ Ai so A 4 A.

1.4. PARTIAL ORDERS

2. Suppose that B 4 A and A 4 B. Then for all j ∈ J, there exists an i ∈ I such that Bj ⊆ Ai . However, for this index i, there exists j 0 ∈ J such that Ai ⊆ Bj 0 . Hence Bj ⊆ Ai ⊆ Bj 0 . However, since the sets in B are mutually disjoint, we conclude that j = j 0 . Hence Bj = Ai . Since j was arbitrary, we conclude that B = A. Thus the relation of refinement is antisymmetric. 3. Finally, let B be a refinement of A and let C = {Ck }k∈K be a partition of S such that C 4 B. Then for all k ∈ K, there exists j ∈ J such that Ck ⊆ Bj . Since B is a refinement of A, then there exists i ∈ I such that Bj ⊆ Ai . Hence, since ⊆ is transitive, Ck ⊆ Ai . Thus C 4 A. Hence, the relation of refinement is transitive. These three results show that refinement is a partial order on the set of partition of S. Exercise: 8 Section 1.4 Question: Draw the Hasse diagram of the partial order ⊆ on P({1, 2, 3, 4}). Solution: The Hasse diagram of (P({1, 2, 3, 4}), ⊆) is {1, 2, 3, 4}

{1, 2}

{1, 2, 3}

{1, 2, 4}

{1, 3, 4}

{2, 3, 4}

{1, 3}

{1, 4}

{2, 3}

{2, 4}

{1}

{2}

{3}

{4}

{3, 4}

∅

Exercise: 9 Section 1.4 Question: Draw the Hasse diagram for the poset ({1, 2, 3, 4, 5, 6}, ≤). Solution: The Hasse diagram of ({1, 2, 3, 4, 5, 6}, ≤) is 6 5 4 3 2 1

Exercise: 10 Section 1.4 Question: Let A = {a, b, c, d, e, f, g}. Draw the Hasse diagram for the partial order 4 given as a subset of A × A as 4 = {(a, a), (b, b), (c, c), (d, d), (e, e), (f, f ), (g, g), (a, c), (b, c), (d, g), (a, e), (b, e), (c, e), (d, h), (g, h)}

CHAPTER 1. SET THEORY

Solution: The Hasse diagram of (A, 4) is e

h g

c a

Exercise: 11 Section 1.4 Question: A person’s blood type is usually listed as one of the eight elements in the set B 0 = {o+, o−, a+, a−, b+, b−, ab+, ab−}. We define the donor relation → on B 0 as follows. The relation t1 → t2 holds if the letter portion of the blood type donates according to the way described in the examples for this section and if someone with a + designation can only give to someone else with +, while someone with − can give to anybody. 1. Draw the Hasse diagram for (B 0 , →). 2. Show that the (B 0 , →) poset does not have the lexicographic order on B × {+, −}. Solution: We study the partial order of blood type B 0 including the rhesus. a) The Hasse diagram for the poset (B 0 , →) is ab+

ab−

a−

b−

o− b) Under the partial order on {+, −} is described completely by + → +, − → −, and − → +. So for example, in the lexicographic order on B 0 , we have (a, +) →lex (ab, −) because the pairs already differ on the first entry and a → ab in B. However, we see that in the actual donor relation on B 0 , a+ cannot donate to ab−. Hence the actual donor relation on B 0 is not the lexicographic partial order on B × {+, −}. Exercise: 12 Section 1.4 Question: Consider the set of triples of integers Z3 . Define the relation 4 on Z3 by ( a1 + a2 + a3 < b1 + b2 + b3 if a1 + a2 + a3 6= b1 + b2 + b3 ; (a1 , a2 , a3 ) 4 (b1 , b2 , b3 ) ⇐⇒ a1 + a2 + a3 4lex b1 + b2 + b3 if a1 + a2 + a3 = b1 + b2 + b3 , where 4lex is the lexicographic order on Z3 (with each copy of Z equipped with the partial order ≤). Prove that 4 is a partial order on Z3 . Prove also that 4 is a total order. Solution: We first prove that 4 is a partial order on Z3 . Reflexivity : Let (a1 , a2 , a3 ) ∈ Z3 . Then since a1 + a2 + a3 = a1 + a2 + a3 , we use the lexicographic order to compare the entries but all entries are equal and this satisfies the lexicographic order. Hence (a1 , a2 , a3 ) 4 (a1 , a2 , a3 ).

1.4. PARTIAL ORDERS

Antisymmetry : Suppose that (a1 , a2 , a3 ) 4 (b1 , b2 , b3 ) and (b1 , b2 , b3 ) 4 (a1 , a2 , a3 ). Assume that a1 + a2 + a3 6= b1 + b2 + b3 , then a1 + a2 + a3 < b1 + b2 + b3 and b1 + b2 + b3 < a1 + a2 + a3 , which is a contradiction. Hence we must have a1 + a2 + a3 = b1 + b2 + b3 . Thus, we compare the triples by lexicographic order. However, the lexicographic order is a partial order, which is antisymmetric so we can conclude that (a1 , a2 , a3 ) = (b1 , b2 , b3 ). Transitivity : Suppose that (a1 , a2 , a3 ) 4 (b1 , b2 , b3 ) and (b1 , b2 , b3 ) 4 (c1 , c2 , c3 ). We can break the situation into three cases. If a1 + a2 + a3 = b1 + b2 + b3 = c1 + c2 + c3 , then we compare the triples by lexicographic order, which is transitive so (a1 , a2 , a3 ) 4 (c1 , c2 , c3 ). If a1 + a2 + a3 = b1 + b2 + b3 6= c1 + c2 + c3 (resp. a1 + a2 + a3 6= b1 + b2 + b3 = c1 + c2 + c3 ) then a1 + a2 + a3 < c1 + c2 + c3 so (a1 , a2 , a3 4 (c1 , c2 , c3 ). Finally, if all thee of the sums are different, then we deduce that a1 + a2 + a3 < b1 + b2 + b3 < c1 + c2 + c3 so we can conclude that (a1 , a2 , a3 4 (c1 , c2 , c3 ). We conclude that 4 is transitive. Finally, to show that 4 is a total order, let (a1 , a2 , a3 ), (b1 , b2 , b3 ) ∈ Z3 be arbitrary, distinct elements. There are two cases. If a1 + a2 + a3 6= b1 + b2 + b3 , then either a1 + a2 + a3 < b1 + b2 + b3 , which implies that (a1 , a2 , a3 ) 4 (b1 , b2 , b3 ), or the reverse is true. If a1 + a2 + a3 = b1 + b2 + b3 , then we compare the triples by the lexicographic order. In this case, let i be the least index for which ai 6= bi . Then (a1 , a2 , a3 ) 4 (b1 , b2 , b3 ) if ai < bi and (b1 , b2 , b3 ) 4 (a1 , a2 , a3 ) if bi < ai . Hence, every pair of elements is comparable and the relation is a total order. Exercise: 13 Section 1.4 Question: Let (Ai , 4i ) be posets for i = 1, 2, . . . , n and define 4lex as the lexicographic order on A1 ×A2 ×· · · An . Prove that 4lex is a total order if and only if 4i is a total order on Ai for all i. Solution: First suppose that 4i is a total order on Ai for all i. Let (a1 , a2 , . . . , an ) and (b1 , b2 , . . . , bn ) be elements in A1 × A2 × · · · An . If ai = bi for i = 1, . . . , n, then (a1 , a2 , . . . , an ) 4lex (b1 , b2 , . . . , bn ). Otherwise, let j be the least index for which ai = bi . Since all 4i are total orders, then 4j is a total order. Thus, either aj 4j bj or bj 4j aj . Hence, (a1 , a2 , . . . , an ) 4lex (b1 , b2 , . . . , bn ) or the reverse is true. Thus 4lex is a total order. Now suppose that 4lex is a total order. Let j be any index with 1 ≤ j ≤ n and let aj , bj ∈ Aj . Consider a pair of n-tuples (a1 , a2 , . . . , an ) and (b1 , b2 , . . . , bn ) such that ai = bi for all i < j. Since (a1 , a2 , . . . , an ) and (b1 , b2 , . . . , bn ) are comparable in 4lex , then aj 4j bj or bj 4j aj . Since aj , bj were arbitrary, then 4j is a total order. Thus, we conclude that all the partial orders 4i are partial orders. Exercise: 14 Section 1.4 Question: Let 4 be the lexicographic order on R3 , where each R is equipped with the usual ≤. Prove or ~ if ~a 4 ~b and ~c 4 d, ~ then ~a + ~c 4 ~b + d. ~ disprove the following statement: For all vectors ~a, ~b, ~c, d, ~ ~ Solution: We first prove that if ~a 4 b, then ~a + ~c 4 b + ~c. With the lexicographic order, ~a 4 ~b if and only if the first index j ∈ {1, 2, 3} for which aj 6= bj has aj < bj . For any ~c ∈ R3 , for all indices ai = bi if and only ai + ci = bi + ci . Hence the first index for with ai + ci 6= bi + ci is j and then we have aj + cj < bj + cj . Thus ~a + ~c 4 ~b + ~c. Since the above result was arbitrary, ~a 4 ~b implies ~a +~c 4 ~b +~c and ~c 4 d~ implies ~c +~b 4 d~+~b. By transitivity of 4, we deduce that ~ ~a + ~c 4 ~b + ~c 4 ~b + d.

Exercise: 15 Section 1.4 Question: Answer the following questions pertaining to the poset described by the Hasse diagram below. 1. List all the minimal elements. 2. List all the maximal elements. 3. List all the maximal elements in the subposet with {a, b, c, d, e, f, g}. 4. Determine the length of the longest chain and find all chains of that length. 5. Find the least upper bound of {a, b}, if it exists. 6. Find the greatest lower bound of {b, c}, if it exists.

CHAPTER 1. SET THEORY j i

h g

e c

d a

7. List all the upper bounds of {f, d}. Solution: In the given Hasse diagram, we have the following named elements. a) The minimal elements are a and b. b) The maximal element is j. c) The maximal elements in {a, b, c, d, e, f, g} are e, f , and g. d) There are 3 chains of length 5. They are {a, d, e, i, j}, {a, d, g, h, j}, and {a, c, f, h, j}. There is no chain of greater length. e) The subposet {a, b} has only one upper bound, namely e, and this is the least upper bound. f) The subposet {b, c} does not have a lower bound. g) The set of upper bounds of {f, d} is {h, j}. Exercise: 16 Section 1.4 Question: Consider the partial order on R2 given in Example 1.4.6. Let A be the unit disk A = {(x, y) ∈ R2 | x2 + y 2 ≤ 1}. a) Show that A has both a maximal and minimal element. Find all of them. b) Find all the upper bounds and all the lower bounds of A. Solution: The partial order on R2 is defined by (x1, y1) 4 (x2, y2) if and only if 2x1 − y1 < 2x2 − y2 or (x1, y1) = (x2, y2). a) The solution to this problem is directly related to the calculus problem of optimizing 2x − y for (x, y) ∈ A. The gradient of 2x − y is never 0 so there are no optimal values to 2x − y on the interior of A. We can parametrize the boundary of A by (cos t, sin t) with t ∈ [0, 2π]. We can optimize 2x − yon the boundary by optimizing 2 cos t − sin t. This is optimized with tan t = − 21 . With the result that sin t = − 12 cos t, we deduce that the optimum values occur at 2 1 2 1 √ , −√ √ √ and − , 5 5 5 5 with the former corresponding to a maximum and the latter being a minimum element with respect to 4. √ b) The upper bounds to A are any (x, y) with 2x − y > √55 = 5 as well as the point √25 , − √15 . The lower √ bounds of A are all the points (x, y) with 2x − y < − 5 as well as the point − √25 , √15 . Exercise: 17 Section 1.4 Question: Consider the lexicographic order on R2 coming from the standard (R, ≤). Let A be the closed disk of center (1, 2) and radius 5. 1. Show that A has both a maximal and minimal element. Find all of them. 2. Find all the upper bounds and all the lower bounds of A. 3. Show that A has both a least upper bound and a greatest lower bound.

1.4. PARTIAL ORDERS

Solution: The lexicographic order on R2 coming from the standard (R, ≤) is a total order. a) A maximal element of A will have a greatest x value and if there are any ties on the x value, we break them with the y value. The maximal element is the point (6, 2). No point in A has a greater x-value. Similarly, the point with the least x value is (−4, 2) and there is no other point with the same x component. Hence (−4, 2) is minimal. b) The set of upper bounds to A is {(x, y) ∈ R2 | x > 6} ∪ {(6, y) | y ≥ 2}. The set of lower bounds of A is {(x, y) ∈ R2 | x < −4} ∪ {(−4, y) | y ≤ 2}. c) The single maximal element is the unique least upper bound to A and the single minimal element is the unique greatest lower bound. Exercise: 18 Section 1.4 Question: Prove that in a finite lattice, there exists exactly one maximal element and one minimal element. Solution: Let (S, 4) be a finite lattice. We first prove that a maximal element exists. Since S is finite every chain in S is finite. Consequently, there exists a chain C of maximal length. We can consider the set of positive integers defined by {|{y ∈ C | x 4 y}| | x ∈ C}. By the well-ordering of the integers, this set must have a least element and this least element must be 1. The element M that gives this least element satisfies |{y ∈ C | M 4 y}|. Hence, the only element y such that M 4 y is M itself, which means that M is maximal. Let M1 and M2 be two maximal elements. Let M be a least upper bound to M1 and M2 . In particular, M1 4 M and M2 4 M . Since M1 and M2 are maximal, then M1 = M = M2 . Hence, the maximal element is unique. A similar reasoning holds with minimal elements and greatest lower bounds. Hence, S contains a unique minimal element. Exercise: 19 Section 1.4 Question: Let (B, →) be the poset of blood types equipped with the donor relation. (See Example 1.4.4.) a) Consider the poset ({1, 2, 3}, ≤). Show that the function f : B −→ {1, 2, 3} defined by f (o) = 1, f (a) = 2, f (b) = 2 and f (ab) = 3 is a monotonic function. b) Show that there exists no isomorphism between (B, →) and ({1, 2, 3, 4}, ≤). Solution: Let (B, →) be the poset of blood types. a) It is obvious that for all x ∈ B, we have f (x) ≤ f (x). Consequently, we only need to check the monotonic property on unequal elements x and y that satisfy x → y. The five unequal pairs of donating relation give the following output by f . in {1, 2, 3} true of false in B o→a 1≤2 T o→b 1≤2 T o → ab 1≤3 T a → ab 2≤3 T b → ab 2≤3 T Thus, we have exhaustively checked that f is monotonic. b) Let h be a bijection from ({1, 2, 3, 4}, ≤) to (B, →). Let x and y be the elements in {1, 2, 3, 4} such that h(x) = a and h(y) = (b). The elements x and y are distinct since h is a bijection. Now since ≤ is a total order, x ≤ y or y ≤ x. However, neither a → b nor b → a. Thus, no bijection can be monotonic. Exercise: 20 Section 1.4 Question: Let (S, 4), (T, 40 ), and (U, 400 ) be three posets. Let f : S → T and g : T → U be monotonic functions. Prove that the composition g ◦ f : S → U is monotonic. Solution: Let x, y ∈ S with x 4 y. Since f is monotonic, then f (x) 40 f (y). Now since g is monotonic, then g(f (x)) 400 g(f (y)). Thus we have proved that x 4 y =⇒ (g ◦ f )(x) 400 (g ◦ f )(y). Hence, the composition g ◦ f is monotonic.

CHAPTER 1. SET THEORY

Exercise: 21 Section 1.4 Question: Prove that the poset (R, ≤) is not isomorphic to (R − {0}, ≤). Solution: Suppose that f : R → R − {0} is an isomorphism from the poset (R, ≤) to (R − {0}, ≤). Let a, b ∈ R. For all x such that a ≤ x ≤ b, we have f (a) ≤ f (x) ≤ f (b). Furthermore, for all y with f (a) ≤ y ≤ f (b), we also have a ≤ f −1 (y) ≤ b. Hence, the interval [a, b] is mapped to the interval [f (a), f (b)]. Let a and b be such that f (a) = −1 and f (b) = 1. Then f ([a, b]) is the interval [−1, 1]. However, [−1, 1] is not a subset of R − {0}. Exercise: Question: Prove that the poset of integers greater that a fixed number k (with partial order ≤) is isomorphic to the (N, ≤). Solution: It is obvious that f : N → {k + 1, k + 2, . . .} defined by f (n) = n + k + 1 is a bijection. Furthermore, for all m, n ∈ N, we have m ≤ n implies m + k + 1 ≤ n + k + 1. The result follows. Exercise: 23 Section 1.4 Question: Let (S, 41 ) and (T, 42 ) be two partially ordered sets and let f : S → T be a monotonic function. a) Prove that if A is a subset of S with an upper bound u, then f (u) is an upper bound of f (A). b) Prove with a counterexample that f (lub(A)) is not necessarily equal to lub(f (A)). c) Prove that if f is an isomorphism, then f (lub(A)) = lub(f (A)). Solution: Let (S, 41 ) and (T, 42 ) be two partially ordered sets and let f : S → T be a monotonic function. a) Since u is an upper bound of A, then x 41 u for all x ∈ A. Hence, f (x) 42 f (u) for all x ∈ A, or in other words, y 42 f (u) for all y ∈ f (A). Thus f (u) is an upper bound of f (A). b) Consider the function tan−1 : R → R and A = R. Then lub(f (A)) = π2 whereas lub(A) does not exist so f (lub(A)) does not exist either. c) Suppose now that f is surjective and let u = lub(A). We know that f (u) is an upper bound of f (A). Let y 0 be another upper bound of f (A). Since f is surjective, there exists u0 ∈ S such that f (u0 ) = y 0 . Since b 42 y 0 for all b ∈ f (A), then since f is an isomorphism, a 41 u0 for all a ∈ A. Thus u0 is also an upper bound of A. Hence u 41 u0 . Thus, f (u) 42 y 0 . We conclude that f (u) is a least upper bound of f (A). Exercise: 24 Section 1.4 Question: Prove or disprove that (Z, ≤) and (Q, ≤) are isomorphic as posets. Solution: Suppose that h is an isomorphism from a poset (S, 41 ) to (T, 42 ). Suppose that y is an immediate successor to an element x in S. Then x 41 y and x 6= y and if z is any element such that x 41 x 41 y, then z = x or z = y. Then h(x) 6= h(y) and h(x) 42 h(y). Furthermore, for all z 0 such that h(x) 42 z 0 42 h(y), then since h−1 is also monotonic we deduce that x 41 h−1 (z 0 ) 41 y. Thus h−1 (z 0 ) = x, which implies that z 0 = h(x) or h−1 (z 0 ) = y, which implies that z 0 = h(y). Hence, if y is an immediate successor to x, then h(y) is an immediate successors to h(x). In this particular example, every element in (Z, ≤) has an immediate successor but no element in the poset (Q, ≤) has an immediate successor. Hence, they cannot be isomorphic as posets. Exercise: 25 Section 1.4 Question: Determine whether the posets corresponding to the following Hasse diagrams are lattices. If they are not, explain why. (a)

(b) g

(c)

(d)

f d

1.4. PARTIAL ORDERS

Solution: a) This is a lattice. b) This is not a lattice. Consider the pair {b, c}. The set of upper bounds is {e, f, g, h}. We note that e and f are incomparable and hence there is no upper bound u such that u 4 u0 for all other upper bounds u0 . c) This is a lattice. d) This is not a lattice. The set {d, e} does not have a greatest lower bound. Exercise: 26 Section 1.4 Question: Explain under what conditions a flow chart may be viewed as a partial order. Solution: A flow chart is a list of instructions to accomplish a certain task (or answer a certain question) where individual instructions may depend on the answers to intermediate questions. This exercise is simply asking to compare the possible structure of a flow chart to that of a Hasse diagram. If a flow chart can be viewed as a partial order, then any list of followed instructions is a chain. But in a poset, a chain cannot be a loop. Hence, a flow chart may be viewed as a partial order if the flow chart does not have any possible sequence of decisions that leads to repeating the same instruction twice. Exercise: 27 Section 1.4 Question: Let (S, 4) and (T, 42 ) be two partial orders. Suppose that ∼ is an equivalence relation on S that satisfies Condition (1.6). Prove that for any monotonic function f : S → T such that f (a) = f (b) whenever a ∼ b, there exists a unique monotonic function f 0 : S/ ∼ → T such that f = f 0 ◦ p, where p : S → S/ ∼ is the projection p(a) = [a] and the partial order on S/ ∼ is defined in (1.7). In the terminology of diagrams, prove that the diagram below is commutative. (S, 4)

(S/ ∼, 40 ) f0 (T, 42 )

Solution: Suppose that f : S → T is a monotonic function such that f (a) = f (b) whenever a ∼ b. Define the function f 0 : S/ ∼ T by f 0 ([a]) = f (a). This function is well-defined since if b ∼ a, then f (b) = f (a), so the definition of f 0 is independent of the representative of the equivalence class. This function is monotonic since [a] 40 [c] if and only if there exist a0 and c0 such that a0 ∼ a and c0 ∼ c and a0 4 c0 . But then f (a0 ) 42 f (c0 ) so f 0 ([a]) 42 f 0 ([c]). Note that f 0 is defined so that f 0 ◦ p = f . Let f˜ be any function f˜ : S/ ∼→ T satisfying the same relations as f 0 . Then for all equivalence classes [a] ∈ S/ ∼, we have f˜([a]) = f (a) = f 0 ([a]). Hence f 0 = f˜. So the function is unique. Exercise: 28 Section 1.4 Question: Let R1 and R2 be partial orders on a set S. a) Prove that R1 ∩ R2 is a partial order. b) Show by a counterexample that R1 ∪ R2 is not necessarily a partial order. Solution: Let R1 and R2 be partial orders on a set S. We consider the R1 and R2 as subsets of S × S. a) Reflexivity: Let x ∈ S; then (x, x) ∈ R1 and (x, x) ∈ R2 so (x, x) ∈ R1 ∩ R2 . Antisymmetry: suppose that (x, y) ∈ R1 ∩ R2 and (y, x) ∈ R1 ∩ R2 ; then x = y since (x, y) ∈ R1 and (y, x) ∈ R1 and R1 is a partial order. Transitivity: Let (x, y), (y, z) ∈ R1 ∩ R2 ; then (x, z) ∈ R1 since R1 is a transitive and (x, z) ∈ R2 since R2 is transitive so (x, z) ∈ R1 ∩ R2 . b) Let R1 be the partial order of ≤ on N and let R2 be the partial order of ≥ on the same set. Then R1 ∪ R2 is the relation that relates everything in N to everything else. This relation is not antisymmetric. Exercise: 29 Section 1.4 Question: Consider the poset (N, ≤) and consider the equivalence relation ∼ on N defined by j n k jmk = . n ∼ m ⇐⇒ 10 10

CHAPTER 1. SET THEORY 1. Describe the equivalence classes of ∼ and find a complete set of distinct representatives of ∼. 2. Show that ∼ satisfies the poset quotient condition. 3. Describe the poset (N/ ∼, ≤inh ).

Solution: a) Notice that the ∼ equivalence relation considers nonnegative integers the same if they only differ in their units digit. A complete set of distinct representatives is all integers with 0 as the units digit. In fact, we jnk note that every n ∈ N is ∼-equivalent to 10 . 10 b) Suppose n 6∼ m, which means that n and m do not have all digits equal in the 10 or above places. Suppose also that n ≤ m. Suppose also that n0 ∼ n and m0 ∼ m. Now n0 and m0 satisfy jnk jmk jmk jnk ≤ n0 ≤ 10 + 9 and 10 ≤ m0 ≤ 10 + 9. 10 10 10 10 10 n n n Now n ≤ m but n 6∼ m means that m > 10 10 + 9 so m ≥ 10 10 + 10. In particular, m0 ≥ 10 10 + 10 so m0 > n0 and hence m0 6≤ n0 . c) The quotient set N/ ∼ is in bijection with N where we have effectively ignored the units digit of n. The quotient partial order is again the usual ≤ on N. The overall quotient process ignores the units digit and manages to preserve the ≤. Exercise: 30 Section 1.4 Question: Let S = P({a, b, c, d, e}) and consider the poset (S, ⊆). Consider the equivalence relation ∼ on S that has as its partition o n o n {a} ∪ C, {b} ∪ C, {a, b} ∪ C | C ⊆ {c, d, e} ∪ C | C ⊆ {c, d, e} . (The equivalence relation has the effect of considering a and b as the same element.) Equivalence classes have either one element or three elements. a) Show that ∼ satisfies the poset quotient condition. b) Show that (S/ ∼, ⊆inh ) is isomorphic to a lattice of subgroups for a set of four elements. Solution: a) Suppose that A, B ∈ P({a, b, c, d, e}) such that A and B are inequivalent with A ⊆ B. Suppose also that A ∼ A0 and B ∼ B 0 under the equivalence relation defined in the problem. Case (1), neither A nor B contain a or b. The poset quotient condition is trivially satisfied since we must have A0 = A and B 0 = B so A 6= B and A ⊆ B so B 0 * A0 . Case (2), A contains a or b and B contains neither a nor b. But because of these conditions, we cannot have A ⊆ B since A contains a or b and B does not. Hence, this case never occurs. Case (3), A contains neither a nor b and B contains a or b. Then A0 = A and B 0 also must contain a or b so we cannot have B 0 ⊆ A0 . Case (4) both A and B contain a or b. Since A and B are inequivalent then A ∩ {c, d, e} = 6 B ∩ {c, d, e}. Also since A ⊆ B, then A ∩ {c, d, e} ( B ∩ {c, d, e}. Assume that B 0 ⊆ A0 ; then B ∩ {c, d, e} = B 0 ∩ {c, d, e} ⊆ A0 ∩ {c, d, e} = A ∩ {c, d, e}, which we just showed is not true. Hence B 0 * A0 . In all four cases, we have shown that the equivalence relation satisfies the quotient poset condition. b) Consider the function f : P({a, c, d, e}) → S/ ∼ defined by f (A) = [A], that maps a subset A to its corresponding equivalence class in S/ ∼. It is not hard to see that this is a bijection. Also, it is obvious from the definition of the inherited partial order that f is monotonic. However, we need to prove that f −1 is monotonic. We note that [A] ⊆inh [B] if and only if A ⊆ B if A and B do not both contain a or b and A ∩ {c, d, e} ⊆ B ∩ {c, d, e} otherwise. But ( A if A does not contain a or b f −1 ([A]) = (A ∩ {c, d, e}) ∪ {a} if A contains a or b. In all cases, if [A] ⊆inh [B], then f −1 ([A]) ⊆ f −1 ([B]).

2 | Number Theory 2.1 – Basic Properties of Integers Exercise: 1 Section 2.1 Question: Find the prime factorization of the following integers: (a) 56; (b) 97; (c) 126; (d) 399; (e) 255; (f) 1728 Solution: (a) 56 = 23 × 7; (b) 97=97; (c) 126 = 2 × 32 × 7; (d) 399 = 3 × 7 × 19; (e) 255 = 3 × 5 × 17; (f) 1728 = 26 × 33 . Exercise: 2 Section 2.1 Question: Find the prime factorization of the following integers: a) 111; b) 470; c) 289; d) 743; e) 2345; f) 101010 Solution: (a) 111 = 3 × 37; (b) 470 = 2 × 5 × 47; (c) 289 = 172 ; (d) 743 = 743. Note that as we check various prime factors to see if√they divide 743, the last one we need to check is 23 because it is the largest prime factor less than or equal to 743; (e) 2345 = 5 × 7 × 67; (f) 101010 = 2 × 3 × 5 × 7 × 13 × 37. Exercise: 3 Section 2.1 Question: Draw the Hasse diagram of ({1, 2, 3, . . . , 12}, |). Solution: 8

Exercise: 4 Section 2.1 Question: Let n be a positive integer. Show that the number of edges in the Hasse diagram of ({1, 2, 3, . . . , n}, |) is X n . p p: primes≤n

Solution: In the Hasse diagram of ({1, 2, 3, . . . , n}, |), there is an edge up from a to b if and only if b is a prime multiple of a. Hence, each edge corresponds to a unique prime number. There is an edge corresponding to a prime p out of each integer a ∈ {1, 2, . . . , n} if and only if ap ≤ n. Hence, there j k is an edge corresponding to a

prime p out of each integer a ∈ {1, 2, . . . , n} if and only if a ≤ np . There are n p . Thus the number of edges in the Hasse diagram is X p: primes≤n

n p

integers less than or equal to

n . p

Exercise: 5 Section 2.1 Question: Use the Euclidean Algorithm to find the greatest common divisor of the following pairs of integers. 1. a = 234, and b = 84. 2. a = 5241, and b = 872. 3. a = 1010101, and b = 1221. 43

CHAPTER 2. NUMBER THEORY

Solution: Euclidean Algorithm: a) gcd(234, 84) = 6 because 234 = 84 × 2 + 66 84 = 66 × 1 + 18 66 = 18 × 3 + 12 18 = 12 × 1 + 6 12 = 6 × 2 + 0 and 6 is the last nonzero remainder. b) gcd(5241, 872) = 1 because 5241 = 872 × 6 + 9 872 = 9 × 96 + 8 9=8×1+1 8=1×8+0 and 1 is the last nonzero remainder. c) gcd(1010101, 1221) = 1 because 1010101 = 1221 × 827 + 334 1221 = 334 × 3 + 219 334 = 219 × 1 + 115 219 = 115 × 1 + 104 115 = 104 × 1 + 11 104 = 11 × 9 + 5 11 = 5 × 2 + 1 5=1×5+0

Exercise: 6 Section 2.1 Question: Use the Euclidean Algorithm to find the greatest common divisor of the following pairs of integers. a) a = 55, and b = 34 b) a = 4321, and b = 1234 c) a = 54321, and b = 1728 Solution: a) The Euclidean Algorithm on 55 and 34 gives: 55 = 34 × 1 + 21 34 = 21 × 1 + 13 21 = 13 × 1 + 8 13 = 8 × 1 + 5 8=5×1+3 5=3×1+2 3=2×1+1 2 = 1 × 2 + 0. So the greatest common divisor is gcd(55, 34) = 1.

2.1. BASIC PROPERTIES OF INTEGERS

b) The Euclidean Algorithm on 4321 and 1234 gives: 4321 = 1234 × 3 + 619 1234 = 619 × 1 + 615 619 = 615 × 1 + 4 615 = 4 × 153 + 3 4 = 3 × 1 + 1. This shows that gcd(4321, 1234) = 1. c) The Euclidean Algorithm on 54321 and 1728 gives: 54321 = 1728 × 31 + 753 1728 = 753 × 2 + 222 753 = 222 × 3 + 87 222 = 87 × 2 + 48 87 = 48 × 1 + 39 48 = 39 × 1 + 9 39 = 9 × 4 + 3 9=3×3+0 This shows that gcd(54321, 1728) = 3. Exercise: 7 Section 2.1 Question: Define the Fibonacci sequence {fn }n≥0 by f0 = 0, f1 = 1 and fn = fn−1 + fn−2 for all n ≥ 2. Let fn and fn+1 be two consecutive terms in the Fibonacci sequence. Prove that gcd(fn+1 , fn ) = 1 and show that for all n ≥ 2, the Euclidean algorithm requires exactly n − 1 integer divisions (including the last one that has a remainder of 0). Solution: The successive indices f1 = f2 are the only time the Fibonacci sequence elements are equal. Hence, for n ≥ 4, the recurrence relation fn = fn−1 + fn−2 is such that 0 ≤ fn−2 < fn−1 . Thus fn = fn−1 × 1 + fn−2 is the integer division of fn by fn−1 . So when performing the Euclidean Algorithm on fn+1 and fn , the recurrence relation gives the Euclidean Algorithm step for from fn+1 down to f4 = f3 + f2 , which is 3 = 2 + 1. This accounts for n − 2 integer divisions. The last integer division is f3 = f2 × 2 + 0. Hence, there are n − 1 integer divisions in the Euclidean Algorithm and the penultimate line in the Euclidean Algorithm is 3 = 2 + 1. Consequently, gcd(fn+1 , fn ) = 1. Exercise: 8 Section 2.1 Question: Let a, b, c ∈ Z. Prove that a|b implies that a|bc. Solution: If a | b then there exists k ∈ Z such that b = ak. Hence, bc = a(kc). Thus a | bc. Exercise: 9 Section 2.1 Question: Perform the Extended Euclidean Algorithm on the three pairs of integers in Exercise 2.1.5. Solution: Extended Euclidean Algorithm: a) We have gcd(234, 84) = 6 and extending the Euclidean Algorithm gives 6 = 18 − 1 × 12 = 18 − (66 − 18 × 3) = (−1) × 66 + 4 × 18 = (−1) × 66 + 4 × (84 − 66) = 4 × 84 − 5 × 66 = 4 × 84 − 5 × (234 − 2 × 84) = −5 × 234 + 14 × 84. b) We have gcd(5241, 872) = 1 and extending the Euclidean Algorithm gives 1=9−1×8 = 9 − (872 − 96 × 9) = −872 + 97 × 9 = −872 + 97(5241 − 6 × 872) = 97 × 5241 − 583 × 872.

CHAPTER 2. NUMBER THEORY c) We have gcd(1010101, 1221) = 1 and extending the Euclidean Algorithm gives 1 = 11 − 2 × 5 = 11 − 2(104 − 9 × 11) = (−2) × 104 + 19 × 11 = (−2) × 104 + 19 × (115 − 104) = 19 × 115 − 21 × 104 = 19 × 115 − 21 × (219 − 115) = (−21) × 219 + 40 × 115 = (−21) × 219 + 40 × (334 − 219) = 40 × 334 − 61 × 219 = 40 × 334 − 61 × (1221 − 3 × 334) = (−61) × 1221 + 223 × 334 = (−61) × 1221 + 223 × (1010101 − 827 × 1221) = 223 × 1010101 − 184482 × 1221.

Exercise: 10 Section 2.1 Question: Perform the Extended Euclidean Algorithm on the three pairs of integers in Exercise 2.1.6 Solution: Extended Euclidean Algorithm: a) We have gcd(55, 34) = 1 and extending the Euclidean Algorithm gives 1=3−1×2 = 3 − 1 × (5 − 3) = (−1) × 5 + 2 × 3 = (−1) × 5 + 2 × (8 − 5) = 2 × 8 − 3 × 5 = 2 × 8 − 3 × (13 − 8) = (−3) × 13 + 5 × 8 = (−3) × 13 + 5 × (21 − 13) = 5 × 21 − 8 × 13 = 5 × 21 − 8 × (34 − 21) = (−8) × 34 + 13 × 21 = (−8) × 34 + 13 × (55 − 34) = 31 × 55 − 21 × 34. b) We have gcd(4321, 1234) = 1 and extending the Euclidean Algorithm gives 1=4−3 = 4 − (615 − 153 × 4) = (−1) × 615 + 154 × 4 = (−1) × 615 + 154 × (619 − 615) = 154 × 619 − 155 × 615 = 154 × 619 − 155 × (1234 − 619) = (−155) × 1234 + 309 × 619 = (−155) × 1234 + 309 × (4321 − 3 × 1234) = 309 × 4321 − 1082 × 1234. c) We have gcd(54321, 1728) = 3 and extending the Euclidean Algorithm gives 3 = 39 − 4 × 9 = 39 − 4 × (48 − 39) = (−4) × 48 + 5 × 39 = (−4) × 48 + 5 × (87 − 48) = 5 × 87 − 9 × 48 = 5 × 87 − 9 × (222 − 2 × 87) = (−9) × 222 + 23 × 87 = (−9) × 222 + 23 × (753 − 3 × 222) = 23 × 753 − 78 × 222 = 23 × 753 − 78 × (1728 − 2 × 753) = (−78) × 1728 + 179 × 753 = (−78) × 1728 + 179 × (54321 − 31 × 1728) = 179 × 54321 − 5627 × 1728.

Exercise: 11 Section 2.1 Question: Suppose that a, b ∈ Z∗ and that s, t ∈ Z∗ such that sa + tb = gcd(a, b). Show that s and t are relatively prime. Solution: Suppose that a, b ∈ Z∗ and that s, t ∈ Z∗ such that sa + tb = gcd(a, b). Since gcd(a, b) divides both a and b, we have b a s+ t = 1. gcd(a, b) gcd(a, b) Since a/ gcd(a, b) and b/ gcd(a, b) are integers, then this gives an integer linear combination of s and t that is 1. Since the greatest common divisor of two integers is the least positive integer linear combination, we deduce that gcd(s, t) = 1.

2.1. BASIC PROPERTIES OF INTEGERS

Exercise: 12 Section 2.1 Question: Consider the relation of “relatively prime” on Z∗ . Determine whether it is reflexive, symmetric, antisymmetric, or transitive. Solution: Reflexive. If a ≥ 2, then gcd(a, a) = a so “relatively prime” is not reflexive. Symmetric. “Relatively prime” is symmetric since gcd(a, b) = gcd(b, a). Antisymmetric. Suppose that gcd(a, b) = 1 and gcd(a, b) = 1. This does not imply that a = b. Hence “relatively prime” is not antisymmetric. Transitive. “Relatively prime” is not transitive: gcd(2, 3) = 1 and gcd(3, 4) = 1 but gcd(2, 4) = 2.

Exercise: 13 Section 2.1 Question: Let a, b, c be nonzero integers. Prove that gcd(ab, ac) = a gcd(b, c). Solution: Let s0 , t0 ∈ Z be integers such that s0 b + t0 c = gcd(b, c), which exist by virtue of Proposition 2.1.12. Then s0 ab + t0 ac = a gcd(b, c) so also by the same proposition, since a gcd(b, c) is a linear combination of ab and ac, then gcd(ab, ac) divides a gcd(b, c). Conversely, let s1 , t1 ∈ Z such that gcd(ab, ac) = s1 (ab) + t1 (ac). Then gcd(ab, ac) = a(s1 b + t1 c) and since s1 b + t1 c is a linear combination of b and c, then by Proposition 2.1.12 it must be a multiple of gcd(b, c). Hence, we deduce that gcd(ab, ac) divides a gcd(ab, ac). Two positive integers that divide each other must be equal so gcd(ab, ac) = a gcd(b, c). Exercise: 14 Section 2.1 Question: Let a and b be positive integers. Show that the set of common multiples of a and b is lcm(a, b)Z, i.e., the set of multiples of lcm(a, b). Solution: Let a and b be positive integers and let S be the set of common multiples. Let m be the least positive element of S, which exists by the well-ordering of the integers. This is lcm(a, b). (S is not empty since ab ∈ S.) Let M be any other common multiple of a and b. Consider the integer division of M by m, as M = qm + r, where 0 ≤ r < m. We then have r = M − qm. We have M = `a and m = ka so r = (` − qk)a. Hence r is a multiple of a. Similarly, r is a multiple of b. Thus r ∈ S. Since m is the least positive element in S, then r must be 0. Hence M = qm. Thus, every element of S is a multiple of m = lcm(a, b). Exercise: 15 Section 2.1 Question: Prove that any integer greater than 3 that is 1 less than a square cannot be prime. Solution: An integer that is one less than a square has the form n2 − 1 for some positive integer n. However, n2 − 1 = (n − 1)(n + 1). The condition that n2 − 1 > 3 is equivalent to n > 2. Hence, n + 1 > n − 1 > 1. Thus n2 − 1 = (n − 1)(n + 1) is a factorization of n2 − 1 in which both factors are greater than 1. Thus n2 − 1 is not a prime number. Exercise: 16 Section 2.1 Question: Prove that if 2n − 1 is prime then n is prime. Solution: We prove this with a contrapositive proof. Suppose that n is composite with n = rs with r, s > 1. Then s 2n − 1 = 2rs − 1 = (2r ) − 1. In the formula as − bs = (a − b)(as−1 + as−2 b + as−3 b2 + · · · + bs−1 ), we set a = 2r and b = 1 and get s−1 s−2 2n − 1 = (2r − 1) (2r ) + (2r ) + · · · + (2r ) + 1 .

CHAPTER 2. NUMBER THEORY

This expresses 2n − 1 as a product of two integers. To establish a contradiction, we simply need to show that both of these factors are greater than 1. With the assumption that r ≥ 2, we have 2r ≥ 4 so 2r − 1 ≥ 3. The s−1 s−2 first factor is greater than 1. Since s ≥ 2, the expression (2r ) + (2r ) + · · · + (2r ) + 1 involves at least two terms so it is greater than or equal to 2r + 1 ≥ 22 + 1 = 5. In particular, the second factor is greater than 1. We have proven that if n is composite then 2n − 1 is composite. The (logically equivalent) contrapositive of this statement is that if 2n − 1 is prime, then n is prime. Exercise: 17 Section 2.1 Question: Prove or disprove that p1 p2 · · · pn + 1 is a prime number where p1 , p2 , . . . , pn are the n smallest consecutive prime numbers. Solution: This hypothesis is not true. It suffices to calculate the p1 p2 · · · pn + 1 for a few n and checked their prime factorizations. n p1 p2 · · · pn + 1 1 3 =3 =7 2 7 3 61 = 61 = 421 4 421 5 2311 = 2311 6 30031 = 59 × 509

Exercise: 18 Section 2.1 Question: Prove that the product of two consecutive positive integers is even. Solution: Suppose that n is even; then n(n + 1) is even. Suppose that n is odd; then n + 1 is even so n(n + 1) is even. Hence, regardless of what n is, the product n(n + 1) is even. Exercise: 19 Section 2.1 Question: Prove that the product of four consecutive positive integers is divisible by 24. Solution: We prove this by cases that 24 | n(n + 1)(n + 2)(n + 3) for all n ∈ Z. At least one of the integers n, n + 1, n + 2, or n + 3 is divisible by 3. n has a remainder or 0 when divided by 4 . Then n is divisible by 4 and n + 2 is even. Hence, 8 | n(n + 1)(n + 2)(n + 3) so also 24 | n(n + 1)(n + 2)(n + 3). n has a remainder or 1 when divided by 4 . Then n + 3 is divisible by 4 and n + 1 is even. Hence, 8 | n(n + 1)(n + 2)(n + 3) so also 24 | n(n + 1)(n + 2)(n + 3). n has a remainder or 2 when divided by 4 . Then n + 2 is divisible by 4 and n is even. Hence, 8 | n(n + 1)(n + 2)(n + 3) so also 24 | n(n + 1)(n + 2)(n + 3). n has a remainder or 3 when divided by 4 . Then n + 1 is divisible by 4 and n + 3 is even. Hence, 8 | n(n + 1)(n + 2)(n + 3) so also 24 | n(n + 1)(n + 2)(n + 3). In all cases, 24 divides the product n(n + 1)(n + 2)(n + 3) of 4 consecutive integers. Exercise: 20 Section 2.1 Question: Suppose that the prime factorizations of a and b are αn 1 α2 a = pα 1 p2 · · · pn

and b = pβ1 1 pβ2 2 · · · pβnn ,

with pi distinct primes and αi , βi ≥ 0. min(α1 ,β1 ) min(α2 ,β2 ) n ,βn ) p2 · · · pmin(α . n max(α1 ,β1 ) max(α2 ,β2 ) max(αn ,βn ) Prove that lcm(a, b) = p1 p2 · · · pn .

a) Prove that gcd(a, b) = p1 b)

Solution: Suppose that the prime factorizations of a and b are αn 1 α2 a = pα 1 p2 · · · pn

with pi distinct primes and αi , βi ≥ 0.

and b = pβ1 1 pβ2 2 · · · pβnn ,

2.1. BASIC PROPERTIES OF INTEGERS

a) Let d0 be a common divisor of a and b. Since d0 k = a and d0 ` = b for some integers k and `, then the only primes occurring in the prime factorization of d0 are p1 , p2 , . . . , pn . Suppose that d0 = pγ11 pγ22 · · · pγnn . Then n −γn a = d0 p1α1 −γ1 p2α2 −γ2 · · · pα n

and b = d0 p1β1 −γ1 p2β2 −γ2 · · · pnβn −γn Since all the powers on the primes must be nonnegative, we deduce that γi ≤ αi and γi ≤ βi for i = 1, 2, . . . , n. min(α ,β ) min(α ,β )

1 1 2 2 n ,βn ) Let d = p1 p2 · · · pmin(α . We see that from the above condition that d is a common n divisor. Furthermore, every other common divisor d0 as above has γi ≤ max(αi , βi ) for i = 1, 2, . . . , n and thus min(α1 ,β1 )−γ1 min(α2 ,β2 )−γ2 n ,βn )−γn d = d0 p1 p2 · · · pmin(α . n

Consequently, d0 | d. Thus d is a greatest common divisor to a and b. b) Let m0 be a common multiple of a and b. Since m0 = ka and m0 = `b for some integers k and `, then the prime p1 , p2 , . . . , pn occur in the prime factorization of m0 . Suppose that m0 = pγ11 pγ22 · · · pγnn Q, where Q is not divisible by pi for any i = 1, 2, . . . , n. Then m0 = apγ11 −α1 pγ22 −α2 · · · pγnn −αn Q and m0 = bp1γ1 −β1 p2γ2 −β2 · · · pγnn −βn Q Since all the powers on the primes must be nonnegative, we deduce that γi ≥ αi and γi ≥ βi for i = 1, 2, . . . , n. max(α ,β ) max(α ,β )

1 1 2 2 n ,βn ) Let m = p1 p2 · · · pmax(α . We see that from the above condition that m is a common n multiple. Furthermore, every other common multiple m0 as above has γi ≥ max(αi , βi ) for i = 1, 2, . . . , n and thus γ −max(α1 ,β1 ) γ2 −max(α2 ,β2 ) m0 = mp11 p2 · · · pγnn −max(αn ,βn ) Q.

Consequently, m | m0 . Thus m is a least common multiple to a and b. Exercise: 21 Section 2.1 Question: Let a and b be positive integers. Prove that gcd(a, b) lcm(a, b) = ab using the result of Problem 2.1.20. Solution: Let a and b be integers with the prime factorization of αn 1 α2 a = pα 1 p2 · · · pn

and b = pβ1 1 pβ2 2 · · · pβnn ,

with pi distinct primes and αi , βi ≥ 0. Then according to Problem 2.1.20, min(α1 ,β1 )+max(α1 ,β1 ) min(α2 ,β2 )+max(α2 ,β2 ) n ,βn )+max(αn ,βn ) p2 · · · pmin(α . n

gcd(a, b) lcm(a, b) = p1

Now for any two real numbers x and y (and so this would also hold for integers), ( x + y if x ≤ y min(x, y) + max(x, y) = . y + x if x > y So min(x, y) + max(x, y) = x + y for all real numbers x, y ∈ R. Hence, returning to our situation, n +βn gcd(a, b) lcm(a, b) = p1α1 +β1 p2α2 +β2 · · · pα n β1 β2 αn βn 1 α2 = (pα 1 p2 · · · pn ) p1 p2 · · · pn

= ab.

CHAPTER 2. NUMBER THEORY

Exercise: 22 Section 2.1√ Question: Prove that 2 is not a rational number. √ Solution: Assume that 2 = ab with a and b relatively prime. Then 2b2 = a2 . Consider the prime factorization of this expression 2b2 = a2 . The prime factorization of 2b2 involves an odd number of prime factors, counting 2 separately √ repeated prime factors, whereas a has an even number of prime factors. This leads to a contradiction. Hence, 2 is irrational. Exercise: 23 Section 2.1 √ Question: Prove that for all primes p and all integers k ≥ 2, the number k p is irrational. √ √ Solution: Assume that k p is rational and that k p = ab in reduced form, i.e., gcd(a, b) = 1. Then pbk = ak . Since the prime p divides ak , we know that p | a with a = pd. Thus pbk = pk dk and hence bk = pk−1 dk . Then p is in the prime factorization of bk , so p | bk and hence p | b. This contradicts the assumption that a and b are √ relatively prime. Hence, k p is irrational. Exercise: 24 Section 2.1 Question: Determine all the nonzero ordp (n), defined in (2.4), for all primes p, where n is one of the following (a) 450;

(b) 392;

(d) 121212.

Solution: a) Since 450 = 2 × 32 × 52 , then the only nonzero ordp values are ord2 (450) = 1, ord3 (450) = 2, and ord5 (450) = 2. b) Since 392 = 23 × 72 , then the only nonzero ordp values are ord2 (4392) = 3 and ord7 (392) = 2. c) Since 2310 = 2 × 3 × 5 × 7 × 11, then the only nonzero ordp values are ord2 (2310) = ord3 (2310) = ord5 (2310) = ord7 (2310) = ord11 (2310) = 1. d) Since 121212 = 22 × 32 × 7 × 13 × 37, then the only nonzero ordp values are ord2 (121212) = ord3 (121212) = 2 and ord7 (121212) = ord13 (121212) = ord37 (121212) = 1.

Exercise: 25 Section 2.1 Question: Find ord5 (200!). Use this to determine the number of 0s to the right in the decimal expansion of 200!. Solution: There are 40 multiples of 5 occurring in the product of integers in 20!. Furthermore, 8 of them are multiples of 52 = 25 and 1 of them is a multiple of 53 = 125. Consequently, ord5 (200!) = 40 + 8 + 1 = 49. It is obvious that ord2 (200!) ≥ 100. Hence, 1049 divides 200! but 1050 - 200!. Hence, there are 49 0s in the decimal expansion of 200!. Exercise: 26 Section 2.1 Question: Let p be a prime number. Prove that the function ordp : Q → Z defined in (2.4) satisfies the following logarithmic-type properties. a) ordp (mn) = ordp (m) + ordp (n) for all m, n ∈ Z; b) ordp (mk ) = k ordp (m) for all m ∈ Z and k ∈ N∗ . Solution: Let p be a prime number. a) Suppose that ordp (m) = α and ordp (n) = β. Then pα | m and pα - m and pβ | n and pβ - n. Furthermore, pα+β | mn but pα+β+1 - mn. Hence, ordp (mn) = α + β. b) If ordp (m) = α, then m = pα Q with p - Q. Thus mk = pαk Qk and since p - Q, we still have p - Qk . Thus, pαk | mk but pαk+1 - mk . Thus, ordp (mk ) = k ordp (m).

2.1. BASIC PROPERTIES OF INTEGERS

Exercise: 27 Section 2.1 Question: For the following integers, calculate ϕ(n) by directly listing the set in (2.5). (a)φ(30);

(b)φ(33);

(c)φ(12).

Solution: a) {a ∈ N∗ | 1 ≤ a ≤ 30 and gcd(a, 30) = 1} = {1, 7, 11, 13, 17, 19, 23, 29}. Thus, φ(30) = 8. b) {a ∈ N∗ | 1 ≤ a ≤ 33 and gcd(a, 33) = 1} is the set {1, 2, 4, 5, 7, 8, 10, 13, 14, 16, 17, 19, 20, 23, 25, 26, 28, 28, 31, 32}. Thus, φ(33) = 20. c) {a ∈ N∗ | 1 ≤ a ≤ 12 and gcd(a, 12) = 1} = {1, 5, 7, 11}. Thus, φ(12) = 4. Exercise: 28 Section 2.1 Question: Prove that for all integers n, n=

φ(d),

d|n

where this summation notation means we sum over all positive divisors d of n. Solution: There are obviously n distinct fractions in the set n1 , n2 , n3 , . . . , nn . A fraction of the form na in 0 0 reduced form is na = ad where d is a divisor of n. If ad is in reduced form then a0 and d are relatively prime. For 0 each divisor d of n, there are φ(d) fractions of the form ad with gcd(a0 , d) = 1. Thus n=

φ(d).

d|n

Exercise: 29 Section 2.1 Question: Prove that for any prime p, the following identities hold. a) φ(p) = p − 1 b) φ(pk ) = pk − pk−1 Solution: a) The set of integers between 1 and p that are relatively prime to p is {1, 2, . . . , p − 1}. Hence, φ(p) = p − 1. b) The set of integers between 1 and pk that are relatively prime to p are the integers between 1 and pk that are not divisible by p. The number of integers between 1 and pk that are divisible by p are {pa | 1 ≤ a ≤ pk−1 }. Thus, φ(pk ) = pk − pk−1 . Exercise: 30 Section 2.1 Question: Prove that if a and b are relatively prime, then Euler’s totient function satisfies φ(ab) = φ(a)φ(b). Solution: Suppose that a and b are positive integers. Let Dn = {k | 1 ≤ k ≤ n such that gcd(k, n) > 1}. Then the sets bDa = {bk | 1 ≤ k ≤ a such that gcd(k, a) > 1} and aDb are subsets of Dab . The union aDb ∪ bDa covers Dab but aDb ∩ bDa is nontrivial. In fact, aDb ∩ bDa consists of products of elements that are not relatively prime to a and not relatively prime to b. Since gcd(a, b) = 1, this set has cardinality (a − φ(a))(b − φ(b)). By the Inclusion-Exclusion principle, |Dab | = |bDa | + |aDb | − |bDa ∩ aDb | = a(b − φ(b)) + b(a − φ(a)) − (a − φ(a))(b − φ(b)) = ab − φ(a)φ(b). But |Dab | = ab − φ(ab) so we deduce that φ(ab) = φ(a)φ(b). Exercise: 31 Section 2.1 Question: Using Exercises 2.1.29 and 2.1.30, prove Proposition 2.1.27.

CHAPTER 2. NUMBER THEORY α

αk αi j 1 α2 Solution: Let n = pα 1 p2 · · · pk be the prime factorization of n. By Exercise 2.1.30, since gcd(pi , pj ) = 1 for i 6= j, we have αk α2 1 φ(n) = φ((pα 1 ) φ (p2 ) · · · φ (pk ) αk −1 α1 −1 α2 −1 1 2 k = pα pα · · · pα , 1 − p1 2 − p2 k − pk

where the second equality holds by part (b) of Exercise 2.1.29.

2.2 – Modular Arithmetic Exercise: 1 Section 2.2 Question: List ten elements in the conjugacy class 3 in modulo 7. Solution: Modulo 7, the conjugacy class 3 contains among other elements . . . , −18, −11, −4, 3, 10, 17, 24, 31, 38, 45, . . . Exercise: 2 Section 2.2 Question: List all the elements in Z/13Z. Solution: Z/13Z = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}. Exercise: 3 Section 2.2 Question: List all the elements in Z/24Z and in U (24). Solution: The elements in Z/24Z are Z/24Z = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}. The units in this modular arithmetic are U (24) = {1, 5, 7, 11, 13, 17, 19, 23}.

Exercise: 4 Section 2.2 Question: Perform the following calculations in the modular arithmetic of the given modulus n. a) 3̄ + 5̄ · 7̄ with n = 9 b) (5̄ · 4̄ − 72 · 3̄)2 with n = 11 c) 13 · 42 · 103 with n = 15 Solution: a) With n = 9, we have 3̄ + 5̄ · 7̄ = 3̄ + 8̄ = 2̄. b) With n = 11, we have (5̄ · 4̄ − 72 · 3̄)2 = (9̄ − 7̄)2 = 2̄2 = 4̄. c) With n = 15, we have 13 · 42 · 103 = 13 · 12 · 13 = −2 · −3 · −2 = −12 = 3.

Exercise: 5 Section 2.2 Question: Write out the elements in the set U (30). Solution: U (30) = {1̄, 7̄, 11, 13, 17, 19, 23, 29}. Exercise: 6 Section 2.2 Question: In Z/17Z, solve for x in terms of y in y = 2̄x + 3̄.

2.2. MODULAR ARITHMETIC

Solution: In Z/17Z, the equation y = 2̄x + 3̄ is equivalent to y + 14 = 2̄x. The multiplicative inverse of 2̄ in Z/17Z is 9̄. Thus x = 9̄(y + 14) = 9̄y + 7̄. Exercise: 7 Section 2.2 Question: In Z/29Z, solve for x in terms of y in y = 17x + 20. Solution: We need to find the multiplicative inverse of 17 in Z/29Z. Whether we use the Extended Euclidean −1 Algorithm or look for the inverse by exhaustively trying elements, we find that 17 = 12. Hence we have y = 17x + 20 =⇒ y + 9 = 17x =⇒ x = 12(y + 9) = 12y + 21

Exercise: 8 Section 2.2 Question: Show that for all integers a, we have a2 ≡ 0 or 1 (mod 4). Show how this implies that for all integers a, b ∈ Z, the sum of squares a2 + b2 never has a remainder of 3 when divides by 4. Solution: Considering the four cases for a congruent modulo 4, we have (a) if a ≡ 0 (mod 4), then a2 ≡ 0 (mod 4); (b) if a ≡ 1 (mod 4), then a2 ≡ 1 (mod 4); (c) if a ≡ 2 (mod 4), then a2 ≡ 4 ≡ 0 (mod 4); and (d) if a ≡ 3 (mod 4), then a2 ≡ 9 ≡ 1 (mod 4). Hence, in all cases a2 ≡ 0 or 1 (mod 4) for all integers a. Consequently, for all integers a, b ∈ Z,  2 2  0 if a ≡ 0 and b ≡ 0 2 2 2 a + b ≡ 1 if a ≡ 1 and b2 ≡ 0ORa2 ≡ 0 and b2 ≡ 1   2 if a2 ≡ 1 and b2 ≡ 1. Hence, a2 + b2 is never congruent to 3 modulo 4. Exercise: 9 Section 2.2 Question: Prove that if d|m and a ≡ b (mod m), then a ≡ b (mod d). Solution: Suppose that d | m. Then m = dk for some integer k. The statement a ≡ b (mod m) is equivalent to m | (b − a), or in other words b − a = m` for some integer `. Thus b − a = d(k`) so d | (b − a) and therefore a ≡ b (mod d). Exercise: 10 Section 2.2 Question: Prove that if a, b, c, and m are integers with m ≥ 2 and c > 0, then a ≡ b (mod m) implies that ac ≡ bc (mod mc). Solution: Let a, b, c, and m be integers with m ≥ 2 and c > 0. Then a ≡ b (mod m) is equivalent to m | (b−a), which is equivalent to mk = b − a for some integer k. Then multiplying by c, we have (mc)k = bc − ac. Hence, mc | (bc − ac) and so ac ≡ bc (mod mc). Exercise: 11 Section 2.2 −1 Question: Perform the Extended Euclidean Algorithm to calculate 52 in Z/101Z. Solution: The Euclidean Algorithm to find that gcd(101, 52) proceeds as follows. 101 = 52 × 1 + 49 52 = 49 × 1 + 3 49 = 3 × 16 + 1 3=1×3+0 (This shows that gcd(101, 52) = 1 so 52 is invertible modulo 101. Now reversing the process to complete the Extended Euclidean Algorithm, we have 1 = 49 − 3 × 16 = 49 − (52 − 49) × 16 = 49 × 17 − 52 × 16 = (101 − 52) × 17 − 52 × 16 = 101 × 17 − 52 × 33

CHAPTER 2. NUMBER THEORY

Considering the linear combination 1 = 101 × 17 − 52 × 33 modulo 101, we get −52 × 33 ≡ 1 Hence 52

−1

(mod 101).

= −33 = 68.

Exercise: 12 Section 2.2 −1 Question: Perform the Extended Euclidean Algorithm to calculate 72 in Z/125Z. Solution: We first perform the Euclidean Algorithm on 125 and 72. 125 = 72 × 1 + 53 72 = 53 × 1 + 19 53 = 19 × 2 + 15 19 = 15 × 1 + 4 15 = 4 × 3 + 3 4=3×1+1 3=1×3+0 This confirms that gcd(125, 72) = 1, which means that 72 has a multiplicative inverse modulo 125. The Extended Euclidean Algorithm gives 1=4−3 = 4 − (15 − 3 × 4) = −15 + 4 × 4 = −15 + 4 × (19 − 15) = 4 × 19 − 5 × 15 = 4 × 19 − 5 × (53 − 2 × 19) = −5 × 53 + 14 × 19 = −5 × 53 + 14 × (72 − 53) = 14 × 72 − 19 × 53 = 14 × 72 − 19 × (125 − 72) = −19 × 125 + 33 × 72. The Extended Euclidean Algorithm gives the linear combination 1 = −19 × 125 + 33 × 72. Modulo 125, this −1 expression becomes 1̄ = 33 × 72. Thus 72 = 33. Exercise: 13 Section 2.2 Question: Find the smallest positive integer n such that 2n ≡ 1 (mod 17). Solution: We consider the powers of 2 modulo 17. We perform the operations in Z/17Z. We have 2̄1 = 2̄; 2̄2 = 4̄; 2̄3 = 8̄; 2̄4 = 16; 2̄5 = 32 = 15; 2̄6 = 30 = 13; 2̄7 = 26 = 9; 2̄8 = 18 = 1. Thus, the first power n for which 2n ≡ 1 (mod 17) is n = 8. Exercise: 14 Section 2.2 Question: Find the smallest positive integer n such that 3n ≡ 1 (mod 19). Solution: We consider the powers of 3 modulo 19. We perform the operations in Z/19Z. We have 3̄1 = 3̄; 3̄2 = 9̄; 3̄3 = 27 = 8; 3̄4 = 24 = 5; 3̄5 = 15; 3̄6 = 45 = 7; 3̄7 = 21 = 2; 3̄8 = 6; 3̄9 = 18. At this stage, a clever thing to do is to notice that 3̄9 = −1. Hence, for 10 ≤ k ≤ 18, we have 3̄k = −3̄k−9 . In particular, k = 18 is the first integer where 3̄k = −18 = 1. Exercise: 15 Section 2.2 Question: Show that the powers of 7 in Z/31Z account for exactly half of the elements in U (31). Solution: We first observe that |U (31)| = φ(31) = 30, since 31 is a prime number. We now must calculate 1 2 3 4 5 6 7 the powers of 7. We have 7 = 7; 7 = 49 = 18; 7 = 126 = 2; 7 = 14; 7 = 98 = 5; 7 = 35 = 4; 7 = 28; 8 9 10 11 12 13 14 7 = 196 = 10; 7 = 70 = 8; 7 = 56 = 25; 7 = 175 = 20; 7 = 140 = 16; 7 = 112 = 19; 7 = 133 = 9; 15 a 7 = 63 = 1. After this, the powers of 7 will repeat (cycle). Hence, {7 | a ∈ N} has 15 elements, which is exactly half of the elements of U (31). Exercise: 16 Section 2.2 Question: Show that a number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11. (An alternating sum means that we alternate the signs in the sum + − + − . . ..)

2.2. MODULAR ARITHMETIC

Solution: Suppose that a number n is written in decimal as n = (dk · · · d1 d0 )10 , where di are digits with 0 ≤ di ≤ 9 and dk 6= 0. This means that n = dk × 10k + dk−1 × 10k−1 + · · · + d1 × 10 + d0 . Taking this expression modulo 11, since 10 ≡ −1 (mod 11), we have n ≡ dk × (−1)k + dk−1 × (−1)k−1 + · · · + d1 × (−1) + d0 ≡ d0 − d1 + d2 − · · · + (−1)k−1 dk−1 + (−1)k dk

(mod 11)

(mod 11).

Thus 11 | n if and only if n ≡ 0 (mod 11) if and only if d0 − d1 + d2 − · · · + (−1)k−1 dk−1 + (−1)k dk ≡ 0 if and only if the alternating sum of the digits is divisible by 11. Exercise: 17 Section 2.2 Question: Prove that if n is odd then n2 ≡ 1 (mod 8). Solution: If n is odd, then n = 2k + 1 for some integer k. Then n2 = (2k + 1)2 = 4k 2 + 4k + 1 = 4k(k + 1) + 1. Note that k(k + 1) is the product of two consecutive integers, one of which must be even. Hence, k(k + 1) is even so n2 = 8

k(k+1) 2

+ 1. Therefore, n2 ≡ 1 (mod 8) for all odd integers n.

Exercise: 18 Section 2.2 Question: Show that the difference of two consecutive cubes (an integer of the form n3 ) is never divisible by 3. Solution: Suppose that one cube is n3 . Then the next cube is (n + 1)3 . The difference between these is (n + 1)3 − n3 = n3 + 3n2 + 3n + 1 − n3 = 3(n2 + n) + 1. Hence, (n + 1)3 − n3 ≡ 1 (mod 3) for all integers n. In particular, the difference between two consecutive cubes is neve divisible by 3. Exercise: 19 Section 2.2 Question: Use Fermat’s Little Theorem to determine the remainder of 734171 modulo 13. Solution: Since 73 ≡ 8 (mod 13), we first simplify 734171 ≡ 84171 (mod 13). By Fermat’s Little Theorem, 812 ≡ 1 (mod 13). We perform the integer division of 4171 by 12 and get 4171 = 12 × 347 + 7. Thus 347 7 84171 ≡ 812×347+7 ≡ 812 8 ≡ 87 (mod 13). In this particular case of 8, we also can do the following simplification 87 ≡ 221 ≡ 212 ≡ 29 ≡ 24 · 24 · 2 ≡ 3 · 3 · 2 ≡ 5

(mod 13).

Thus, we conclude that the remainder of 734171 modulo 13 is 5. (Note that we did not use a calculator or computer or even pen and paper for any of these calculations.) Exercise: 20 Section 2.2 Question: Find the units digit of 78357 . Solution: To find the units digit of 78357 means to determine the remainder of 78357 when divided by 10. It is obvious that 78357 is even so it will suffice to determine the remainder 78357 when divided by 5. First, we make the simplification that 78357 ≡ 3357 (mod 5). Now the integer division of 357 by 4 gives 357 = 4 × 89 + 3. So by Fermat’s Little Theorem 3357 ≡ 34×89+3 ≡ (34 )8 933 ≡ 1 · 27 ≡ 2 (mod 5). So 78357 is even and has a remainder of 2 when divided by 5. The only integer between 0 and 9 to have these two properties is 2. Thus the units digit of 78357 is 2. Exercise: 21 Section 2.2 Question: Let {bn }n≥1 be the sequence of integers defined by b1 = 1, b2 = 11, b3 = 111, and in general n digits

z }| { bn = 111 · · · 1.

CHAPTER 2. NUMBER THEORY

Prove that for all prime numbers p different from 2 or 5, there exists a positive n such that p | bn . Solution: Solution 1: Notice that for all n ≥ 1, we have n digits

z }| { 9bn = 999 · · · 9 = 10n − 1. By Fermat’s Little Theorem, for all primes p such that p is not 2 or 5, 10p−1 ≡ 1

(mod p) =⇒ p | 10p−1 − 1.

Hence for all primes p 6= 2, 5, we have p | 9bn . If p 6= 3, then since p - 9, we have p | bn . If p = 3, it is easy to notice directly that b3 is divisible by 3, since b3 = 111 = 3 × 37. The result follows. Solution 2: Let p be a prime number distinct from 2 and 5. Let for all n ∈ N∗ , consider the set Bn defined as {1, 11, 111, . . . , bn }. By the pigeonhole (or box) principle, at least two elements in Bp+1 must be in the same congruence class in Z/pZ, say bk and b` with ` > k. Then b` − bk is divisible by p. However, b` − bk = b(`−k) × 10k+1 . Since p is a prime number and does not divide 10k+1 , then p | b(`−k) . The result follows. Exercise: 22 Section 2.2 Question: Show that 3 | n(n + 1)(n + 2) for all integers n. Solution: In three consecutive integers, there is always at least one that is divisible by 3. Hence, 3 must divide the product of three consecutive integers. Exercise: 23 Section 2.2 Question: Let p be a prime. Prove that p divides the binomial coefficient the binomial theorem to conclude that (a + b)p ≡ ap + bp

p k

for all k with 1 ≤ k ≤ p − 1. Use

(mod p)

for all integers a, b ∈ Z. Solution: The binomial formula gives (a + b)p =

p X k=0

p! ap−k bk . k!(p − k)!

Now if 1 ≤ k ≤ p−1, then k < p so no integer between 1 and k is divisible by the prime p. Hence, p - k!. Similarly p! p − k < p so p - (p − k)!. In the binomial coefficient kp = k!(p−k)! , there is a factor of p on the numerator but it p is not canceled out by the denominator, so p | k for all k with 1 ≤ k ≤ p − 1. Consequently, in modulo p, the binomial formula simplifies to (a + b)p ≡ ap + bp (mod p).

Exercise: 24 Section 2.2 Question: Let n1 and n2 be relatively prime. Prove that x ≡ a1

(mod n1 ) and x ≡ a2

(mod n2 ) ⇐⇒ x ≡ a1 t1 n2 + a2 t2 n1

(mod n1 n2 )

where t1 ≡ n−1 (mod n1 ) and t2 ≡ n−1 (mod n2 ). 2 1 Solution: Suppose that x ≡ a1 (mod n1 ) and x ≡ a2 (mod n2 ). Then x − a1 = k1 n1 for some integer k1 and x − a2 = k2 n2 for some integer k2 . Furthermore, with t1 ≡ n−1 (mod n1 ) and t2 ≡ n−1 (mod n2 ), we have 2 1 t1 n2 = 1 + `1 n1 and t2 n1 = 1 + `2 n2 for some integers `1 and `2 . Then x − (a1 t1 n2 + a2 t2 n1 ) = x − a1 (1 + `1 n1 ) − a2 t2 n1 = (k1 − a1 `1 − a2 t2 )n1 . Similarly, x − (a1 t1 n2 + a2 t2 n1 ) = (k2 − a2 `2 − a1 t1 )n2 .

2.2. MODULAR ARITHMETIC

Thus, x−(a1 t1 n2 +a2 t2 n1 ) is divisible by by n1 and n2 . Since n1 and n2 are relatively prime, x−(a1 t1 n2 +a2 t2 n1 ) is therefore divisible by n1 n2 . Hence, x ≡ a1 t1 n2 + a2 t2 n1

(mod n1 n2 ).

Conversely, suppose that x ≡ a1 t1 n2 +a2 t2 n1 (mod n1 n2 ) where t1 ≡ n−1 (mod n1 ) and t2 ≡ n−1 (mod n2 ). 2 1 Then x − (a1 t1 n2 + a2 t2 n1 ) = kn1 n2 for some integer k. Modulo n1 , this expression becomes x − a1 t1 n2 ≡ 0

(mod n1 ).

But since t1 ≡ n−1 (mod n1 ), we get x ≡ a1 (mod n1 ). The same result holds when considering the expression 2 modulo n2 . Exercise: 25 Section 2.2 Question: Apply the result of Exercise 2.2.24 to solve the system ( x ≡ 2 (mod 9) x ≡ 4 (mod 11). Solution: To solve the system means to find all x that solve the two congruences simultaneously. We first need to calculate t1 and t2 . Modulo n1 = 9, we have n2 ≡ 11 ≡ 2 and so t1 ≡ n−1 2 ≡ 5 (mod 9). Modulo n2 = 11, we have t2 ≡ 9−1 ≡ 5 (mod 11). Then according to Exercise 2.2.24, the solution to the system is x ≡ 2 · 5 · 11 + 4 · 5 · 9 ≡ 92

(mod 99).

Exercise: 26 Section 2.2 Question: Apply the result of Exercise 2.2.24 to solve the system ( x ≡ 15 (mod 17) x ≡ 10 (mod 169). Solution: To solve the system means to find all x that solve the two congruences simultaneously. We first need to calculate t1 and t2 . Modulo n1 = 17, we have n2 ≡ 169 ≡ 16 ≡ −1 (mod 17) and so t1 ≡ n−1 2 ≡ −1 (mod 17). Modulo n2 = 169, we have t2 ≡ 17−1 ≡ 10 (mod 169) since 17 × 10 = 169 + 1. Then according to Exercise 2.2.24, the solution to the system is x ≡ 15 · (−1) · 169 + 410 · 10 · 17 ≡ 67165 ≡ 1086

(mod 2873).

Exercise: 27 Section 2.2 Question: Prove that if ac ≡ bc (mod m) then a ≡ b (mod m d ) where d = gcd(m, c). Solution: Suppose that ac ≡ bc (mod m) and set d = gcd(m, c). Then there exists an integer k such that bc − ac = mk. We can now divide both sides by d to get b dc − a dc = m d k. Hence, c c m a ≡b (mod ). d d d Since d = gcd(m, c), then gcd(m/d, c/d) = 1. Consequently, c/d has a multiplicative inverse k modulo m/d. Multiplying the above equation by k, we get a ≡ b (mod m d ). Exercise: 28 Section 2.2 Question: Consider the sequence of integers {cn }n≥0 defined by c0 = 1,

c1 = 101,

c2 = 10101,

c3 = 1010101,

...

CHAPTER 2. NUMBER THEORY

Prove that for all integers n ≥ 2, the number cn is composite. Solution: We note first that c1 = 101 is a prime number. It is not hard to see that cn =

n X

100n = 100n + 100n−1 + · · · + 1002 + 100 + 1 =

i=0

100n+1 − 1 , 99

where the second equality holds by the formula for the finite geometric series. If n is odd with n ≥ 3, then the digit expansion of cn consists of an even number of 1s. Then ! k X c2k+1 = (100 + 1)1002k + · · · (100 + 1)1002 + (100 + 1)1000 = 101 × 10000i . i=0

Thus, when n is odd, 101 | cn so cn is composite. If n is even with n = 2k, then 1 1 1 (1002k+1 − 1) = (104k+2 − 1) = c2k = 99 99 11

4k+1 X

! i

i=0

There are an even number of elements in the sum on the far right so ! 2k 1 X i 10 (102k+1 + 1). c2k = 11 i=0 Note that 10 ≡ −1 (mod 11) so 102k+1 + 1 ≡ (−1)2k+1 + 1 ≡ 0 (mod 11). Hence 11 | 102k+1 + 1 and for k ≥ 1, P2k we also have (102k+1 + 1)/11 > 1. Furthermore, i=0 10i for k ≥ 1 so we have obtained a nontrivial factorization of c2k into ! 2k X 102k+1 + 1 i 10 . 11 i=0 Hence, cn is also composite for n even with n ≥ 2. The result follows.

2.3 – Mathematical Induction Exercise: 1 Section 2.3 Question: Prove that

n X i=1

i3 =

n2 (n + 1)2 for all integers n ≥ 1. 4 2

Solution: Basis Step: When n = 1, the summation is 13 = 1. If n = 1, then n (n+1) = 24 = 1. 4 n X n2 (n + 1)2 Induction Step: Suppose that i3 = for some integer n ≥ 1. Then 4 i=1 n+1 X

i3 =

i=1

n X

i3 + (n + 1)3

i=1 2

n (n + 1)2 + (n + 1)3 for the induction hypothesis 4 n2 (n + 1)2 + 4(n + 1)3 (n + 1)2 (n2 + 4(n + 1)) (n + 1)2 (n2 + 4n + 4)) = = = 4 4 4 (n + 1)2 (n + 2)2 ) . = 4 =

Thus, if the formula holds for n, it also holds for n + 1. By induction,

n X i=1

i3 =

n2 (n + 1)2 for all integers n ≥ 1. 4

2.3. MATHEMATICAL INDUCTION

Exercise: 2 Section 2.3 Question: Use mathematical induction to prove the geometric summation formula: n X

Ari =

i=0

A(rn+1 − 1) r−1

where r 6= 1

for all nonnegative integers n. n X

A(r − 1) . The formula holds for n = 0. r−1 i=0 Induction Step: Suppose that the formula holds for some nonnegative integer n. Then ! n+1 n X X i i Ar = Ar + Arn+1

Solution: Basis Step: If n = 0, then

i=0

Ari = A =

i=0

A(rn+1 − 1) + Arn+1 by the induction hypothesis = r−1 A(rn+2 − 1) Arn+1 − A + Arn+2 − Arn+1 = = r−1 r−1 A(r(n+1)+1 − 1) = . r−1 Hence, if the formula holds for n, then it holds for n + 1. By induction, if r 6= 1, then

n X

Ari =

i=0

A(rn+1 − 1) r−1

for all n ≥ 0. Exercise: 3 Section 2.3 Question: Prove that for every positive integer n, 1 · 2 + 2 · 3 + · · · + n(n + 1) =

n(n + 1)(n + 2) . 3

Solution: For the basis step, we note that if n = 1, the left-hand side of the formula is 1 · 2 = 2, whereas the right-hand side of the formula is 1 · 2 · 3/3 = 2. Hence, the formula holds for n = 1. Now suppose that the formula holds for some positive integer n. Then with the integer n + 1, using the induction hypothesis in the first line, we have 1 · 2 + 2 · 3 + · · · + n(n + 1) + (n + 1)(n + 2) n(n + 1)(n + 2) + (n + 1)(n + 2) 3 n(n + 1)(n + 2) + 3(n + 1)(n + 2) = 3 (n + 1)(n + 2)(n + 3) = 3 (n + 1)((n + 1) + 1)((n + 1) + 2) = . 3 =

Hence, if the formula holds for n, then it also holds for n+1. By induction, 1·2+2·3+· · ·+n(n+1) = n(n+1)(n+2) 3 for all positive integers n. Exercise: 4 Section 2.3 Question: Prove that 1 + nh ≤ (1 + h)n that for all h ≥ −1 and for nonnegative integers n ≥ 0. Solution: Note that the condition of h ≥ −1 is equivalent to h + 1 ≥ 0. When n = 0, then 1 + nh ≤ (1 + h)n reads 1 ≤ 1 so the inequality holds. Now, suppose that the inequality 1 + nh ≤ (1 + h)n holds for some n ≥ 0. Then (1 + h)n+1 = (1 + h)n (1 + h). Since 1 + h ≥ 0, using the induction hypothesis, we deduce that (1 + h)n+1 ≥ (1 + nh)(1 + h) = 1 + nh + h + nh2 ≥ 1 + (n + 1)h.

CHAPTER 2. NUMBER THEORY

Thus, if the inequality holds for some nonnegative n, then it also holds for n + 1. By induction, supposing h ≥ −1, then 1 + nh ≤ (1 + h)n for nonnegative integers n. Exercise: 5 Section 2.3 Question: Prove that 5|(n5 − n) for all nonnegative integers n in the following two ways: a) Using Fermat’s Little Theorem. b) By induction on n. Solution: We prove that 5|(n5 − n) for all nonnegative integers n. a) By Fermat’s Little Theorem, if 5 - n, then n4 ≡ 1 (mod 5), which means that 5 divides n4 − 1, which in turns implies that 5 divides n5 − n. If 5 | n, then n5 and n are both divisible by 5 and thus so is n5 − n. b) We note right away that if n = 0, then n5 − n = 0 so 5 divides n5 − n. Now suppose that 5 divides n5 − n for some nonnegative integer n with n5 − n = 5K. Then (n + 1)5 − (n + 1) = n5 + 5n4 + 10n3 + 10n2 + 5n + 1 − n − 1 = (n5 − n) + 5(n4 + 2n3 + 2n2 + n) = 5(K + n4 + 2n3 + 2n2 + n). Thus, 5 divides (n + 1)5 − (n + 1). By induction, 5 divides n5 − n for all nonnegative integers n. Exercise: 6 Section 2.3 Question: Prove by induction that

n X (2i + 1) = (n + 1)2 . i=0

Solution: Note that if n = 0, then

n X

(2i + 1) = 1, whereas (n + 1)2 = 12 = 1. So the formula holds for n = 0.

i=0

Now suppose that the formula holds for some nonnegative integer n. Then ! n+1 n X X (2i + 1) = (2i + 1) + (2(n + 1) + 1) = (n + 1)2 + 2(n + 1) + 1 = ((n + 1) + 1)2 . i=0

i=0

Thus, the formula holds also for n + 1. By induction,

n X

(2i + 1) = (n + 1)2 for all integers n ≥ 0.

i=0

Exercise: 7 Section 2.3 Question: Prove that fn−1 fn+1 − fn2 = (−1)n for all n ≥ 1. Solution: We prove by induction that fn−1 fn+1 − fn2 = (−1)n for all n ≥ 1. If n = 1, then f0 f2 − f12 = 0 − 12 = (−1)1 . So the formula holds for n = 1. Now suppose that the formula holds for some n ≥ 1. Then 2 2 fn fn+2 − fn+1 = fn (fn+1 + fn ) − fn+1

= fn2 + fn+1 (fn − fn+1 ) = fn2 + fn+1 (−fn−1 ) = −(−1)n = (−1)n+1

by the induction hypothesis.

Thus, if the formula holds for some n then it also holds for n + 1. By induction, fn−1 fn+1 − fn2 = (−1)n for all n ≥ 1. Exercise: 8 Section 2.3 2 Question: Prove that fn2 + fn−1 = f2n−1 for all n ≥ 1. Solution: For this exercise, we first make the following observation. fn = fn−1 + fn−2 = f3 fn−2 + f2 fn−3 = f4 fn−3 + f3 fn−4 .. . = fn = fk+1 fn−k + fk fn−k−1

2.3. MATHEMATICAL INDUCTION

For this exercise, it is useful to use f2n = fn+1 fn + fn fn−1 for all n. 2 2 We prove that fn2 + fn−1 = f2n−1 for all n ≥ 1 by induction. If n = 1, then fn2 + fn−1 = f12 + f02 = 1 = f1 = f2n−1 . Now suppose that the formula is true for some n ≥ 1. Then f2n+1 = f2n + f2n−1 2 = fn+1 fn + fn fn−1 + fn2 + fn−1

by the induction hypothesis

2 = fn+1 fn − fn fn−1 + fn2 + 2fn fn−1 + fn−1 = fn (fn+1 − fn−1 ) + (fn + fn−1 )2 2 = fn2 + fn+1 .

Hence, if the formula is true for some n, then it is also true for n + 1. By induction, the formula is true for all n ≥ 1. Exercise: 9 Section 2.3 Question: Prove that

n X

fi = fn+2 − 1.

i=0

Solution: We prove by induction that

n X

fi = fn+2 − 1 for all n ≥ 0. If n = 0, then

i=0

n X

fi = 0, which is equal

i=0

to 1 − 1 = f2 − 1. Thus, the formula holds for n = 0. Now suppose that the formula holds for some nonnegative n. Then ! n+1 n X X fi = fi + fn+1 i=0

i=0

= fn+2 − 1 + fn+1

by the induction hypothesis

= fn+3 − 1 = f(n+1)+2 − 1. Thus, the formula then holds for n + 1 as well. By induction, the formula holds for all nonnegative n. Exercise: 10 Section 2.3 Question: Prove 2 | fn if and only if 3 | n. Solution: We will first prove by induction that 2 | f3m for all nonnegative integers m. Let m = 0. Then f0 = 0 and 2 | f0 . Now suppose that 2 | f3m for some nonnegative integer m. Then f3m+3 = f3m+2 + f3m+1 = 2f3m+1 + f3m . Since 2 | f3m , then we see that 2 | f3m+3 . By induction, 2 | f3m for all n ≥ 0. Now we prove that 2 - f3m±1 for all m ≥ 0 (ignoring the case of f−1 implied in this notation). If m = 0 or m = 1, this takes into account f1 = 1, f2 = 1, and f4 = 3. None of these are even. Suppose that f3m±1 is odd for some m ≥ 1. Then, f3m+4 = f3m+3 + f3m+2 = 2f3m+2 + f3m+1 . Since we know that f3m+1 is odd, then f3(m+1)+1 is odd. Also, f3(m+1)−1 = f3m+2 = f3m+1 + f3m . Since we know that f3m is even from the previous part and f3m+1 is odd by the induction hypothesis, then we conclude that f3(m+1)−1 is also odd. The result is proved by induction. Comment: Though this problem is in a section on induction, a much fast proof of this same result consists in looking at the Fibonacci number modulo 2. We see that they make the pattern of 0, 1, 1, 0, 1, 1, . . .. The same result follows immediately. Exercise: 11 Section 2.3 n X Question: Prove that fi2 = fn fn+1 . i=0

Solution:

CHAPTER 2. NUMBER THEORY

We prove by induction that

n X

fi2 = fn fn+1 for all n ≥ 0. With n = 0, the formula claims that

i=0

f02 = 0 = f0 f1 . This is obviously true so the basis step holds. Now suppose that the formula is true for some nonnegative integer n. Then ! n+1 n X X 2 2 2 2 fi = fi + fn+1 = fn fn+1 + fn+1 = fn+1 (fn + fn+1 ) = fn+1 fn+2 . i=0

i=0

Thus, the formula holds for n + 1. By induction,

n X

fi2 = fn fn+1 for all n ≥ 0.

i=0

Exercise: 12 Section 2.3 Question: Prove that for all real numbers r 6= 1, n X

krk =

k=0

((r − 1)n − 1) rn+1 + r . (r − 1)2

Solution: We prove by induction on n with n ≥ 0, that n X k=0

krk =

((r − 1)n − 1) rn+1 + r (r − 1)2

n+1 Pn +r −r+r for all real numbers r 6= 1. If n = 0, then k=0 krk = 0 whereas ((r−1)n−1)r = (r−1) 2 = 0. Hence, the (r−1)2 formula is valid for n = 0. Now suppose that the formula holds for some n ≥ 0. Then ! n+1 n X X krk = krk + (n + 1)rn+1

k=0

((r − 1)n − 1) rn+1 + r + (n + 1)rn+1 by the induction hypothesis = (r − 1)2 ((r − 1)n − 1) rn+1 + r + (n + 1)rn+1 (r − 1)2 = (r − 1)2 nr − n − 1 + (n + 1)(r2 − 2r + 1) rn+1 + r = (r − 1)2 2 2 (nr − nr + r − 2r)rn+1 + r (nr − n + r − 2)rn+2 + r = = (r − 1)2 (r − 1)2 =

((r − 1)(n + 1) − 1)r(n+1)+1 + r . (r − 1)2

Hence, he formula then holds for n + 1. By induction, the formula holds for all n ≥ 0. Exercise: 13 Section 2.3 Question: Prove that 13 divides 3n+1 + 42n−1 for all n ≥ 1. Solution: We prove by induction that n ≥ 1, the number 3n+1 + 42n−1 is divisible by 13. For n = 1, we have 3n+1 + 42n−1 = 9 + 4 = 13, which is obviously divisible by 13. Now suppose that 13 divides 3n+1 + 42n−1 for some n ≥ 1. Then 3n+2 + 42(n+1)−1 = 3 · 3n+1 + 16 · 42n−1 = 3 · 3n+1 + (13 + 3) · 42n−1 = 3(3n+1 + 42n−1 ) + 13 · 42n−1 . By the induction hypothesis, 13 divides 3n+1 + 42n−1 so 3(n+1)+1 + 42(n+1)−1 is the sum of two multiples of 13 and hence is a multiple of 13. By induction, 3n+1 + 42n−1 is divisible by 13 for all n ≥ 1. Exercise: 14 Section 2.3 Question: A set of lines in the plane is said to be in general position if no two lines are parallel and no three

2.3. MATHEMATICAL INDUCTION

lines intersect at a single point. Prove that for any set {L1 , L2 , . . . , Ln } of lines in R2 in general position, the complement R2 − (L1 ∪ L2 ∪ · · · ∪ Ln ) consists of (n2 + n + 2)/2 disjoint regions in the plane. Solution: We prove the result by induction on n and we can start with n = 0. If n = 0, there are 0 lines and the complement R2 − (L1 ∪ L2 ∪ · · · ∪ Ln ) consists of a single disjoint region. Furthermore, if n = 0, then (n2 + n + 2)/2 = 2/2 = 1. So the formula holds for n = 0. Suppose that the for some n, formula is true for any set of n lines in general position. Now consider a set {L1 , L2 , . . . , Ln+1 } of n + 1 lines in general position. Then Ln+1 intersects each of the lines L1 , L2 , through Ln . The segments (possibly) rays on the line Li where Ln+1 intersects them form some of the boundary edges of n + 1 regions in R2 − (L1 ∪ L2 ∪ · · · ∪ Ln ). So Ln+1 cuts n + 1 regions in R2 − (L1 ∪ L2 ∪ · · · ∪ Ln ), adding n + 1 to the count. Hence, by induction, the complement R2 − (L1 ∪ L2 ∪ · · · ∪ Ln+1 ) consists of (n2 + n + 2)/2 + n + 1 disjoint regions in the plane. We have n2 + 2n + 1 + n + 1 + 2 (n + 1)2 + (n + 1) + 2 n2 + n + 2 + 2n + 2 = = . 2 2 2 Hence, the formula continues to hold for n + 1 lines. By induction, for all n ≥ 0, n lines in general position cut the plane into (n2 + n + 2)/2 regions. (n2 + n + 2)/2 + n + 1 =

Exercise: 15 Section 2.3 1 1 1 Question: Let Hn = 1 + + + · · · + be the nth harmonic number. Prove that H2n ≤ 1 + n. 2 3 n Solution: We prove by induction that H2n ≤ 1 + n for all n ≥ 0. For the basis step with n = 0, we notice that H1 = 1 and H1 ≤ 1 + 0. Hence, the inequality holds for n = 0. Suppose that the inequality holds for some n ≥ 0. Then 1 1 1 + + · · · . H2n+1 = H2n + 2n + 1 2n + 2 2n+1 Each of the fractions in the parentheses, is less than or equal to 21n and there are 2n of those fractions. Hence, 1 H2n+1 ≤ n + 1 + 2n n = (n + 1) + 1. 2 Hence, the inequality holds for n + 1 as well. By induction, H2n ≤ 1 + n for all n ≥ 0. Exercise: 16 Section 2.3 Question: Prove that n! ≤ nn−1 for all positive integers n. Solution: Let n = 1. Then 1! = 1 and 11−1 = 10 = 1. Hence, if n = 1, we have n! ≤ nn−1 . Now suppose that n! ≤ nn−1 for some positive n. Then, using the induction hypothesis, (n + 1)! = n!(n + 1) ≤ nn−1 (n + 1) Since n ≥ 1, then n ≤ n + 1 so nn−1 ≤ (n + 1)n−1 . We now use this with the above inequality to establish that (n + 1)! ≤ nn−1 (n + 1) ≤ (n + 1)n−1 (n + 1) = (n + 1)n . Thus, the inequality also holds for n + 1. By induction, n! ≤ nn−1 for all positive integers n. Exercise: 17 Section 2.3 n X Question: Show that i(i!) = (n + 1)! − 1 i=1

Solution: Basis Step: If n = 1, then

n X

i(i!) = 1 · 1! = 1 and also (1 + 1)! − 1 =. Hence, the formula holds for

i=1

n = 1. Induction Step: Suppose that the formula holds for some positive integer n. Then ! n+1 n X X i(i!) = i(i!) + (n + 1)(n + 1)! i=1

i=1

= (n + 1)! − 1 + (n + 1)(n + 1)! = (1 + n + 1)(n + 1)! − 1 = (n + 2)! − 1 = ((n + 1) + 1)! − 1.

CHAPTER 2. NUMBER THEORY

So the formula then also holds for n + 1. By induction,

n X

i(i!) = (n + 1)! − 1 for all n ≥ 1.

i=1

Exercise: 18 Section 2.3 Question: Show that any amount of postage of value 48 cents or higher can be formed using just 5-cent and 12-cent stamps. Solution: The question can be rephrased to say that for all integers n ≥ 48, there exist s, t ∈ N such that n = 5s + 12t. We prove this using strong induction. We can list a first few possibilities n 48 49 50 51 52 53

= 5s + 12t = 5 × 0 + 12 × 4 = 5 × 5 + 12 × 2 = 5 × 10 + 12 × 0 = 5 × 3 + 12 × 3 = 5 × 8 + 12 × 1 = 5 × 1 + 12 × 4

We see that there are solutions up to n = 54. (Strong Induction hypothesis) Suppose that n ≥ 53 and that for all 48 ≤ k ≤ n, there exist s, t ∈ N such that k = 5s + 12t. Consider now n + 1. Then by the induction hypothesis, there exists s0 , t0 ∈ N such that n + 1 − 5 = 5s0 + 12t0 . Then n + 1 = 5(s0 + 1) + 12t0 . Consequently, by strong induction, for all n ≥ 48, there exist s, t ∈ N such that n = 5s + 12t. Exercise: 19 Section 2.3 Question: Let A1 , A2 , . . . , An and B be sets. Use mathematical induction to prove that (A1 − B) ∩ (A2 − B) ∩ · · · (An − B) = (A1 ∩ A2 ∩ · · · ∩ An ) − B.

Solution: Let A1 , A2 , . . . , An and B be sets. Using induction on n, we prove that for all sets A1 , A2 , . . . , An and set B, (A1 − B) ∩ (A2 − B) ∩ · · · (An − B) = (A1 ∩ A2 ∩ · · · ∩ An ) − B. If n = 1 then A1 − B = A1 − B. Now suppose that for a given positive integer n, the formula (A1 − B) ∩ (A2 − B) ∩ · · · (An − B) = (A1 ∩ A2 ∩ · · · ∩ An ) − B is true for all sets A1 , A2 , . . . , An and B. Consider a collection A1 , A2 , . . . , An+1 of sets. Then (A1 − B) ∩ (A2 − B) ∩ · · · (An+1 − B) = ((A1 − B) ∩ (A2 − B) ∩ · · · (An − B)) ∩ (An+1 − B) = ((A1 ∩ A2 ∩ · · · ∩ An ) − B) ∩ (An+1 − B) = ((A1 ∩ A2 ∩ · · · ∩ An ) ∩ B) ∩ (An+1 ∩ B) = (A1 ∩ A2 ∩ · · · ∩ An+1 ) ∩ (B ∩ B) = (A1 ∩ A2 ∩ · · · ∩ An+1 ) ∩ B = (A1 ∩ A2 ∩ · · · ∩ An+1 ) − B. Hence, by induction, for all n ≥ 1 and all sets A1 , A2 , . . . , An and set B, we have (A1 − B) ∩ (A2 − B) ∩ · · · (An − B) = (A1 ∩ A2 ∩ · · · ∩ An ) − B.

Exercise: 20 Section 2.3 Question: Let α be any real number such that α + α1 ∈ Z. Prove that for all nonnegative integers n, αn +

1 ∈ Z. αn

2.3. MATHEMATICAL INDUCTION

Solution: Suppose that α ∈ R such that α + α1 ∈ Z. Obviously, for n = 0 or n = 1, we have αn + Now let n ≥ 2 suppose that αk +

1 . αn

1 ∈ Z for all k with 0 ≤ k < n. Then αk n X n 1 n n−2j α+ = α . α j j=0

By grouping together the jth element from the first and jth element from the last in the above binomial expansion, we have n (Pbn/2c n n−2j 1 α + αn−2j if n is odd 1 j=0 j Pn/2−1 n n−2j = α+ n 1 α α + αn−2j if n is even. j=0 n/2 + j Solving for αn + α1n we get 1 α + n = α n

1 α+ α

n −

(Pbn/2c n 1 αn−2j + αn−2j j=1 j P n/2−1 n n 1 αn−2j + αn−2j j=1 n/2 + j

if n is odd if n is even

! .

By the induction hypothesis, all terms in the summations on the right-hand side are integers. Hence, αn + α1n ∈ Z.

CHAPTER 2. NUMBER THEORY

3 | Groups 3.1 – Symmetries of the Regular n-gon Exercise: 1 Section 3.1 Question: Use diagrams to describe all the dihedral symmetries of the equilateral triangle. Solution: The equilateral triangle has 6 dihedral symmetries.

identity

rotation 120◦

rotation 240◦

reflection through x-axis

reflection

Exercise: 2 Section 3.1 Question: Write down the composition table for D4 . Solution: Composition table for D4 where the entries give a ◦ b. a\b 1 r r2 r3 s sr sr2 sr3

1 1 r r2 r3 s sr sr2 sr3

r r r2 r3 1 sr sr2 sr3 s

r2 r2 r3 1 r sr2 sr3 s sr

r3 r3 1 r r2 sr3 s sr sr2

s s sr3 sr2 sr 1 r3 r2 r

sr sr s sr3 sr2 r 1 r3 r2

sr2 sr2 sr s sr3 r2 r 1 r3

sr3 sr3 sr2 sr s r3 r2 r 1

Exercise: 3 Section 3.1 Question: Determine what r3 sr4 sr corresponds to in dihedral symmetry of D8 . Solution: In dihedral symmetry of D8 , we have the following algebraic identities on r and s: r8 = 1,

s2 = 1,

rk s = sr−k .

So for our element, progressively change it to put all the s terms to the left: r3 sr4 sr = r3 s(r4 s)r = r3 s2 r−4 r = r3 1r−3 = 1.

Exercise: 4 Section 3.1 Question: Determine what sr6 sr5 srs corresponds to as a dihedral symmetry of D9 . 67

(3.1)

CHAPTER 3. GROUPS

Solution: Recall from Corollary 3.5 that srk = rn−k s where in our case n = 9. So, sr6 sr5 srs = sr6 sr5 ssr8 = ssr3 r5 (1)r8 = (1)r8 r8 = r9 r7 = 1r7 = r7 .

Exercise: 5 Section 3.1 Question: Let n be an even integer with n ≥ 4. Prove that in Dn , the element rn/2 satisfies rn/2 w = wrn/2 for all w ∈ Dn . Solution: From the paragraph above Proposition 3.1.4 we can write w ∈ Dn as w = sa rb where a is either 0 or 1. Consider rn/2 sa rb . We have two cases. Case 1: a = 0 So we have rn/2 rb = rn/2+b = rb+n/2 = rb rn/2 . Case 2: a = 1 Now, rn/2 srb = srn−n/2 rb = srn/2 rb = srn/2+b = srb+n/2 = srb rn/2 . In both cases, we see that rn/2 w = wrn/2 . Exercise: 6 Section 3.1 Question: Let n be an arbitrary integer n ≥ 3. Show that an expression of the form ra sb rc sd · · · is a rotation if and only if the sum of the powers on s is even. Solution: For any numbers l and m we have rl sm = sm rl−m . So we can move all powers of s around without changing the exponent’s value. Since we can rewrite any element as sj rk , we have ra sb rc sd · · · = sb+d+··· rm for some m. Now, if b+d+· · · is an even number then sb+d+··· rm = s2 s2 · · · s2 rm = (1)(1) · · · (1)rm = 1rm = rm and our element is a rotation. If b+d+· · · is an odd number then sb+d+··· rm = s1 s2 · · · s2 rm = s(1)(1) · · · (1)rm = srm and our elements is not a rotation. Exercise: 7 Section 3.1 Question: Use linear algebra to prove that Rα ◦ Fβ = Fα/2+β ,

Fα ◦ Rβ = Fα−β/2

, and Fα ◦ Fβ = R2(α−β) .

Solution: As linear transformations on R2 → R2 , the matrices of the rotation Rα and of the reflection Fβ with respect to the standard basis are respectively cos α − sin α cos 2β sin 2β and . sin α cos α sin 2β − cos 2β The matrix for Rα ◦ Fβ is cos α − sin α cos 2β sin α cos α sin 2β

sin 2β − cos 2β

cos α cos 2β − sin α sin 2β cos α sin 2β + sin α cos 2β sin α cos 2β + cos α sin 2β sin α sin 2β − cos α cos 2β cos(α + 2β) sin(α + 2β) = . sin(α + 2β) − cos(α + 2β)

This matrix corresponds to the reflection Fα/2+β .

3.1. SYMMETRIES OF THE REGULAR N -GON The matrix for Fα ◦ Rβ is cos 2α sin 2α cos β sin 2α − cos 2α sin β

− sin β cos β

cos 2α cos β + sin 2α sin β − cos 2α sin β + sin 2α cos β = sin 2α cos β − cos 2α sin β − sin 2α sin β − cos 2α cos β cos(2α − β) sin(2α − β) = sin(2α − β) − cos(2α − β)

This matrix corresponds to the reflection Fα−β/2 . The matrix for Fα ◦ Fβ is cos 2α sin 2α cos 2β sin 2β cos 2α cos 2β + sin 2α sin 2β cos 2α sin 2β − sin 2α cos 2β = sin 2α − cos 2α sin 2β − cos 2β sin 2α cos 2β − cos 2α sin 2β sin 2α sin 2β + cos 2α cos 2β cos(2α − 2β) − sin(2α − 2β) = sin(2α − 2β) cos(2α − 2β) This matrix corresponds to the reflection R2(α−β) . Exercise: 8 Section 3.1 Question: Describe the symmetries of an ellipse with unequal half-axes. Solution: The ellipse with unequal half-axes has 4 symmetries. Supposing that the axes of the ellipse are on the x and y axes, then the ellipse has for symmetries: the identity, reflection through the x axis, reflection through the y axis, and rotation by 180◦ , which is the composition of the two reflections. Exercise: 9 Section 3.1 Question: List all the symmetries of the circle and describe the compositions between them. Solution: Assume that a circle has the origin as its center. The (dihedral) symmetries of the circle consist of all rotation Rα , where α ∈ R, and reflections Fβ , through a line through the origin that makes and angle β ∈ R with respect to the x-axis. he rotations are uniquely defined if α ∈ [0, 2π) and the reflections are uniquely defined if β ∈ [0, π). The compositions between these symmetries are Rα ◦ Rβ = Rα+β along with the other three compositions described in Exercise 3.1.7. Exercise: 10 Section 3.1 Question: List all the symmetries and describe the compositions between them for the infinitely long sine curve shown below: ...

...

Solution: It is useful to sketch the axes and the vertical line x = −π/2 and x = π/2. b ...

a ...

We see the the sine curve is symmetric with respect to reflection through the line marked a. We denote the reflection by a as well. The sine curve is also symmetric with respect to reflection through b. The sine function is also invariant under reflection through any line x = π2 + kπ. The function on R2 is fk (x, y) = ((2k + 1)π − x, y), where k can be an integer. The sine curve also stays invariant under a rotation by an angle π through the origin. (The sine function is odd.) The sine curve is also invariant under rotation by π around any point of (kπ, 0). The function on R2 is rk (x, y) = (2kπ − x, −y). The sine function is also periodic to it is invariant under a translation by 2π. The function for this is tk (x, y) = (x + 2kπ, y).

CHAPTER 3. GROUPS

The sine function also is invariant under a flip-translation described by the function on R2 given by ak = (x, y) = (x + (2k + 1)π, −y). There is a briefer way to list all the possible symmetries of the sine curve, but we will use this intuitive ones. We can summarize all compositions by the following chart. ◦ fm rm tm am

fn tm−n am−n−1 fm+n rm+n+1

rn am−n tm−n rm+n fm+n

tn fm−n rm−n tm+n am+n

an rm−n fm−n−1 am+n tm+n

Exercise: 11 Section 3.1 Question: List all the symmetries and describe the compositions between them for the infinitely long pattern shown below: ...

...

Solution: In the diagram, consider the point O and the vector ~v . . . . ~v O

...

This figure has the following symmetries, with k any integer: • reflection Fx through the x-axis; • translations Tk by any integer multiple k of the vector ~v ; • glide reflections Gk defined by Gk = Tk ◦ Fx ; −→ • rotations Rk/2 by 180◦ about any point A located on the x-axis at position OA = 21 k~v from O; −→ • reflections Fk/2 through a vertical line through any point A located on the x-axis at position OA = 12 k~v from O. (It is convenient to use vector notation to locate points because of the composition calculations that come below.) The compositions between these are given by the table the shows f ◦ g with f along the rows and g along the columns. (Note that I = T~0 is the identity.) Fx Tk Gk Rk/2 Fk/2

Fx I Gk Tk Fk/2 Rk/2

Tr Gk

Gr Tk

Rr/2 Fr/2

Fr/2 Rr/2

T(k+r) G(k+r) R(k−r)/2 F(k−r)/2

G(k+r) T(k+r) F(k−r)/2 R(k−r)/2

R(k+r)/2 F(k+r)/2 Tk−r Gk−r

F(k+r)/2 R(k+r)/2 Gk−r Tk−r

Exercise: 12 Section 3.1 Question: List all the symmetries and describe the compositions between them for the infinitely long pattern shown below: ...

Solution: We draw an x-axis through the pattern and fix an origin.

...