Paul Halmos, Naive Set Theory

Exercises from section 25

Prove that each infinite cardinal number is a limit number.

A cardinal number was defined in this section as an ordinal number α such that if another ordinal number β is equivalent to α (i.e., there’s a bijection between them, they have the same cardinal number), then α ≤ β. Definition can be tricky: it is comparing the ordinals under bijection (i.e. how cardinals are compared) such that they are equal but then it reclassifies them under ordinal order to find the smallest (which gets defined as ‘the cardinal’).

Limit numbers were introduced way back. I had to look it up. They were transfinite ordinal numbers that lack immediate predecessors (so they are ‘the limit’ which is approached but not reached by a potentially infinite sequence of lesser ordinals).

Assume an infinite cardinal number ξ were not a limit number. Then it would have an immediate and strict predecessor ν: ν⁺ = ξ and ν < ξ. Also, ν and ξ belong to the same ordinal ‘class’ (i.e., they might be in the ω box, with ν = ω+10, and ξ = ω+11. The particular box - ω2, ω², ω^ω…- doesn’t matter). Let f be the bijection that maps ν to itself: f(ν) = ν. We define a bijection g: ν ↦ ξ through transfinite recursion thus: g(0) = ν and g(n⁺) = f(n). With this we establish that ν ∼ ξ, and we’ve arrived at a contradiction, as ν is an ordinal equivalent to ξ but ν < ξ.

If card A = a, what is the cardinal number of the set of all one-to-one mappings of A onto itself? What is the cardinal number of the set of all countably infinite subsets of A?

If A is finite, then a simple argument tells you that the cardinal number is a! by reasoning thus: given any set of n elements, if you think of permutations of the set to itself, you are thinking of all the possible permutations of elements of A with themselves. Such permutations are generated by a simple count: for the first chosen element (as we’re talking about well-ordered sets, there are no issues about ‘a first’, ‘a second’, etc… . Just go from least to least element of a diminishing set), you have n possible choices; for the second element, (n-1), and so on until there’s only one choice for the last element, so for any finite set of cardinal a, the answer is a(a-1)(a-2)…(1) = a!

If the set is infinite, ω ⪯ A. Now we saw when we talked about cardinal arithmetic that a^b is the cardinal of A^B, which can be described as the set of all functions from a set B to a set A. In our case, a^a would be the cardinal of all the functions from A to itself. Obviously, cardinal of the set of all one-to-one mappings of A onto itself (we’ll be calling it A^↔ for short) is a subset of a^a.

We can see that card(A^↔) can’t be less than a, given that there’s an injection F: A ↦ A^↔ that works like this: take the identity bijection, f₀, that maps every element to itself, and a fixed element a₀ ∈ A. For every x ∈ A, define F(x) = f_x*, where f_x* is a bijection obtained from f₀ by swapping x and a₀ (assuming x ≠ a₀) while leaving all other elements unchanged. Since each x produces a distinct bijection, this construction defines an injection from A into the set of bijections.

On the other hand, I can’t see how I could upper-bound card(A^↔). Something that would work would be knowing that a^a = a. This is true from what I’ve seen online (not only that: a^a = 2^a), but it wasn’t demonstrated by Halmos and seems to require some very sophisticated machinery, so we’ll have to leave it at that.

For the second task: If A is finite, there are no countably infinite subsets of A, so a = 0. If A is infinite, the situation is complex. To start with, a < 2^a, as the latter is the cardinal of the set 2^A of all functions from A ↦ 2 (or the Power Set of A), and the set of all countably infinite subsets ⊆ P(A).

If we think of the set of all countably infinite subsets of A, they could perhaps be represented by injective mappings ω ↦ A. Each such injection selects a distinct element of A for each natural number, producing a countably infinite subset. This would give us another upper bound, a^ω.

I am not sure how I could proceed to a more concrete answer. This seems Halmos again jumping to an absurd level of difficulty by proposing exercises that are both ambiguous and requiring really sophisticated mathematical machinery way above anything demonstrated in this book.

Prove that if α and β are ordinal numbers, then card (α + β) = card α + card β and card (αβ) = (card α)(card β). Use the ordinal interpretation of the operations on the left side and the cardinal interpretation on the right.

I really got bogged down here, trying to show all minute cases when α and β where finite, when one was finite but the other wasn’t and so on, so I checked another proof online that was suggested by a person called Sophie C., and which with some tweaking leads to a cleaner and simpler solution:

Let α and β be arbitrary ordinal numbers. Let’s use ⊕, ⊗ when we’re doing doing ordinal arithmetic and +, × when cardinal arithmetic. By the definition of ordinal addition and multiplication:

• α ⊕ β is the order type of a well-ordered set obtained by taking the disjoint union A ∪ B, with every element of A ordered before every element of B.

• α ⊗ β is the order type of a well-ordered set obtained from the Cartesian product A × B, with an appropriate ordering (e.g., reverse lexicographic).

Since cardinality depends only on the size of the set and not on the particular ordering, we have:

1. card(α ⊕ β) = card(A ∪ B) = card(A) + card(B) = card(α) + card(β)

2. card(α ⊗ β) = card(A × B) = card(A) ⋅ card(B) = card(α) ⋅ card(β)

Therefore:

card(α ⊕ β) = card(α) + card(β)

card(α ⊗ β) = card(α)⋅card(β)