How does well-ordering theorem apply to real numbers if real numbers are not countable?

1k Views Asked by At

From what I understand, the well-ordering theorem assumes ANY set can be made well-ordered depending on how you define the ordering.

For example, $\mathbb{Z}$ is not well-ordered according to the conventional ordering of (<). But, if we define a new ordering, say ($\prec$), s.t. for any $a,b \in \mathbb{Z}$, we have $a \prec b$ whenever $|a| \le |b|$, then we can order the set of integers as $\{0, 1 ,-1, 2,-2,3, -3,...\}$ and thus make the set well-ordered. Under this new ordering the least element is $0$, and every nonempty subset will also have a least element.

If the well-ordering axiom is true, then there exists an ordering s.t. the $\mathbb{R}$ are also well-ordered, but how is this possible given the $\mathbb{R}$ is uncountable?

In other words, if there was such an ordering, say ordering $(@)$, then that ordering would effectively be a function makes the reals listable, would it not? Under $@$, there would be some number, say $n_1$, that would be the least element of $\mathbb{R}$... and another number, $n_2$, that would be the least element of $\mathbb{R}-\{n_1\}$... and another number, $n_3$, that would be the least element of $\mathbb{R}-\{n_1,n_2\}$, and so on and so forth... but we know the reals cannot be placed into a one-to-one correspondence with $\mathbb{N}$ as $n_1,n_2,n_3$,... This seems like a contradiction to me.

Can anyone resolve this for me without getting too steeped in jargon and notation? Thanks.

2

There are 2 best solutions below

4
On

First, your list of elements of $\mathbb Z$ can be regarded as well-ordered, but not using the relation you have stated, since that makes both $n\prec -n$ and $-n\prec n$.

Secondly a well-ordered set corresponds to an ordinal number. A countable set is one which has a bijection to the ordinal $\omega$ (which can be regarded as the ordered set $\{0,1,2,3,4, \dots\}$).

To illustrate the difference, consider the integers with the ordering $0, 1, 2, 3 \dots -1, -2, -3, \dots$. This has order type $2\omega$ and is a well-ordering (you should check this). Using your strategy for the reals you would list the positive integers, but would never get to the negative integers.

Countably infinite sets can have many different well-orderings of different order types (uncountably many in fact). But they all have a well-ordering of type $\omega$.

Your strategy for the reals fails to show hey are countable because it doesn't list every real number. Cantor's diagonal argument shows that no strategy can work.

Perhaps others will inject a little more technical precision here. The fact that all sets can be well-ordered does not follow from the "other" axioms of set theory. It is sometimes posed as an axiom itself, and is sometimes regarded as a consequence of the Axiom of Choice.

4
On

It is indeed possible to generate an infinite list-more precisely, a list of order type $\omega$-by recursively choosing the least element of any well ordered set. This list will usually not contain the whole set, and indeed cannot when the set is uncountable. You haven't given any justification for why you intuit that this process should exhaust the set, so it's difficult to say more.