# How does one define a well-ordering for the set of Zermelo ordinals?

For the von Neumann ordinals, $$\in$$ is the standard well-ordering.

I would like to know the standard way to define a well-ordering $$<$$ for the set of Zermelo ordinals.

In particular, I would like to know, for any two distinct Zermelo ordinals $$u$$ and $$v$$, how one determines, formally1, whether $$u < v$$ or $$v < u$$.

I assume that this definition of $$<$$ for Zermelo ordinals will depend only on Zermelo's axioms, with the possible addition of the Axiom of Foundation. At any rate, I am interested only in such a definition. (In particular, I would like to avoid any definition that requires the existence of the set $$\omega$$ of finite von Neumann ordinals.2)

In case the definition of Zermelo ordinals is not sufficiently standardized, below I give the one I know.

If $$w$$ is any set, let $$\rho(w)$$ be the formula that asserts $$\varnothing \in w \;\; \wedge \;\; \forall y\in w (\{y\} \in w).$$

Zermelo's original Axiom of Infinity postulates the existence of a set $$w$$ such that $$\rho(w)$$.

Let set $$z$$ be the smallest set $$w$$ such that $$\rho(w)$$ holds. Formally, $$z := \bigcap \,\{w : \rho(w)\}.$$

A "Zermelo ordinal" is an element of the set $$z$$.

1 I use the word "formally" here to rule out the method of "counting the number of curly braces." :)

2 On p. 42 of his The Foundations of Mathematics Kenneth Kunen contrasts Zermelo's original Axiom of Infinity (Axiom des Unendlichen: $$\exists w [\varnothing \in w \ \wedge \ \forall y\in w (\{y\} \in w)]$$), which justifies the existence of the set of Zermelo ordinals, with the now more standard Axiom of Infinity ($$\exists w [\varnothing \in w \ \wedge \ \forall y\in w (y \cup \{y\} \in w)]$$), which justifies the existence of the set $$\omega$$ of finite von Neumman ordinals. Kunen writes (my emphasis added):

...the two Axioms of Infinity are equivalent, although one needs to use [the Axiom of] Replacement (which Zermelo did not have) to prove the equivalence...".

As an exercise, I would like to prove, using the Axiom of Replacement, that the existence of the set $$z$$ of Zermelo ordinals implies the existence of the set $$\omega$$ of finite von Neumman ordinals, but all my attempts stumble for not having a proper definition of a well-ordering for $$z$$.

First, we need to show that transitive closures (of relations) exist. This can be done using the axiom of the power set and $$\Delta_0$$ separation without reference to the axiom of infinity. It can also be done with full separation.

The transitive closure of $$S \subseteq A^2$$ is simply $$\{(a, b) \in A^2 \mid \forall Q \subseteq A^2,$$ if $$Q$$ is transitive and $$S \subseteq Q$$ then $$(a, b) \in Q\}$$. You can easily verify that the transitive closure is the smallest transitive relation containing $$S$$.

Then $$< \subseteq z^2$$ is the transitive closure of $$\in_z = \{(a, b) \in z^2 \mid a \in b\}$$. Since $$\in_z$$ is well-founded and the transitive closure of a well-founded relation is also well-founded, we see that $$<$$ is well-founded. The fact that $$<$$ is a strict total order can be shown using induction.

Edit: Here's a proof that the transitive closure of a well-founded relation is well-founded.

Consider any relation $$\prec \subseteq S^2$$, and let $$<$$ be its transitive closure. Prove that $$x < y$$ if and only if either $$x \prec y$$ or $$\exists z \in S (z \prec y \land x < z)$$. Dually, we see that $$x < y$$ if and only if either $$x \prec y$$ or $$\exists z \in S (x \prec z \land z < y)$$.

A set $$Q \subseteq S$$ is said to be "inductive" with respect to $$\prec$$ if $$\forall x \in S (\{y \in S \mid y \prec x\} \subseteq Q \to x \in Q)$$. Then $$\prec$$ is said to be a well-founded relation if for all $$Q \subseteq S$$ which are inductive with respect to $$S$$, $$Q = S$$. We are defining the term "well-founded" here using well-founded induction.

Now suppose that $$\prec$$ is well-founded. We wish to demonstrate that $$<$$ is also well-founded. Consider some $$Q$$ which is inductive with respect to $$<$$. Define $$Q' = \{x \in S \mid \{y \in S \mid y < x\} \subseteq Q\}$$. Note that $$Q' \subseteq Q$$.

I claim that $$Q'$$ is inductive with respect to $$\prec$$. For consider some arbitrary $$x \in S$$, and suppose $$\{y \in S \mid y \prec x\} \subseteq Q'$$. Now suppose we have some $$y \in S$$ with $$y < x$$. Then there are two cases. The first is that $$y \prec x$$; in this case, we have $$y \in Q' \subseteq Q$$. The second is that there is some $$z \in S$$ such that $$z \prec x$$ and $$y < z$$. In that case, we know that $$z \in Q'$$, and therefore $$y \in Q$$. So in either case, we know that $$y \in Q$$. Thus, we see that $$\{y \in S \mid y < x\} \subseteq Q$$. Therefore, $$x \in Q'$$.

Since $$Q'$$ is inductive with respect to $$\prec$$ and $$\prec$$ is well-founded, we have $$Q' = S$$. Then we have $$S = Q' \subseteq Q \subseteq S$$, so $$Q = S$$. $$\square$$

Now we show that any well-founded relation $$\prec \subseteq S^2$$ is irreflexive. Define $$Q = \{x \in S \mid x \nprec x\}$$; we will show that $$Q$$ is inductive. Now consider an arbitrary $$x \in S$$, and suppose $$\{y \in S \mid y \prec x\} \subseteq Q$$. Suppose $$x \prec x$$. Then $$x \in Q$$; that is, $$x \nprec x$$. This is a contradiction. Therefore, $$x \nprec x$$; that is, $$x \in Q$$. Since $$Q$$ is inductive, we have $$Q = S$$, so $$S$$ is irreflexive. $$\square$$

Let's return to our original topic, the relation $$<$$ on the Zermelo ordinals. We have shown that $$<$$ is well-founded and thus irreflexive. And of course it is transitive, being a transitive closure. All that remains is to show that $$<$$ is total.

We demonstrate $$\forall a \in z \forall b \in z (a < b \lor a = b \lor b < a)$$ by induction on $$a$$.

The base case is $$\forall b \in z (0 < b \lor 0 = b \lor b < 0)$$. We actually strengthen what must be proved to $$\forall b \in z (0 < b \lor 0 = b)$$; this follows immediately from induction on $$b$$.

For the inductive step, suppose $$\forall b \in z (a < b \lor a = b \lor b < a)$$. We wish to show that $$\forall b \in z (Sa < b \lor Sa = b \lor b < Sa)$$. Consider some $$b \in z$$. By the inductive hypothesis, we know that either $$a < b$$, $$a = b$$, or $$b < a$$. If $$a = b$$ or $$b < a$$, then clearly $$b < Sa$$. If $$a < b$$, then we have two possibilities. The first is that $$a \in b$$; in this case, we have $$b = Sa$$. The second is that there is some $$c \in z$$ such that $$a \in c$$ and $$c < b$$. In this case, we actually have $$c = Sa$$, and therefore $$Sa < b$$. This completes the proof. $$\square$$

• Thanks! This way of defining transitive closure is handier for this problem than the one that Kunnen gives, because it does not require the use of $\omega$ at all. (Kunnen's is a recursive definition, and it does use $\omega$, though I suppose one could devise a similar definition that uses $z$ instead.) Unfortunately, I can't come even close to filling the missing bits in your argument, to prove that $<$, as you defined it, is well-founded on $z$ and that it is a strict total order on $z$ (other than the by-construction fact that $<$ is transitive on $z$). Can you point to a full proof?
– kjo
May 29 at 9:27
• @kjo I fleshed out the proof for you. You are correct that you run into a serious issue trying to define transitive closures in terms of the natural numbers if you only have $z$ and not $\omega$. You would like to define the transitive closure using finite sequences, but to discuss finite sequences, you would likely need to already have the $<$ operator in hand. May 29 at 17:03
• Thank you! There's a lot of interesting mathematics in your post. I did not know that way of defining well-foundedness. It was not at all obvious to me that it was equivalent to the definition I knew; it was very illuminating for me to work out the proof of this equivalence. I had not realized how much ground, mostly new to me, had to be covered to address my original question... For one thing, I still feel a bit wobbly on the properties of a relation's transitive closure. I will probably be posting some follow-up questions on this subject. (More targeted, I hope!) Thanks again!
– kjo
May 29 at 23:02
• @kjo A good question is one that raises more good questions. My definition of well-foundedness is more common among mathematicians who work with constructive logic, where you don’t assume $\forall P(P \lor \neg P)$. The traditional version of wellfoundedness is useless in this setting, since if we have a classically well-founded $\prec$ and any $a \prec b$, the law of excluded middle holds (by considering a set of the form $\{x \mid x =b \lor (x =a \land P)\}$, whose minimal element is either $a$ (meaning $P$ holds) or $b$ (meaning $\neg P$ holds). I’m glad you found the exercise illuminating. May 29 at 23:24