2
$\begingroup$

I would like to prove the set of all countable ordinals is actually a set.

There are some related questions, but I think none of them answer exactly what I want. There is one in particular here which tries to show the result (probably it proves it) but I don't understand.

Following the above answer, I pick a set $A$ such that $|A|=\aleph_0$. The family of all well-orders of $A$ is a subclass of $A\times A$ and thus is a set. Call it $\mathscr R$. For each $R\in\mathscr R$ the well-ordered structure $(A,R)$ is order-ismorphic to some ordinal $\alpha$ (which must be countable). This proves all ordinals which are order-isomorphic to some structure $(A,R)$ is a countable set.

However, I'm not sure such a set ($\mathcal A$) is $\{\alpha\in\mathcal O : |\alpha|\leq \aleph_0\}$ whole, but only a subset. In fact, I'm very sure about that, because $\mathscr R$ is countable and: hence $\mathcal A$ and also $\bigcup\mathcal A$ will be, while the last should be $\omega_1$.

What I'm following this pourpose? Because I would like to define

$$ \omega_1 = \bigcup \{\alpha\in\mathcal O : |\alpha|\leq \aleph_0\}, $$ whithout using $\aleph_1$. It will be an ordinal because the union of a set of ordinal it is. However, it may be $\mathcal O$, the class of all ordinal numbers. The unique way to avoid this is proving $\{\alpha\in\mathcal O : |\alpha|\leq \aleph_0\}$ is a set.

Correction: As @NoahSchweber says, each $R\in \mathscr R$ is countable but $\mathscr R$ itself is a subset of $P(A\times A)$, so it may be uncountable. However, I'm not worried about countability. Showing the set is uncountable is quite easy, since if not it should be an element of itself.

I want to prove $\{\alpha\in\mathcal O : |\alpha|\leq \aleph_0\}$ is a set.

$\endgroup$
5
  • 1
    $\begingroup$ $\mathcal{R}$ is definitely not countable. Why do you think it is? $\endgroup$ Apr 24, 2018 at 12:29
  • $\begingroup$ Also I'm a bit confused re: $\aleph_1$: this argument is how you show that $\aleph_1$ exists in the first place ... $\endgroup$ Apr 24, 2018 at 12:43
  • $\begingroup$ @NoahSchweber: Each $R\in\mathscr R$ is a subset of $A\times A$, so each $R$ is a countable set. But you are perfectly correct. The set of all of them is a subset of $P(A\times A)$. I was wrong thanks. $\endgroup$
    – Dog_69
    Apr 24, 2018 at 13:22
  • $\begingroup$ I have edited my question. $\endgroup$
    – Dog_69
    Apr 24, 2018 at 13:29
  • $\begingroup$ I've added a line to my answer showing how, from the fact that every countable ordinal is represented in $\mathcal{R}$, the fact that the class of ordinals is a set follows. $\endgroup$ Apr 24, 2018 at 13:42

2 Answers 2

3
$\begingroup$

Your claim that $\mathcal{R}$ - the set of well-orderings with domain a subset$^*$ of some fixed countably infinite set $A$ - is countable is incorrect. Indeed, we can see directly that every countable ordinal is isomorphic to some element of $\mathcal{R}$:

  • Fix $\alpha$ a countable ordinal.

  • Since $\alpha$ is countable, we get an injection $f:\alpha\rightarrow A$. Let $I$ be the image of $f$.

  • Define a relation $\trianglelefteq$ on $I$ as follows: $$x\trianglelefteq y\iff f^{-1}(x)<f^{-1}(y)$$ (where "$<$" is the usual ordering on $\alpha$).

  • $\mathcal{L}=(I,\trianglelefteq)$ is a well-ordering with domain $\subseteq A$, so $\mathcal{L}\in\mathcal{R}$; and clearly $\mathcal{L}$ and $\alpha$ are isomorphic (the original map $f$ is an isomorphism).

From here we immediately get that the set of countable ordinals exists (or if you prefer, that the class of countable ordinals is a set), by replacement:

  • It's a standard theorem (using replacement) that every well-ordering is isomorphic to an ordinal.

  • OK, now apply replacement to $\mathcal{R}$ to get the set of ordinals isomorphic to some element of $\mathcal{R}$; this is exactly the set of countable ordinals.


$^*$Why "a subset?" Well, this is because otherwise we miss the finite ordinals (clearly no finite ordinal is isomorphic to a well-ordering with infinite domain!). It's not a huge issue, but let's phrase things this way.

$\endgroup$
1
  • $\begingroup$ I have just realized your answer is the proof of Hartog number for the case $X$ is a countable set. And I tried to understand that theorem some weeks ago. I knew the answer indeed. Sorry for the inconvenience caused. $\endgroup$
    – Dog_69
    Apr 24, 2018 at 18:05
1
$\begingroup$

A binary relation on $S$ is a subset of $S\times S.$ A well-order $<$ on $S$ is a certain kind of binary relation on $S$, although we prefer to write $a<b$ rather than $(a,b)\in <.$

Let $A$ be countably infinite. Define $B$ by: $b\in B$ iff there exists $S\subset A$ such that $b$ is a well-order on $S$. We have:

(1). If $b\in B$ there exists a $unique$ countable ordinal $x$ which is order-isomorphic to $b.$

(2). If $x$ is a countable ordinal there exists $b\in B$ which is order-isomorphic to $x.$

By (1), Separation and Comprehension imply there exists the set $C$ of all countable ordinals that are order-isomorphic to members of $B$. By (2), every countable ordinal belongs to $C.$ So $C$ is the set of countable ordinals.

$\endgroup$
2
  • $\begingroup$ The question is about the set of countable ordinals, not finite ordinals. $\endgroup$ Apr 25, 2018 at 0:56
  • $\begingroup$ @NoahSchweber OOPS. I completely re-wrote it. $\endgroup$ Apr 25, 2018 at 2:00

You must log in to answer this question.

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