Paul Halmos - Naive Set Theory

Exercises from sections 12-14

Okay, so this was pretty tough. These sections in Halmos’s book explain the Peano Axioms and how to get addition, multiplication and exponentiation out of them. Solving some of these exercises definitely feels like trying to fight a boxing match with your hands tied. Folding your mind about the definitions of these operations and using only them to show stuff. A lot of cleverness in manipulations is required.

SECTION 12

Prove that if n is a natural number, then n ≠ n⁺

If n is a natural number, it is either 0 or some other n > 0. If it is 0, 0 = ∅, and n⁺ = {n ∪ {n}} = {∅}, and ∅ ≠{∅}.

If n is > 0, then n is a set with some elements: {x_1, x₂, x₃...}, and n⁺ contains all those elements and n itself: {x_1, x₂, x₃... n}, by definition of n⁺ according to the Peano axioms. Clearly, n ≠ n⁺ because they do not contain the same elements (n ⊆ n⁺ but n⁺ ⊄ n).

If n ≠ 0, show n = m⁺ for some natural number m

Let n ≠ 0. Then n is nonempty. Besides, n is a transitive set, so it includes elements (which are sets themselves) and all the elements of its elements. In fact, the successor function tells us that building any n is constructing a set that starts with the empty set and then keeps adding elements that are sets themselves and that contain as elements all the previous sets n'. Therefore, we can take the greatest element in n, the set than includes all the others in n as its elements (call it m). Then set n contains {m} and, because it is transitive, also includes all elements of m as elements, so n = m∪{m} = m⁺.

Prove that ω is transitive

To show that ω is transitive, we must show that if x ∈ y and y ∈ ω, then x ∈ ω. Perhaps we can proceed through mathematical induction.

We want to show that S: {y ∈ ω and all elements of y are elements of ω} = ω

Base case: y = 0 = ∅

We know, by Peano axioms, that 0 ∈ ω. Also, there is no x ∈ 0 that doesn't belong to ω (because there is no x ∈ 0. This is vacuously true), so indeed, 0 ∈ S.

Assume k ∈ S. Then k ∈ ω and all elements of k are elements of ω. By the successor function, we know k⁺ ∈ ω, and that k⁺= k ∪ {k}. Now, of the elements that belong to k⁺, we know k ∈ ω (by induction hypothesis), and we know the other elements of k⁺ are the elements of k, which also by the induction hypothesis are elements of ω. Therefore, if k ∈ S, k⁺ ∈ S, and therefore, S = ω

Prove that if E is a non-empty subset of some natural number, then there exists an element k in E such that k ∈ m whenever m is an element of E distinct from k.

Let e be a natural number, and let E be one of its non-empty subsets. This means e ≠ 0 = ∅, because in that case, there would be no non-empty subsets of e.

We can do a slightly modified induction proof starting at 1. What we'll show is that S: {e ∈ ω: ∀E ⊆ e ∃k ∈ E : (m ∈ E ∧ m ≠ k) → k ∈ m} = ω-{0}

Base case: e = 1 = {∅}

In this case, e only has one non-empty subset, which is itself, so E ={∅} and k = ∅. There is no m distinct from k in E, so it is vacuously true that k ∈ m, and as a consequence, 1 ∈ S.

Let's do a second case, e = 2 = {∅, {∅}}. 2 has two non-empty subsets: {∅} and itself. If E = {∅} and k = ∅. Like in 1, as there is no m distinct from k in E, it is vacuously true that k ∈ m. If E = {∅, {∅}} and k = ∅, then there is an m = {∅} ≠ ∅, and ∅ ∈ {∅}. Therefore, it is true that k ∈ m, and as a consequence, 2 ∈ S.

Assume λ ∈ S. Therefore, each non-empty subset E it contains has some element k such that k ∈ m for every other element m ∈ E that is not k.

What happens with λ⁺? As λ ∈ ω, λ⁺ ∈ ω, and λ⁺= λ∪{λ}. Now, the non-empty subsets of λ⁺ fall into two groups: those that include λ as an element and those that don't. Let's start with the latter. As all elements of λ are elements of λ⁺, subsets of λ⁺ that don't include λ are exactly all the subsets of λ itself, and from the induction hypothesis, we know each of those non-empty subsets satisfies our rule.

As for those that include λ, one way of seeing them is as each of the subsets E of λ in union with λ (for example, for the empty set, this is ∅∪λ = λ). Now we know that before adding λ, each subset did have k ∈ E such that k ∈ m for every other element m ∈ E that is not k. If we can show that k ∈ λ, the proof would be complete.

Given that k ∈ E, it follows k ∈ λ, as E were non-empty subsets of λ, and the only elements they can contain have to come from λ in the first place. Therefore, these non-empty subsets of λ⁺ also satisfy the rule, which means λ⁺ ∈ S. As a consequence, by induction, set S = ω-{0}.

SECTION 13

The proof that addition is commutative (i.e., m + n = n + m for all m and n) is a little tricky; a straightforward attack might fail. The trick is to prove, by induction on n, that (i) 0 + n = n and (ii) m⁺+ n = (m + n)⁺, and then to prove the desired commutativity equation by induction on m, via (i) and (ii).

This is dropped in a paragraph, but said proof is not spelled out, so let's see if I can do it.

(i) 0 + n = n

By induction. Base case, n = 0: 0 + 0 = s₀(0) = 0. True

Assume true for k, show true for k⁺: true for k means 0+k = s₀(k) = k. Now 0+k⁺= s₀(k⁺) = (s₀(k))⁺ = (k)⁺, so it is true that 0+k⁺= k⁺.

(ii) m⁺+ n = (m + n)⁺

By induction. Base case, n = 0: m⁺+ 0 = s_m+(0) = m⁺. And (m + 0)⁺= (s_m(0))⁺ = (m)⁺ = m⁺. So, m⁺+ 0 = (m + 0)⁺

Assume true for k [m⁺+ k = (m + k)⁺], show true for k⁺ [m⁺+ k⁺ = (m + k⁺)⁺]: m⁺+ k⁺= s_m+(k⁺) = (s_m+(k))⁺ = (m⁺ + k)⁺ = ((m + k)⁺)⁺ = ((s_m(k))⁺)⁺ = (s_m(k⁺))⁺ = (m+k⁺)⁺

Prove the desired commutativity equation (induction on m)

m+n = n+m

Base case, m = 0: Then equation turns to 0+n = n + 0. 0+n = n by (i). n+0 = s_n(0) = n by definition of addition, so base case is true.

Assume true for k [k+n = n+k], show true for k⁺ [k⁺+n = n+k⁺]: From (ii) we already know that k⁺+n = (k + n)⁺. As for n+k⁺, = s_n(k⁺) = (s_n(k))⁺ = (n+k)⁺, which by induction hypothesis equals (k + n)⁺, so indeed, k⁺+n = n+k⁺.

The discovery and establishment of the properties of powers, as well as the detailed proofs of the statements about products, can safely be left as exercises for the reader.

[Side note: the general statement 'can safely be left as exercises for the reader' is the kind of statement that the reader least likes to read, ever]

Distributive property of products and sums: k(m+n) = km + kn

By induction on n. Base case, n = 0. Then k(m+n) = k(m+0) = k(s_m(0)) = k(m) = km. Also, km + k(0) = km + p_k(0) = km + 0 = s_km(0) = km. So base case is proved.

Assume true for j [k(m+j) = km+kj], show true for j⁺ [k(m+j⁺) = km+kj⁺]. k(m+j⁺) = k(s_m(j⁺)) = k(s_m(j))⁺ = k(m+j)⁺ = p_k(m+j)⁺= p_k(m+j) + k = k(m+j) + k = km+kj +k. On the other hand, km+kj⁺= km + p_k(j⁺) = km + p_k(j) + k = km+kj +k. This proves k(m+j⁺) = km+kj⁺.

Associativity of products: (ab)c = a(bc)

By induction on c. Base case, c = 0. Then (ab)0 = p_ab(0) = 0. Also, a(b0) = a(p_b(0)) = a(0) = p_a(0) = 0. So base case is proved.

Assume true for k [(ab)k = a(bk)], show true for k⁺ [(ab)k⁺ = a(bk⁺)]. (ab)k⁺ = p_ab(k⁺) = p_ab(k) + ab = (ab)k + ab = a(bk) + ab = a((bk) + b) = a(p_b(k⁺)) = a(bk⁺). This proves (ab)k⁺ = a(bk⁺).

Commutativity of products: ab = ba

Like the commutativity of addition, what we need will probably require intermediate steps. If we were to try to show ab = ba and, say, try induction on a, we can see that the base step produces a first problem, in that we know what b0 is (p_b(0) = 0) but we haven't shown what 0b is. We have to deal with that intermediate step, using induction on b:

(i) 0b = 0

By induction on b. Base case: b=0. Then, 0.0 = p₀(0) = 0.

True for k [0k = 0], show true for k⁺ [0k⁺ = 0]. 0k⁺= p₀(k⁺) = p₀(k)+0 = (0k) + 0 = 0 + 0 = s₀(0) = 0, so 0k⁺ = 0 is true.

So now we can proceed to show the base case for showing, by induction on a, that ab = ba. Base case, a=0. Then 0b = 0 (as we've shown in (i)) and b0 = p_b(0) = 0.

For the next step we'd need to assume the case for k: kb = bk  and show that if follows for k⁺b = bk⁺. In the way Halmos has defined multiplication, we can pretty straightforwardly deal with the bk⁺, but not so much with the other end of the equation. So, we start with bk⁺=(bk)+b = b + (bk) (commutativity of sums) = b + (kb) (by induction hypothesis).

To complete the proof, we'd need to show that k⁺b = b + (kb) as well, so this is our next intermediate step, using induction on b:

[note: this was the place where I really, really, really got suck. I spent three days trying to work out both what I needed as the intermediate step and messing up attempts with different things. Had to look for some help]

(ii) k⁺b = b + (kb)

By induction on b. Base case, b=0. Then k⁺(0) = p_k+(0) = 0, and 0 + (k0) = 0 + (p_k(0)) = 0 + 0 = s₀(0) = 0.

True for h [k⁺h = h + (kh)], show true for h⁺ [k⁺h⁺ = h⁺ + (kh⁺)]. k⁺h⁺= k⁺(h)+k⁺ = k⁺+ k⁺(h) = k⁺+ h + (kh) = k + h⁺+(kh) = k +(kh) + h⁺= (kh) + k + h⁺= (kh⁺) + h⁺= h⁺ + (kh⁺)

Laws of powers - the following are the ones that only use sums, products, and natural number coefficients

Law of Products: a^m × aⁿ = a^m+n

Law of Power of a Product: (a×b)^m = a^m×b^m

Law of Power of a Power: (a^m)ⁿ = a^{m x n}

Although it is not required, we will probably need to prove a few things about 1 which we might need to use in the following proofs. 0⁺=1 and, as we saw, e_a(0) = 1. Things we could prove:

n+0⁺ = n⁺

By induction on n, base case: if n = 0, 0+0⁺ = 0⁺. Assume true for k (k+0⁺ = k⁺) and show true for k⁺ (k⁺+ 0⁺ = (k⁺)⁺).  (k⁺)⁺= (k+0⁺)⁺ = k⁺+ 0⁺.

(in the following, I'll just use 1 for 0⁺)

a × 1 = a

Base case, a=0. Then 0 x 1 = 0 x 0⁺ = p₀(0⁺) = p₀(0) + 0 = 0 + 0 = 0

True for k, show for k⁺: k⁺ x 1 = k⁺ x 0⁺ = p_k+(0⁺) = p_k+(0) + k⁺ = 0 + k⁺ = k⁺

As commutativity of products was shown above, this implies 1 x a = a

e_a(1) = a

e_a(1) = e_a(0⁺) = e_a(0) x a = 1 x a = a  = a¹

e₁(n) = 1

If n = 0, this is true by definition of exponentiation.  Assume true for n, show it follows for n⁺:  e₁(n⁺) = e₁(n) x 1 = 1 x 1 = 1

We can now move on to tackle the three product laws above:

Law of Products: a^m × aⁿ = a^m+n

By induction on m. Base case: if m = 0, e_a(0) = 1. 1× e_a(n) = e_a(n) = aⁿ = a⁰⁺ⁿ.

Assume true for k, show for k⁺: e_a(k) × e_a(n) = e_a(k+n)  =>  e_a(k⁺) × e_a(n) = e_a(k⁺+n)   

e_a(k⁺) × e_a(n) = e_a(k) × e_a(1) × e_a(n) = e_a(k) × e_a(n) × e_a(1)  = e_a(k+n) × a = e_a(k+n)⁺ = e_a(k⁺+n)

Law of Power of a Product: (a×b)^m = a^m×b^m

By induction on m. Base case: if m = 0, (a×b)⁰, assuming product of a×b is some natural number c (need to prove this?) = c⁰ = 1. Likewise, a⁰×b⁰ = 1×1 = 1

True for k, show for k⁺: (a×b)^k = a^k×b^k => (a×b)^k+ = a^k+× b^k+

(a×b)^k+ = e_{a x b}(k⁺) = e_{a x b}(k)a x b = (a x b)^ka x b = a^k x b^k x a x b (a^k x a) (b^k x b) = by law of powers to a^k+ × b^k+

Law of Power of a Power: (a^m)ⁿ = a^mn

(really messy having to use x for product here, so I'll just ignore it)

By induction on m. Base case: if m = 0, e_a(0) = 1, and 1ⁿ = e₁(n) = 1. Meanwhile, a^0.n = a⁰ = e_a(0) = 1.

Assume true for k, show for k⁺: (a^k)ⁿ = a^kn => (a^k+)ⁿ = a^k+n

(a^k+)ⁿ = (e_a(k⁺))ⁿ = (e_a(k)a)ⁿ =(a^ka)ⁿ = by law of power of a product to (a^k)ⁿ × aⁿ = a^kn × aⁿ = by law of powers to a^kn+n = a^nk+n = a^nk+ = a^k+n

Exercise: Prove that if m < n, then m+k < n+k, and prove that if m < n and k ≠ 0, then m.k < n.k. Prove that if E is a non-empty set of natural numbers, then there exists an element k in E such that k ≤ m for all m in E.

if m < n, then m+k < n+k

By induction on k. If k = 0, m+k = m, n + k = n and  as m < n, m+0 < n+0

True for j, show it follows for j'

By definition of addition, m+ j' = (m+j)' and (n+j)'= (n+j)'. IH says m+j < n+j. This means (m+j) ∈ (n+j), and therefore, (m+j) ∈ (n+j)'.

As (m+j) ∈ (n+j), (m+j)' is either = (n+j) or < (n+j). If (m+j)' = (n+j), as (n+j) ∈ (n+j)', then (m+j)' ∈ (n+j)'. If (m+j)' < (n+j), then (m+j)' ∈ (n+j) and as all elements of the latter also belong to its successor, then (m+j)' ∈ (n+j)'. Therefore, (m+j)' < (n+j)'.

(really messy also having to use + as a superscript, so I've decided to use ' instead of Halmos's notation. a⁺ = a')

if m < n and k ≠ 0, then mk < nk

By induction on k, but we start at k=1, instead of 0. If k=1, m x 1 = m and n x 1 = n, and so we get m x 1 < n x 1 = m < n, which we know by hypothesis to be true.

True for j, show it follows for j'

mj' = mj + m. Likewise, nj' = nj + n. IH tells us mj < nj.  We also know that m < n. So, from the previous exercise, mj + m < nj + m, and nj + n < nj + n. Applying the same principle, nj + m < nj + n. Combining inequalities, we see that mj + m < nj + n = mj' < nj'

if E is a non-empty set of natural numbers, then there exists an element k in E such that k ≤ m for all m in E.

Proof by induction. Let ∣E∣ represent the number of elements of E. As E is non-empty, it contains at least one element, so 1 ∈ ∣E∣. Let n be such an element. If it only contains n, E = {n} and the statement is trivially true, as n ≤ n, which is the only element in E, so n = k.

Assume the statement is true for some natural number j (that is, if the number of elements of ∣E∣ is j, then there exists an element k in E such that k ≤ m for all m in E), show it follows for j⁺. By Induction Hypothesis, E contains j elements, and it contains an element k_j ≤ m for all m ∈ E. Now let us add one more element, n, to E, turning it into E', and such that now ∣E'∣ is  j+1 = j⁺ elements. By Trichotomy, it must be the case that either k_j ≤ n or k_j > n. If k_j ≤ n, then k_j ≤ m for all m in our expanded set E'. k_j > n, then n < k_j ≤ m. In either case we have shown that when the number of elements of ∣E'∣ is j⁺, there is some element of E' that is strictly smaller, or smaller than or equal than every element of the set, completing the proof.

Exercise: 'A set E is called finite if it is equivalent to some natural number; otherwise, E is infinite'. Use this definition to prove that ω is infinite

(tried different stuff but wasn't able to get a satisfactory answer, even if I had the core 'good' idea of using the existence of successors in ω to somehow find an element in it that couldn't be an image. Read a solution online by some smart guy called George Mplicas, and this was my attempt to reconstruct it some time after having read it)

If ω is finite, it is equivalent to some natural number n. The equivalence means there exists a bijective function f from ω to n such that every element of n gets mapped to and no two different elements of ω map to the same element in n.

Let us build a set E with every x that is the unique preimage of each y ∈ n. We can now take ∪E, and what we get is a set that will be equal to some natural number g (as ∪E is a set of natural numbers, each of which contains as elements all the natural numbers that precede it, the union will effectively be natural number g ≥ x for every x ∈ E). Now take g⁺, which must exist by the properties of ω.  g⁺ = {g ∪ {g}}. This means that g⁺ cannot be an element of E, as it contains g and every x ∈ E, and every subset of E is a subset of g⁺. But this means the function f, when applied to g⁺, cannot map it to any element y ∈ n, as all the x_s that mapped thereon had already been included in the set E. Contradiction: therefore, ω is not finite.

Exercise: 'A finite set is never equivalent to a proper subset'. Use this consequence of the definition of finiteness to prove that ω is infinite.

By contradiction. Assume ω is a finite set. Consider the function f explained in p. 52 such that f, which maps from ω to ω-{0}, is f(n) = n⁺. The first thing we observe is that ω-{0} ⊆ ω: it is, in fact, a proper subset, as it contains all elements of ω except one. Now, consider f. First, lets us show that it is injective. Let m and n be any two elements of n. Then f(m) = m⁺ and f(n) = n⁺. Peano axiom V clearly tells us that if, in such a case, m⁺= n⁺, then m = n. This means our function f is injective.

Now let's show surjectivity. Let us show that the set E = {j ∈ ω: j = n⁺} = ω-{0}. By induction, we start with 1. 1=0⁺, so 1 ∈ E. Assume true for k, show it follows for k⁺. We know k ∈ ω, k≠0 and k = n⁺. By Peano Axiom II, k⁺ ∈ ω, so we have that k⁺ is a successor of k and it is also an element of ω, so E = ω-{0}.  

Given that we've shown that f is actually a bijective function from ω to a proper subset of ω, we have reached a contradiction, and ω cannot be a finite set.

Exercise: The union of a finite set of finite sets is finite. If E is finite, then 𝒫(E) is finite, and moreover, #( 𝒫(E)) = 2^#(E). If E is a non-empty finite set of natural numbers, then there exists an element k in E such that m ≤ k for all m in E.

Let X be our finite set. As it is finite, it is composed of sets x₁, x₂, x_3..., each of them also finite, so x₀ = {x₀₀, x₀₁, x₀₂...}, x₁ = {x₁₀, x₁₁, x₁₂...} and so on. We are asked to show that ∪X = { x₀₀, x₀₁, x₀₂..., x₁₀, x₁₁, x₁₂...} is finite. The number of sets in X is some #n, equivalent to a natural number, so we can establish a bijection from the subset of ω = {0,1,2,3... n} to X, allowing us to label all the sets. Now we can proceed to pairwise unions, starting with (x₀ ∪ x₁). The union of two finite sets is finite, so (x₀ ∪ x₁) is also finite. We can proceed with ((x₀ ∪ x₁) ∪ x₂), and keep iterating until we reach x_n. Each of the sets we will be generating in the process has to be finite, and once we've reached to the end, the set we have arrived at is ∪X, which has to be finite.

Let E be a finite set. It therefore has a cardinal number of elements, #(E), which is equivalent to some natural number n. Now let's think of how many elements its power set must contain. Given that E has n elements, to construct all subsets of E we can take the string of all the elements in E = {e₀,e₁,e₂,e₃... e_n} and for each element decide if the subset does not include it (value: 0) or includes it (value: 1). In this way we get a string with all the possible combinations of n 1_s and 0_s, starting with all 0_s (the empty set) to all 1_s (the set itself), and everything in between. Given n #(E), and for every n we get 2 choices, the total number of choices is 2ⁿ, which is also something relatively easily shown through mathematical induction. And this number is a natural number and a cardinal, as potentiation was a valid operation closed within ω.

As for the last proof, I made above a proof that if E is a non-empty set of natural numbers, then there exists an element k in E such that k ≤ m for all m in E. That proof would work in exactly the same way here, but using ≥.

SECTION 14

Exercise: express the conditions of antisymmetry and totality for relation R by means of equations involving R and its inverse.

The formal version of antisymmetry would be something like so:

 (xRy)∧(yRx) → x = y

The idea of using R^-1 brings in this concept: if an element in an antisymmetric relation has an inverse, its inverse must be equal to itself:

(xRy)∧(xR^-1y) → x = y

The formal version of totality would be something like so:

(x ∈ X) ∧ (y ∈ X) → (xRy)∨(yRx)

Using R^-1 turns it to:

(x ∈ X) ∧ (y ∈ X) → (xRy)∨(xR^-1y)

The idea might be that given a total relation, every element must have an inverse.