4
$\begingroup$

This question is about von Neumann's informal definition of ordinals as "sets of all smaller ordinals" and was discussed in this math.stackexchange question.

When trying to formalize this definition, I came to this: let's consider an arbitrary class $\mathrm{No}$ with the property $\forall s\in \mathrm{No} \Rightarrow s=\{x\in \mathrm{No}: x\subset s\}$, where $\subset$ denotes a strict embedding. It's easy to prove that every $s\in \mathrm{No}$ is transitive, but I faced some problems proving that $\mathrm{No}$ is well-ordered by $\in$, though I feel it's true. I tried to use induction on $\operatorname{card}(\mathrm{No})$, but it seemed inconvenient even for the finite cardinals. Maybe someone knows a nice proof of this fact?

Improve this question
$\endgroup$
7
  • 5
    $\begingroup$ I guess you can show by induction on $\alpha$ that for any ordinal $\alpha$, if there is any element of ${\rm No}$ of rank $\alpha$ then there is only one and it is an ordinal. Thus ${\rm No}$ is either an ordinal or the class of all ordinals. $\endgroup$
    – Nik Weaver
    Commented Sep 17, 2019 at 22:58
  • 1
    $\begingroup$ Show that if $s \in \mathrm{No}$ then $s$ is a (transitive) set of ordinals and hence an ordinal. So $\mathrm{No}$ is a transitive class of ordinals and therefore $\mathrm{No}$ is either an ordinal or the class of all ordinals. For the first part consider $x \in s$ a counter example of minimal rank. $\endgroup$
    – Ramiro de la Vega
    Commented Sep 17, 2019 at 23:28
  • $\begingroup$ @RamirodelaVaga isn't that exactly what I said? $\endgroup$
    – Nik Weaver
    Commented Sep 18, 2019 at 0:00
  • $\begingroup$ Please never use $\textit{strict}$ again to italicise text. If you want it in (La)TeX, use \emph{...} and on stackexchange sites and MO use _underscores_ $\endgroup$
    – David Roberts ♦
    Commented Sep 18, 2019 at 0:04
  • $\begingroup$ @NikWeaver Well it can’t be exactly what you said, because I understand Ramiro de la Vega’s comment, but I don’t quite understand yours (specifically, what do you need “... then there is only one” for). $\endgroup$
    – Emil Jeřábek
    Commented Sep 18, 2019 at 8:14

3 Answers 3

Reset to default
6
$\begingroup$

(Alexander: In light of our exchange of comments, I have slightly revised the first sentence of my response to better reflect my intention.)

Perhaps you will find the following alternative formalization of the familiar informal characterization of a von Neumann Ordinal to be of interest.

A set $\alpha$ is a von Neumann ordinal if and only if there is a well-ordering $<_\alpha$ of $\alpha$ such that for each $y \in \alpha$, $y=\{x \in \alpha: x <_{\alpha}y \}$.

Proof. It is evident that an ordinal defined à la von Neumann is a von Neumann ordinal in the above sense. To establish the converse, let $x,y,z \in \alpha$. (i) If $x \in y$ and $y\in z$, then $x<_{\alpha} y$ and $y<_{\alpha} z$, which implies $x<_{\alpha} z$, which in turn implies $x\in z$. Moreover, (ii) since exactly one of $x=y$, $x<_{\alpha} y$ and $y<_{\alpha} x$ is the case, it follows that exactly one of $x=y$, $x\in y$ and $y\in x$ is the case, which shows $\alpha$ is totally order by $\in$. Now let $A$ be a subset of $\alpha$. Then $A$ has a $<_\alpha$-least member; and since $\in$ totally orders $\alpha$, $A$ has an $\in$-least member, which implies $\in$ well-orders $A$. To complete the proof note that every element of $\alpha$ is a subset of $\alpha$.

Edit: The above alternative definition of a von Neumann ordinal comes from p. 254 of my paper All numbers great and small, in Real Numbers, Generalizations of the Reals, and Theories of Continua, edited by P. Ehrlich, Kluwer Academic Publishers, Dordrecht, pp. 239-258.

Improve this answer
$\endgroup$
9
  • $\begingroup$ Yes, but now I have to show that $\in$ provides such a well-ordering! $\endgroup$
    – Alexander Kuleshov
    Commented Sep 18, 2019 at 2:13
  • 1
    $\begingroup$ @Alexander: did you read my comment? I answered your question. Do you need a more detailed explanation? $\endgroup$
    – Nik Weaver
    Commented Sep 18, 2019 at 2:49
  • $\begingroup$ Thanks, Nik! I've read your comment and I think I'll have to think about it a bit, because set theory and transfinite induction is not really my cup of tea, you know.) And even the ordinals never bothered me until today, but these "vicious circle-type definitions" always excite! So I'll react a bit later, if you don't mind... But the above answer doesn't get us there! $\endgroup$
    – Alexander Kuleshov
    Commented Sep 18, 2019 at 3:45
  • $\begingroup$ No worries, just ask if you want more details. $\endgroup$
    – Nik Weaver
    Commented Sep 18, 2019 at 14:27
  • $\begingroup$ @Alexander. I just added a proof. Does this help or have I misunderstood your comment? $\endgroup$
    – Philip Ehrlich
    Commented Sep 18, 2019 at 14:57
5
$\begingroup$

In order to prove that any class $\mathrm{No}$ satisfying this definition is well-ordered by $\in$ it is crucial to use the axiom of foundation. Axiom of foundation tells us that $\in$ is a well-founded relation. Thus we only need to prove that any two elements of $\mathrm{No}$ are $\in$-comparable. This could be achieved by a proof by a contradiction, where we consider a $\in$-pointwise-minimal $\in$-incomparable pair $a,b\in\mathrm{No}$ to get to a contradiction. This is essentially the same as the arguments that use ranks of sets suggested in the comments (one needs axiom of foundation to prove that every set has a rank), but formulated in the terms of more elementary notions.

If one drops the axiom of foundation, then we could have models, where there are classes satisfying this definition, although not being well-ordered by $\in$-relation. For example, it is possible to have a model with two chains of sets $a_i=\{a_j\mid j>i\}$ and $b_i=\{b_j\mid j>i\}$ such that all $a_i$ and $b_i$ are pairwise distinct sets. Clearly, $\{a_i\mid i\in\omega\}\cup \{b_i\mid i\in\omega\}$ satisfies your definition, but is neither linearly ordered nor well-founded.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks! It's curious, that the situation you described is impossible when $\mathrm{No}$ is finite. If $card(\mathrm{No})=2$, then I don't need the axiom of foundation to show that $\mathrm{No}=\{\varnothing, \{\varnothing\} \}$, and so on... $\endgroup$
    – Alexander Kuleshov
    Commented Sep 18, 2019 at 16:19
  • $\begingroup$ Can you please explain "we consider a $\in$-pointwise-minimal $\in$-incomparable pair $a,b\in\mathrm{No}$ to get to a contradiction" in more details? You suggest to consider a set of all $\in$-incomparable pairs $(x,y)$ and find such an incomparable $(x_0,y_0)$ that $(x,y) \notin (x_0,y_0)$ for each incomparable $(x,y)$? $\endgroup$
    – Alexander Kuleshov
    Commented Sep 19, 2019 at 18:20
  • $\begingroup$ @Alexander Indeed, I was a bit unprecise in this point. Let us consider order $(x,y)\preceq(z,w)$ iff ($x\in z$ or $x=z$) and ($y\in w$ or $y=w$); note that well-foundedness of $\in$ implies well-foundedness of $\preceq$. Here it is sufficient to consider $\in$-incomparable pair $(a,b)\in\mathrm{No}^2$ that is $\preceq$-minimal. $\endgroup$
    – Fedor Pakhomov
    Commented Sep 19, 2019 at 20:03
  • $\begingroup$ Sorry for being impatient, but I can't quickly see the contradiction... Now we must introduce an incomparable $(a^\prime, b^\prime)$ strictly smaller then $(a,b)$. $\endgroup$
    – Alexander Kuleshov
    Commented Sep 19, 2019 at 21:12
  • 1
    $\begingroup$ For this $(a,b)$ let us consider arbitrary element $b'\in b$. By $\preceq$-minimality of $(a,b)$ element $b'$ should be $\in$-comparable with $a$, since $(a,b')\prec (a,b)$. But $b'$ couldn't be equal to $a$ (then $a=b'\in b$ contradicts incomparability of $a$ and $b$) and $a$ couldn't be element of $b'$ (then $a\in b'\in b$ which is impossible since $b$ is transitive). Thus $b'\in a$. Since $b'\in b$ was arbitrary, $b\subseteq a$. For the same reason $a\subseteq b$. Hence $a=b$, contradiction. $\endgroup$
    – Fedor Pakhomov
    Commented Sep 19, 2019 at 21:28
2
$\begingroup$

Okay, here is an expanded version of my comment. Let ${\rm No}$ be a class of sets with the property that every the elements of any $x \in {\rm No}$ are precisely the proper subsets of $x$ which belong to ${\rm No}$.

Theorem: ${\rm No}$ is either an ordinal or the class of all ordinals.

Proof: We will prove by induction on $\alpha$ that for any ordinal $\alpha$, if there is an element of ${\rm No}$ of rank $\alpha$ then there is exactly one such element, and it is $\alpha$ itself. As it follows immediately from the condition on ${\rm No}$ that any element of a set in ${\rm No}$ also belongs to ${\rm No}$, this means that ${\rm No}$ is a class of ordinals which contains every ordinal less than any ordinal it contains, which implies the theorem.

Let $\alpha$ be an ordinal and suppose the claim is true for all smaller ordinals. Let $x$ be an element of ${\rm No}$ whose rank is $\alpha$. By the definition of rank, it follows that the ranks of elements of $x$ are cofinal in $\alpha$. (This includes both the successor and limit cases.) But the induction hypothesis implies that every element of $x$ is an ordinal. As it is immediate from the condition on ${\rm No}$ that $x$ is transitive, this implies that $x$ is precisely the set of all ordinals less than $\alpha$, i.e., $x = \alpha$. ///

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks, Nik! Now I briefly looked through some definitions and rewrote "the ranks of elements of $x$ are cofinal in $\alpha$" in more familiar to me $\varepsilon-\delta$ manner: "for each ordinal $\beta < \alpha$ there exists $y \in x$ such that $rank(y)>\beta$". But $y$ is an ordinal by induction hypothesis, so $rank(y)=y>\beta\Rightarrow \beta\in y \in x\Rightarrow \beta \in x$ by transitivity. Therefore $x$ is is a set of all the ordinals $\beta < \alpha$ thus $x=\alpha$ by the property of (von Neumann) ordinals. Did I get it correctly? $\endgroup$
    – Alexander Kuleshov
    Commented Sep 18, 2019 at 21:14
  • $\begingroup$ Almost --- for each $\beta < \alpha$ there exists $y \in x$ such that ${\rm rank}(y) \geq \beta$. (This covers the case where $\alpha$ is a successor too, though it wouldn't be any trouble to just consider that case separately.) $\endgroup$
    – Nik Weaver
    Commented Sep 18, 2019 at 21:27
  • $\begingroup$ Ahaha that's where my $\varepsilon-\delta$ habit failed, I always forget that there is no $m$ such that $n<m<n+1$... Thanks) In fact doesn't matter, still $\beta \in x$ ! $\endgroup$
    – Alexander Kuleshov
    Commented Sep 18, 2019 at 21:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .