Why isn't this a well ordering of $\{A\subseteq\mathbb N\mid A\text{ is infinite}\}$?

Question

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?

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.