1
$\begingroup$

I can't understand a simple thing again, though found the similar questions here. Given the set $S$ of all countably infinite ordinals, how can we find its order type, or at least its cardinality? Do we need the axiom of choice or continuum hypothesis here? I've just managed to show $\omega_0\leq Ord(S)\leq\omega_1$.

P.S. I'm trying not to use the Neumann's approach (where ordinals are sets with the certain properties), considering the separate class of objects. It's also given that $\omega_1$ is the set of all countable (not necessarily infinite) ordinals.

$\endgroup$
  • 2
    $\begingroup$ The set of all countably infinite ordinals is simply $\omega_1$ itself, and since $\omega_1$ is a cardinal, $|\omega_1| = \omega_1$. $\endgroup$ – Clement Yung Dec 31 '19 at 1:39
  • $\begingroup$ @ClementYung does it follow from the definition, or it can be proved somehow? I've spent about 2 hours for it, since my definition states $\omega_1$ is a type of just all countable (not only infinite) ordinals. $\endgroup$ – Elmar Guseinov Dec 31 '19 at 1:42
  • 1
    $\begingroup$ By definition, we know that $\omega_1 = \sup\{\alpha : \alpha < \omega_1\}$ (where here $``<"$ represents the well order in the set of ordinals by $\subsetneq$). Clearly $\omega_1 \subseteq S$, and you can try to prove that $S \subseteq \omega_1$. $\endgroup$ – Clement Yung Dec 31 '19 at 1:44
  • 3
    $\begingroup$ @ClementYung - Given that $S$ contains no finite ordinals, but $\omega_1$ does, how is the latter a subset of the former? $\endgroup$ – Malice Vidrine Dec 31 '19 at 4:17
  • 1
    $\begingroup$ @MaliceVidrine oh you're right, I missed that. We should instead prove by contradiction, where if $S$ is countable, then $\omega_1 = S \cup \omega_0$ is countable, a contradiction. $\endgroup$ – Clement Yung Dec 31 '19 at 4:22
2
$\begingroup$

Here is an easy argument as to why the answer is $\omega_1$.

$\sf ZF$ (and in fact $\sf Z$) proves that given any two well-ordered sets, one is isomorphic to a unique initial segment of the other. That is, any two well-ordered sets are comparable.

By definition, $\omega_1$ is the smallest order type of an uncountable well-order. So if we prove that $\omega_1\setminus\omega$ is uncountable, then $\omega_1$ is isomorphic to an initial segment of it, but since it is also a subset of $\omega_1$, this initial segment cannot be a proper initial segment, as that would imply $\omega_1$ is isomorphic to a proper initial segment of itself which contradicts the uniqueness part of the above theorem.

But now it's easy. If $\omega_1\setminus\omega$ is countable, then $\omega_1$ is the union of two countable sets, which is indeed countable. That's not true, so the order type is $\omega_1$.


Finally, if you want an explicit argument, which you probably do, note that just like you can add an element to the bottom of $\omega$ and not change the order type, you can also add an $\omega$ sequence to the bottom of the ordinal $\omega\cdot\omega$ without changing the order type. Apply that sort of bijection on the initial segment that is $\omega\cdot\omega$ and the identity elsewhere, and you get your order isomorphism.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot! The idea with two countable cardinalities was really useful. $\endgroup$ – Elmar Guseinov Dec 31 '19 at 16:14
  • $\begingroup$ You're welcome! $\endgroup$ – Asaf Karagila Dec 31 '19 at 16:15
3
$\begingroup$

We don't need the AC or CH.

We can show that the collection of all well-orderings of $\mathbb N$ is a set (this makes essential use of power set). Each of these well-ordered sets corresponds to an ordinal - its order type (this makes essential use of replacement), and so (by replacement again) there is a set of all countable ordinals. This is a well-ordered set under the usual ordering $\in$, so it has an order type. We call this ordinal $\omega_1$ by definition.

$\omega_1$ is not countable since it is an ordinal, and by its definition any countable ordinal is strictly less.

So that's a complete answer to the question, and no choice was used. Where choice might get involved is when we want to say $\omega_1$ is the smallest uncountable cardinality. It's clearly the smallest uncountable ordinal, and so it can be embedded into any uncountable well-orderable set, so it is of size less than or equal to it. But we can't say every set is well-orderable without AC, and for instance, it is consistent with ZF that $\omega_1$ does not have an injection into the reals. (However it is provable in ZF that there is a surjection of the reals onto $\omega_1$.) It's also consistent that there are infinite sets that $\omega$ does not even inject into, so no AC also wrecks $\omega$'s status as the smallest infinite cardinality.

| cite | improve this answer | |
$\endgroup$

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.