# Is a well-ordered set always countable?

Suppose that $$A$$ is a well-ordered set. We can find $$a_{0} = \min{A}$$. Then, if $$A \setminus \left\{a_{0}\right\} \neq \emptyset$$, we can find $$a_{1} = \min{\left(A \setminus \left\{a_{0}\right\}\right)}$$, etc. Intuitively, this seems to be a counting process. Then my hypothesis is, every well-ordered set is countable. Is this a valid guess? In my understanding, if it is valid, then for finite well-ordered sets, we can use mathematical induction to prove it. Then what about infinite cases?

• It's not a bad guess, but it turns out that every set can be well-ordered (this fact is equivalent to the axiom of choice). Feb 13, 2021 at 20:58
• No. Actually, given the axiom of choice any nonempty set can be well ordered. And even without the axiom of choice there are uncountable sets.
– Mark
Feb 13, 2021 at 20:58
• Even without the axiom of choice, any ordinal is well ordered.
– Mark
Feb 13, 2021 at 21:00
• Hartogs' theorem doesn't require the axiom of choice, and proves that for every set $A$ there is a well-ordered set $\alpha$ (indeed an ordinal) for which there is no injection from $\alpha$ to $A$. If you take $A$ to be a countable set then the resulting $\alpha$ is necessarily uncountable. Feb 13, 2021 at 21:04
• @Mark: For Hartogs' theorem? As I said, no you don't. For the existence of uncountable ordinals? No, since it follows from Hartogs. Feb 13, 2021 at 21:08

To clarify exactly what's going on, your argument shows there is a countably infinite subset of any infinite well-ordered ordinal. The reason it doesn't show any well-ordered set is countable is that there's no reason your process should exhaust the set A. If we consider the set $$\mathbb{N}\cup\{\infty\}$$, where we add a point larger than any natural, we can check this is still a well-ordered set. But the process you describe will never "count" the point at infinity. Of course this set is still countable, but the idea is instead of adding 1 point we can add uncountably many (a priori it's not clear how to order these points, this is just supposed to show why we can get uncountable ordinals).

• This seems to be a more detailed answer. The fact that we can count forever doesn't mean it is countable. Feb 13, 2021 at 21:15

Every ordinal is well-ordered by $$\in$$. Ordinals are arbitrarily large. All the axiom of choice adds is that all sets biject with an ordinal, thereby being well-orderable. Even proper classes can be well-orderable; the class of ordinals is well-ordered by $$\in$$.

• Although I have not read ordinals, thanks for your answer. It makes me aware of what ordinals are about. Feb 13, 2021 at 21:09
• @ZiqiFan This would make for good reading. The axiom of choice biject sets with ordinals because if $f$ is a choice function on $\mathcal{P}(X)\setminus\emptyset$ and $\iota(\alpha)$ is defined for ordinals $\alpha$ as $f(X\setminus\{\iota(\beta)|\beta\in\alpha\})$ then, since $\iota$'s domain can't be the class of all ordinals because it's not a set, there is a least $\alpha$ for which $\iota(\alpha)$ is undefined, i.e. $\{\iota(\beta)|\beta\in\alpha\})=X$.
– J.G.
Feb 13, 2021 at 21:15
• @ZiqiFan Well-ordering of all sets also implies AC.
– J.G.
Feb 13, 2021 at 21:15

I'd like to point out why your intuitive argument is wrong. Your sequence starts with the smallest element of $$A$$, then moves to the next smallest element of $$A$$ - the successor of $$a_0$$. By induction (as per the Peano axioms), this process will eventually reach every natural number if we apply it to $$\mathbb N$$. By the way, it's typical to write $$\omega = \mathbb N$$ when referring to it as an ordinal. The thing is, your process being exhaustive would require that every element of $$A$$ other than the smallest one is a successor of some other element. I'll give you an example of a well ordered set where this does not hold.

As I said, we have $$\omega = \mathbb N$$. Let's define a new set, called $$\omega + 1$$, as $$\omega \cup \{\infty\}$$, where $$\infty$$ is just some symbol not in $$\omega$$. We'll keep the ordering on $$\omega$$ and assert that $$\infty$$ is strictly bigger than every element of $$\omega$$. This makes $$\omega + 1$$ into a well ordered set. Essentially, if a nonempty subset contains $$\infty$$ then its minimum is either $$\infty$$ itself or removing $$\infty$$ does not change the minimum. Now, if you tried to apply this process to $$\omega + 1$$, you would get $$a_0 = 0$$, $$a_1 = 1$$,... , $$a_n = n$$. However, you would never reach $$\infty$$ as there is no $$n \in \omega$$ whose successor is $$\infty$$.

I'd like to point you to the notion of transfinite induction, however. This is a method that allows you to make inductive arguments on any well ordered set, as you have tried to do. The difference is that you have to account for these $$\infty$$ esque elements which are not a successor of anything (called limit ordinals). If you can prove a property $$P$$ holds for all limit ordinals in $$A$$ and that $$P(\alpha) \implies P(succ(\alpha))$$ then $$P$$ holds for all $$\alpha$$ in $$A$$.

I'd also like to point out that the more standard notation is $$\omega + 1 = \omega \cup \{\omega\}$$. This definition of the successor ordinal allows for a very clean theory. Here, we have that $$\omega \in \omega + 1$$ is a limit ordinal, so doing induction on $$\omega + 1$$ requires treating this case specially.