MATH 582, INTRODUCTION TO SET THEORY, WINTER 1999

Answers to Problem Set 6 (Revised)

Problem 4.19 We want to prove the claim: for all natural numbers d and m, if d ≠ 0, then there exists natural numbers q, r such that m = d · q + r and r < d. Fix some d ≠ 0; we will prove the claim by induction on m. For the base case, notice that if m = 0, then we can take q = r = 0. Indeed, we have 0 = d · 0 + 0 by (M1) and (A1), and also 0 < d, because d ≠ 0. For the induction step, assume the claim holds for m. So there exist some q, r ∈ ω with m = d · q + r and r < d. Note that this implies r^{+} ⩽ d. We distinguish two cases: Case 1: r^{+} < d. In this case, we have m^{+} = d · q + r^{+} by (A2), and we are done. Case 2: r^{+} = d. In this case, we have m^{+} = d · q + d = d · q^{+} by (M2), so m^{+} = d · q^{+} + 0, and since 0 < d, we are also done.

Problem 4.20 Recall from p.83 that for natural numbers n and k, one has k ∈ − n ⟺ k ∈ n^{+}. By taking the negations of these statements and using trichotomy, one also gets that n ∈ k ⟺ n^{+} ∈ − k. We will use this fact in the following proof.

Suppose A is a nonempty subset of ω and ⋃ A = A. To prove A = ω, we show that A is inductive. Base case: Since A is nonempty, there is some natural number k ∈ A. Either k = 0, in which case we have 0 ∈ A as desired. Otherwise, 0 ∈ k ∈ A, hence 0 ∈ ⋃ A = A. Induction step: Suppose n ∈ A. Then, since A = ⋃ A, we have n ∈ ⋃ A, which implies n ∈ k for some k ∈ A. Since A is a set of natural numbers, k is a natural number. By the above observation, we have n^{+} ∈ − k. There are two cases: Case 1: n^{+} = k, thus n^{+} ∈ A and we are done. Case 2: n^{+} ∈ k ∈ A, hence n^{+} ∈ ⋃ A = A, and again we are done. Thus A is inductive, hence A = ω.

Problem 4.26 We proceed by induction on n. Let

T = {n ∈ ω | for all f : n^{+} → ω, ran f has a largest element}.

We will show that T is inductive. First consider any f : 0^{+} → ω. Since 0^{+} = {0} is a singleton, ran f = {f(0)} has exactly one element, which is automatically largest. This takes care of the base case. Now suppose that n ∈ T. To show that n^{+} ∈ T, consider any f : n^{++} → ω. We have to show that ran f has a largest element. Let g = f|n^{+} be the restriction of f to n^{+}; thus g : n^{+} → ω. By induction hypothesis, we know that ran g has a largest element, say, k. Also, ran f = ran g ∪ {f(n^{+})}. We distinguish two cases: Case 1: k < f(n^{+}). In this case, f(n^{+}) is the largest element of ran f. Case 2: f(n^{+}) ⩽ k. In this case, k is the largest element of ran f. In either case, ran f has a largest element, and since f was arbitrary, it follows that n^{+} ∈ T. Thus, T is inductive, which proves the claim.

Lemma. If n, k ∈ ω and n ∈ − k, then there exists x ∈ ω with k = x + n.

Proof. By induction on k. If k = 0 then n ∈ − k implies n = 0, and we can take x = 0. For the induction step, suppose the claim holds for k, and suppose n ∈ − k^{+}. Then either n = k^{+}, in which case one can take x = 0. Or otherwise n ∈ k^{+}, thus n ∈ − k, and we can find x with k = x + n by induction hypothesis. Then k^{+} = x^{+} + n, and we are done. □

Problem 4.37

(a) For fixed m, n ∈ ω, define the set M = {k ∈ m + n | k ∉ n}. We claim that M has m elements. Let ϕ : m → M be the map that is defined by ϕ(x) = x + n. We must show that ϕ is a well-defined map, and that it is a bijection. To see that ϕ is well-defined, we must check that x + n ∈ M for all x ∈ m. Note that if x ∈ m, then x + n ∈ m + n by Theorem 4N. Also, x ∉ 0 and thus x + n ∉ 0 + n = n, again by Theorem 4N. Thus, x + n ∈ M, and ϕ is well-defined. Also, ϕ is one-to-one by Corollary 4P. To see that ϕ is onto M, take any k ∈ M. Then k ∉ n, thus n ∈ − k by trichotomy. By the Lemma, there exists x ∈ ω with k = x + n. Since k = x + n ∈ m + n, it follows that x ∈ m by Theorem 4N, thus k = ϕ(x). This shows that ϕ is onto.

Notice that M and n are disjoint, by definition of M. We claim that m + n = M ∪ n. For the right-to-left inclusion, notice that M ⊆ m + n by definition. Also, 0 ∈ − m, thus n = n + 0 ∈ − n + m by Theorem 4N and Corollary 4P, thus n ⊆ n + m by Corollary 4M. So we have M ∪ n ⊆ m + n. For the left-to-right inclusion, take any k ∈ m + n. In case k ∈ n, we are done, otherwise k ∉ n, which implies k ∈ M. This shows m + n ⊆ M ∪ n.

Now we show the claim of part (a). Assume A, B are disjoint of m, respectively n, elements. Let f : m → A and g : n → B be bijections, and let ϕ : m → M be the bijection from above. Let h : M → A be the bijection given by h = f ∘ ϕ^{−1}. Using the fact that M and n are disjoint and that A and B are disjoint, it follows easily that h ∪ g : M ∪ n → A ∪ B is a bijection. From m + n = M ∪ n, it follows that A ∪ B has m + n elements.

(b) We first claim that m × n has m · n elements. Define ψ : m × n → m · n by ψ(x, y) = x · n + y. We claim that ψ is well-defined, and that it is a bijection. For well-definedness, we must check that ψ(x, y) ∈ m · n whenever x ∈ m and y ∈ n. But x ∈ m implies x^{+} ∈ − m, and thus x^{+} ·n ∈ − m·n. The last step follows by Theorem 4N, if n ≠ 0, and by (M1) if n = 0. Now y ∈ n implies x · n + y ∈ x · n + n = x^{+} · n ∈ − m · n. Thus ψ(x, y) ∈ m · n, and ψ is well-defined.

To show that ψ is one-to-one, assume that ψ(x, y) = ψ(x′, y′) for some x, x′ ∈ m and y, y′ ∈ n. Then x · n + y = x′ · n + y′. We must show x = x′ and y = y′. First, assume (for the sake of deriving a contradiction) that x ≠ x′. Then either x ∈ x′ or x′ ∈ x by trichotomy; we may assume without loss of generality that x ∈ x′. It follows that x^{+} ∈ − x′, thus x^{+} · n ∈ − x′ · n. This implies x · n + y ∈ x · n + n = x^{+} · n ∈ − x′ · n ∈ − x′ · n + y′, contradicting x · n + y = x′ · n + y′. Thus, it follows that x = x′. Now from x · n + y = x · n + y′ we can get y = y′ by cancellation (Cor. 4P).

Next, we show that ψ is onto m · n. If n = 0, then this is trivial, since m · n = 0 in this case. Thus, assume n ≠ 0 and take any k ∈ m · n. By Problem 4.19, there exist numbers x and y such that k = x · n + y and y ∈ n. We have x · n ∈ − k ∈ m · n, and thus x ∈ m by Theorem 4N. It follows that k = ψ(x, y). Thus ψ is a bijection.

Finally, we show the claim of part (b). Assume A has m elements and B has n elements. Let f : m → A and g : n → B be bijections. Define h : m × n → A × B by h(⟨x, y⟩) = ⟨f(x), g(y)⟩. One checks easily that h is a bijection. Then h ∘ ψ^{−1} is a bijection m · n → A × B, which proves that A × B has m · n elements.

Here is an alternative, easier proof of Problem 4.37 which uses induction.

(a) We show this claim by induction on n. If n = 0, then B = ∅, and hence A ∪ B = A has m = m + n elements. For the induction step, assume the claim holds for n. Suppose A has m elements, B has n^{+} elements, and A and B are disjoint. Then there exists some one-to-one and onto function f : n^{+} → B. Let B′ = f[[n]]; then clearly B = B′ ∪ f(n) and this union is disjoint. Moreover, the function f|_{n} : n → B is one-to-one and onto B′, so that B′ has n elements. Since B′ is still disjoint from A, the set A ∪ B′ has m + n elements by induction hypothesis. Thus, there is some one-to-one and onto function g : m + n → A ∪ B′. Let h = g ∪ ⟨m + n, f(n)⟩, then h is a one-to-one function of m + n^{+} onto A ∪ B, as desired.

(b) Again, we show the claim by induction on n. If n = 0, then B = ∅, and hence A × B = ∅, which has 0 = m · n elements. For the induction step, assume the claim holds for n. Suppose A has m elements and B has n^{+} elements. Then there exists some one-to-one and onto function f : n^{+} → B. As before, let B′ = f[[n]]; then again B = B′ ∪ f(n), this union is disjoint, and B′ has n elements. By induction hypothesis, A × B′ has m · n elements. Since A has m elements, and the set A is in one-to-one correspondence with the set A × {f(n)}, the latter set also has m elements. One also has A × B = A × B′ ∪ A × {f(n)} (by Problem 3.2(a)), moreover, the latter union is disjoint, and so by (a), A × B has m · n + m = m · n^{+} elements, as desired.

Problem 5.1 through 5.3 We must check whether each of the following functions from ω × ω to ω × ω is compatible with the relation ∼, which was defined by ⟨m, n⟩ ∼ ⟨m′, n′⟩ iff m + n′ = m′ + n.

f(⟨m, n⟩) = ⟨m + n, n⟩,
g(⟨m, n⟩) = ⟨m, m⟩,
h(⟨m, n⟩) = ⟨n, m⟩.

The function f is not compatible: for instance ⟨0, 0⟩ ∼ ⟨1, 1⟩, but ⟨0 + 0, 0⟩ ≁ ⟨1 + 1, 1⟩. The function g is trivially compatible, because for all m, m′, one has ⟨m, m⟩ ∼ ⟨m′, m′⟩. The function h is also compatible, because ⟨m, n⟩ ∼ ⟨m′, n′⟩ implies m + n′ = m′ + n implies n + m′ = n′ + m implies ⟨n, m⟩ ∼ ⟨n′, m′⟩.

Problem 5.7 Let a = [⟨x, y⟩] and b = [⟨w, z⟩]. Then

a ·_{ℤ} (−b) = [⟨x, y⟩] ·_{ℤ} (−[⟨w, z⟩])
= [⟨x, y⟩] ·_{ℤ} [⟨z, w⟩]
= [⟨xz + yw, xw + yz⟩],
(−a) ·_{ℤ} b = (−[⟨x, y⟩]) ·_{ℤ} [⟨w, z⟩]
= [⟨y, x⟩] ·_{ℤ} [⟨w, z⟩]
= [⟨yw + xz, yz + xw⟩]
= [⟨xz + yw, xw + yz⟩],
−(a ·_{ℤ} b) = −([⟨x, y⟩] ·_{ℤ} [⟨w, z⟩])
= −([⟨xw + yz, xz + yw⟩])
= [⟨xz + yw, xw + yz⟩].