9
$\begingroup$

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?

$\endgroup$
8
  • 3
    $\begingroup$ 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). $\endgroup$
    – pancini
    Feb 13, 2021 at 20:58
  • $\begingroup$ 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. $\endgroup$
    – Mark
    Feb 13, 2021 at 20:58
  • 1
    $\begingroup$ Even without the axiom of choice, any ordinal is well ordered. $\endgroup$
    – Mark
    Feb 13, 2021 at 21:00
  • 3
    $\begingroup$ 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. $\endgroup$ Feb 13, 2021 at 21:04
  • 3
    $\begingroup$ @Mark: For Hartogs' theorem? As I said, no you don't. For the existence of uncountable ordinals? No, since it follows from Hartogs. $\endgroup$ Feb 13, 2021 at 21:08

3 Answers 3

6
$\begingroup$

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).

$\endgroup$
1
  • 1
    $\begingroup$ This seems to be a more detailed answer. The fact that we can count forever doesn't mean it is countable. $\endgroup$
    – Ziqi Fan
    Feb 13, 2021 at 21:15
5
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ Although I have not read ordinals, thanks for your answer. It makes me aware of what ordinals are about. $\endgroup$
    – Ziqi Fan
    Feb 13, 2021 at 21:09
  • $\begingroup$ @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$. $\endgroup$
    – J.G.
    Feb 13, 2021 at 21:15
  • 1
    $\begingroup$ @ZiqiFan Well-ordering of all sets also implies AC. $\endgroup$
    – J.G.
    Feb 13, 2021 at 21:15
3
$\begingroup$

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.

$\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.