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.

  • 1
    $\begingroup$ $\mathcal{R}$ is definitely not countable. Why do you think it is? $\endgroup$ – Noah Schweber Apr 24 '18 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$ – Noah Schweber Apr 24 '18 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 '18 at 13:22
  • $\begingroup$ I have edited my question. $\endgroup$ – Dog_69 Apr 24 '18 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$ – Noah Schweber Apr 24 '18 at 13:42

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.

  • $\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 '18 at 18:05

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.

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

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.