So, to explain the title, I'm referring to the necessity of the axiom of choice in the existence of a well ordering on reals, or any uncountable set.

Now, while tweaking some sets, I came across this :

We start with the natural numbers, $N$. We take the power set of the naturals, $P(N)$.

Then we remove all the finite subsets of $N$ from $P(N)$. Let us call this new set $S$. This set is the set of all infinite subsets of $N$.

It is easy to show that $S$ has uncountable cardinality, same as that of real numbers. This is because the removal of finite subsets only removes a countable number of elements. (Haven't posted this deduction, for it is very easy, but I may post it if it is not so evident)

Now, we seek to find an ordering on the set $S$. Every set in this set is an infinite subset of natural numbers, so each of these sets are well ordered by the natural ordering of $N$.

Taking any two sets in $S$, say $A$, and $B$, we seek to order them by checking their elements lexicographically. We compare the first two elements in $A$, and $B$. Let them be $a_1$, and $b_1$ respectively. If $a_1 = b_1$, then we move on to the second elements in the sets, $a_2$, and $b_2$, and so on. If, at any point, $a_n < b_n$, then $A < B$, or if $b_n < a_n$, then $B < A$.

This order seems to be a well ordering of the uncountable infinity of reals. I don't seem to have invoked the axiom of choice anywhere in the construction of this set $S$.

So, why isn't this a well ordering on the uncountable of reals?


1 Answer 1


For each natural number $n$, let $A_n$ be the set $\mathbb{N}$ with the number $n$ removed from it. Then consider the collection $A = \{A_n \colon n \in \mathbb{N}\}$.

Then the set $A$ has no smallest element in your ordering, showing that it is not a well-ordering after all.

Proof: Note that for all $n$ we have $A_{n+1} < A_n$ since the first $n - 1$ elements of both sets are equal, and the $n$'th element of $A_{n+1}$ is $n$, which is smaller than the $n$'th element of $A_n$, which is $n + 1$.

So then $A_1>A_2>A_3> \dots $

And we find this is an ordering but the important thing here is that an ordering is called a WELL ordering if it is not only an ordering, but also has the additional property that every set has a smallest element.


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.