Paul Halmos, Naive Set Theory

Exercises from section 19

This is a rather short section, and one that introduces the concept and definition of an ordinal number. It comes with of only a couple of implicit exercises.

Even though I had no issues grasping the main concepts of it, Halmos’s quirks have created difficulties. One is notation: for the successors of ω we get ω+1, ω+2, ω+3… when what is meant is nothing like addition, but rather, something like ω⁺, ω²⁺, ω³⁺…; that is to say, the nth iteration of the successor function + starting with ω.

Even worse is the introduction that precedes the definition of the Axiom of Substitution:

We know that for each natural number n we are permitted to form the set {x : S(n,x)}. In other words, for each natural number n, there exists a set F(n) such that x ∈ F(n) if and only if S(n,x) is true. The connection between n and F(n) looks very much like a function. It turns out, however, that none of the methods of set construction that we have seen so far is sufficiently strong to prove the existence of a set F of ordered pairs such that (n,x) ∈ F if and only if x ∈ F(n). To achieve this obviously desirable state of affairs, we need one more set-theoretic principle (our last). The new principle says, roughly speaking, that anything intelligent that one can do to the elements of a set yields a set.

I’ve found this hideously confusing, and am not sure I have managed to decipher it (luckily, it doesn’t seem to be necessary to understand what’s going on and the rest of the presentation). Before this we saw the concept of an ω-successor function: if you take the set of strict predecessors of a natural number n, and if n ≠ 0, you can define such a function such that f(0) = ω and f(m⁺) = (f(m))⁺ whenever m⁺ < n. This makes sense: the range of the function is going to be a collection with elements ω, ω⁺, ω²⁺, ω³⁺… . And if you think of the range of all possible ω-successor functions, this is looking pretty much like a set which is like the natural numbers but starting at ω and therefore going ‘beyond’ them.

This also gets reinforced with the next idea: if we think of some logical sentence S(n,x) “n is a natural number and x belongs to the range of the ω-successor function with domain n”, we can easily see how to use the sentence for building a set much like ω, ω⁺, ω²⁺, ω³⁺… but with all the possible successors of ω. Let T be the set of all x for which S(n,x) is true for some value of n. We can see that ω ∈ T, as S(1,ω) is true; ω⁺∈ T as well, as S(2,ω⁺) is also true and so on.

Now we get to the aforementioned quote. For each natural number n, its set F(n)= {x : S(n,x)}. It is easy to see that F(n) is going to have almost always more than one element; in fact, it is always going to have n elements for each n: F(1) = {ω}; F(2) = {ω, ω⁺}; F(3) = {ω, ω⁺, ω²⁺}, and so on. The connection between n and F(n) does ‘look very much like a function’, and would look even more so by representing n as the set of predecessors of n, i.e., if n = 2 = {0,1}, with a set of ordered pairs with domain F2 which could plausibly be {(0,ω), (1,ω⁺)}, and extensible to all n. Halmos tells us that the existence of such a set F requires an axiom (okay?), but then describes such a set as ‘a set F of ordered pairs such that (n,x) ∈ F if and only if x ∈ F(n)’. But this makes no sense: we saw that for a given n, there will usually be more than one x in F(n) -there’s two in F2, for example-, so this set s defined by Halmos would not be a function: it would contain, for example, (2,ω) and (2, ω⁺), with ω ≠ ω⁺ .

Anyway, let’s move on to the tasks proposed:

An easy proof by mathematical induction shows that for each natural number n, there exists a unique ω-successor function with domain n

First thing, the statement is a bit unclear. The definition of an ω-successor function, as shown above, explicitly excludes the case n = 0, so our base case will have to be n = 1.

Base case: If n = 1, the set of strict predecessors of 1 is the set {0}. If we define f(0) = ω , and given that there are no more elements in {0} that are <1, we have already arrived at a unique ω-successor function with domain 1: the function that maps 0 → ω.

Assume true for k, show it follows for k+1: As the statement is true for k, there’s a unique ω-successor function with domain k that maps every n < k to some successor of ω. Call this function f. The last mapped element of f was (k-1), so k is the strict successor of (k-1), and f(k-1) was formed by taken the previous value in the range, f(k-2), and applying the successor function to it, so f(k-1) = (f(k-2))⁺, and f(k-1) is the strict successor of f(k-2). We could apply the successor function to f(k-1) itself to get (f(k-1))⁺, and now we have all the elements for formulating an extension of function f. Call such a function F: F has the same input-output for values less then k, and for k, it maps k to (f(k-1))⁺. I claim this function F uniquely maps the initial interval of k⁺ to and is such that such that f(0) = ω and f(m⁺) = (f(m))⁺ whenever m⁺ < k⁺. Therefore, it follows that from assuming k is a unique ω-successor function with domain k, the same is also true for k⁺, and therefore this is true for each natural number n.

It is now easy to verify that ω2 is an ordinal number. The verification depends, of course, on the definition of order in ω2. At this point both that definition and the proof are left as exercises

Let's start with the definition of ordinal number: it is a well-ordered set α such that s(ξ) = ξ for all ξ in α, with s(ξ) being the initial segment of all elements in α < ξ.

Now, for the definition of order in ω2, it doesn't seem very difficult. You just define it as such: if ξ ∈ ω, we follow the usual order for the naturals. If ξ is ω or one of its successors, it follows the usual order where a successor is always greater than all its predecessors (and includes them as elements). When comparing a ξ ∈ ω with one not in ω, the latter is always greater.

As for proof, we can see that ω2 is a well ordered set (using the order definition just presented and given any subset of elements ξ of ω2, we can always determine a least element). If ξ ∈ ω, we saw that all natural numbers satisfy the rule that s(ξ) = ξ. If ξ is not in ω, the textbook showed that s(ω) = ω by definition of ω, so ω⁺ is an ordinal number, and we can keep extending this chain ad infinitum, covering all the elements of ω2.