The first definition of an ordinal number I found was that an ordinal number is the $\in$-image of a well-ordered set $(A,\lt)$. From this definition it was derived that an ordinal is just the set of all lesser ordinals under the $\in$ well-ordering, and every ordinal is a transitive set.

Looking into other sources, I found that the $\in$ function is not even mentioned, but instead an ordinal is just defined as any transitive set of transitive sets. I see how the first definition implies the second, since any ordinal is transitive. But how does the second definition, which seems less restrictive to me for some reason, imply the first? Thank you.

  • $\begingroup$ Since under the second definition an ordinal is well-ordered under $\in$, wouldn't it satisfy the first definition by considering the identity map from the ordinal, considered as well-ordered set? $\endgroup$ – Arturo Magidin May 8 '11 at 2:04
  • $\begingroup$ @Arturo, I guess my misunderstanding then is why the second definition implies an ordinal is well-ordered by $\in$. I see that $\in$ gives a partial ordering. Also for any $B\subset\alpha$ for $\alpha$ an ordinal, $\cap B$ would be the $\in$-minimal element, right? But how is the ordering linear? $\endgroup$ – yunone May 8 '11 at 2:13
  • $\begingroup$ @Arturo, thanks, only if it's not a bother. The set theory I was learning so far didn't include Regularity as one of the axioms, so perhaps that's why it didn't seem obvious. $\endgroup$ – yunone May 8 '11 at 2:43
  • 2
    $\begingroup$ That would be why - without regularity the property isn't true (for instance, in $\mathrm{ZF}^-$ + AFA (the Anti-Foundation Axiom), the set $A=\{A\}$ is transitive but certainly not an ordinal.) $\endgroup$ – Steven Stadnicki May 8 '11 at 4:11
  • $\begingroup$ Note that $\omega\setminus 1$ (i.e. all strictly positive numbers) are still a well-order in $\in$, which is not $\omega$. You need to require slightly more. $\endgroup$ – Asaf Karagila May 8 '11 at 7:37

Okay, I cheated. This is based on these notes by William Weiss.

Let $A$ be a transitive set of transitive sets. We want to prove that $A$ is totally ordered with respect to $\epsilon$. I will assume the Axiom of Regularity.

Axiom of Regularity. For every $A$, $A\neq\emptyset$, there exists $x\in A$ such that $x\cap A = \emptyset$.

First we prove $\epsilon$ is a total order on $A$. If $A$ is empty, there is nothing to do. So assume $A$ is nonempty.

Claim 1. If $a,b\in A$, and $a\subseteq b$, then either $a=b$ or $a\in b$.

Let $$S = \{ b\in A\mid \text{there exists }a\in A\text{ such that }a\subseteq b\text{ and }a\neq b, a\notin b\}.$$ We want to show that $S$ is empty. If $S$ is not empty, then by the Axiom of Regularity there exists $b\in S$ such that $b\cap S=\emptyset$. Let $a$ be a witness to the fact that $b\in S$ (that is, $a\subseteq b$, $a\neq b$, and $a\notin b$.

Then $b-a$ is nonempty, so by the Axiom of Regularity there exists $x\in b-a$ such that $x\cap (b-a)=\emptyset$. Since $x\in b$ and $b$ is transitive, $x\subseteq b$; since $x\cap(b-a)=\emptyset$, then we must also have $x\subseteq a$. Since $x\in b$ but $a\notin b$, then $x\neq a$. Therefore, $a-x\neq \emptyset$. Again by Regularity there exists $y\in a-x$ such that $y\cap (a-x)=\emptyset$. Since $a$ is transitive and $y\in a$, $y\subseteq a$, and as above this implies that $y\subseteq x$ as well, since $y\cap(a-x)=\emptyset$.

Since $x\in b$, and $b\in A$, then $x\in A$. Moreover, since $b\cap S=\emptyset$, then $x\notin S$, so since $y\subseteq x$, it follows that either $y=x$ or $y\in x$. But $x\in b-a$, and $y\in a-x$, so we cannot have $y=x$, hence we conclude that $y\in x$. But $y\in a-x$, which means $y\notin x$. This contradiction arises from the assumption that $S\neq \emptyset$, so $S=\emptyset$.

Therefore, for any $a,b\in A$, if $a\subseteq b$, then either $a=b$ or $a\in b$.

Claim 2. If $a,b\in A$ and $b\not\subseteq a$, then $a\in b$.

Suppose that $b\not\subseteq a$. Using Foundation, let $x\in b-a$ such that $x\cap (b-a)=\emptyset$. Since $x\in b$ and $b$ is transitive, $x\subseteq b$, hence $x\subseteq a$ as well. By Claim 1, either $x=a$ or $x\in a$; the latter is impossible since $x\in b-a$, so $x=a$. Therefore, $a\in b$.

Putting the two together: let $A$ be a transitive set of transitive sets, and let $a,b\in A$. If $b\subseteq a$, then either $b=a$ or $b\in a$, by Claim 1; if $b\not\subseteq a$, then $a\in b$ by Claim 2. Either way, given any $a,b\in A$, we have that either $a\in b$, $a=b$, or $b\in a$, proving that $\epsilon$ is a strict total order on $A$.

  • $\begingroup$ Thanks Arturo for providing the proof. $\endgroup$ – yunone May 8 '11 at 6:49
  • $\begingroup$ @Arturo, I know this post is a few months old, but I just saw it. I am not seeing why it is necessary to prove the result in two stages. If we set $$ S = \{b\in A\mid \text{there exists }a\in A\text{ such that }b\not\subseteq a\text{ and }a\notin b\},$$ it appears to me that the reasoning you use to establish Claim 1 establishes that $S$ is empty. (Where does that reasoning use the fact that $a\subseteq b$?) But then the main result follows without any need for the construction in Claim 2. $\endgroup$ – Marian Oct 1 '11 at 11:55
  • $\begingroup$ @Marian: It's been a while since I typed that, but I think we use that $a\subseteq b$ to be able to apply to $y$ the same argument we just applied to $b$. If $a$ is not contained in $b$, then $y$ could be something in $a-b$. Yes, Claim 1 is established by showing that $S$ is empty, so of course the argument used to establish Claim 1 establishes $S$ is empty; that's how we are establishing claim 1. $\endgroup$ – Arturo Magidin Oct 1 '11 at 20:30
  • $\begingroup$ @Marian: you need 50 reputation points to comment on an answer. .@Arturo: Marian expanded the comment below and asked about this. $\endgroup$ – t.b. Oct 1 '11 at 22:41
  • 1
    $\begingroup$ @Marian: You’re right that the same argument shows that your $S$ is empty. And that is enough for the main result, though by a slightly different route: if $a,b\in A$, $a\notin b$, and $b\notin a$, then $b\subseteq a$ and $a\subseteq b$, so $a=b$. $\endgroup$ – Brian M. Scott Oct 1 '11 at 23:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.