Can I always order a countable set of numbers?

Question

Suppose I have a countable subset of the real numbers $A$. Then since it is countable there is a function $f: \mathbb N \to A$ which is bijective. This function is of course a sequence, so we can write every element $x$ of $A$ as $x_i = f(i)$. So $A= \{ x_i \mid i \in \mathbb N \}$. Of course no two $x_i$ and $x_j$ are the same.

I can now come and reorder the $x_i$'s (instead of naming the $x \in A$ as $x_i$ I can name it $x_j$) such that they are decreasing $$x_1 >x_2>\cdots. $$

(Trivial??) Question: I CAN do that right? It seems right, since any $x_i$ and $x_j$ are different, then one is bigger than the other, thus I can do this comparison with all of them and order them.

If that is the case then take as $A= \Bbb Q \cap (0,1)$ for example. What we said above is that since $A$ is countable I can write $A= \Bbb Q \cap (0,1)=\{ x_i \mid i \in \mathbb N \}$ with $x_1 >x_2>\cdots$.

But that is absurd, there is no biggest rational in $(0,1)$. It's late, what am I missing?

EDIT. Also suppose a case where there IS a biggest number such as $A=\Bbb Q \cap (0,0.9]$ where the biggest rational is $0.9$. Then we can do $ 0.9=x_1 <x_2 <x_3<\cdots$. We have no idea what $x_2$ is, but there is a rational closest to $0.9$ than all others??

Answer 1

" Question: I CAN do that right?"

Actually, no. The "usual" order (where $a < b$ means $b-a$ is positive) is not what is called a "well-ordering", i.e. an order in which there is always a "least" element of all subsets.

You have proven that "$<$" is not a well-ordering as $\mathbb Q \cap (0,1)$ does not have a least or greatest element. (Neither does $\mathbb Z$ or $\mathbb Q$).

!!!!BUT!!!!!, a "well-ordering" of a countable set will always exist! It just won't be "$>$".

You have actually proven that. Let $x \prec y$ mean that $f^{-1}(x) < f^{-1}(y)$. Then "$\prec$" is a well ordering and the "least" element is $x_1$.

"$\prec$" has all the properties of an "order". (Exactly one of $a \prec b$ or $b \prec a$ or $a = b$ are true; $a \prec b$ and $b \prec c \implies a \prec c$). But it doesn't mean what we think of as "bigger" and "smaller". It means nothing more or less than "comes before in a list". Which is just as valid a basis for order and "being smaller" is.

Post-script (and maybe more to the point):

"It seems right, since any xi and xj are different, then one is bigger than the other, thus I can do this comparison with all of them and order them."

Ah!... good question. The problem with this is that you never finish. You can always say "I've sorted 5 billion of them and so far $x_{1,672,453,928}$ is least and $x_{17}$ is the greatest" but then you will also have to admit "but I can not be certain that they will remain the largest and smallest... And I'll never be certain."

Try it with $\mathbb Z$". We can list all the integers in order as $0, 1,-1,2,-2, 3,-3....$.

So "$1$ is bigger than $0$ so keep $1$. $1$ is bigger than $-1$ so keep $1$. $2$ is bigger than $1$ so replace $1$ with $2$. $2$ is bigger than $-2$ so keep $2$. $3$ is biggr than $2$ so replace $2$ with $3$. $3$ is bigger tan $-3$ so..."

You see how that will never actually end and we will never actually get a largest or a smallest element.

Post-Post-Script: Notice a well ordering says all subsets will have a least element. It doesn't actually say it will have a largest element. And "comes earlier in a list" makes sets that do always have a first element but do not always have a last element.

It should be intuitive though that any axiom of definition we make for a well-ordering always having a least element could arbitrarily be make for a "perverse" ordering which always have a greatest element but not nescessarily a least. If "$\prec$" is a well-ordering, then defining "$\prec_{ident}$" as $a \prec_{ident} b \iff b \prec a$ will, of course, be a perverse ordering.

("perverse ordering" and "$\prec_{ident}$ are terms I made up and not valid mathematical terminology. I hope that was clear.)

(That's probably a lot more than you asked for.)

Answer 2

$X = \mathbb{Q} \cap (0, 1)$ is a countable set. An explicit enumeration of this set is $$x_1 = 1/2, \quad x_2 = 1/3, \quad x_3 = 2/3, \quad x_4 = 1/4, \quad x_5 = 3/4, \quad \ldots$$ Therefore, we can construct a total order $<_X$ on the set $X$ as follows: given two numbers $x_i$ and $x_j$ in $X$, we write $x_i <_X x_j$ whenever $i < j$.

This does not correspond to the usual order $<$ on the real numbers, under which there is no smallest element in $X$. On the other hand $x_1 = 1/2$ is the smallest element in the order $<_X$.

Addendum: I realize after writing this that you asked for an order that has a largest element, but the argument is the same, defining instead $<_X$ by $x_i <_X x_j$ whenever $i > j$.

Answer 3

You always can do it. You are making a mistake when says which there is not biggest rational in $(0,1)$. What is the mistake? There ist not biggest rational in (0,1) using the standard order relation. This order that you are defining, is not the standard. See by well ordenation, every set can be well-ordered.

Answer 4

NO, you cannot always compare among an infinite set of numbers and pick out the biggest element, then the second biggest element, and so on. That's always allowed when you have a finite set, but it does not generalize to infinite sets (note that I am talking about the standard ordering, you can see other answers about nonstandard ordering).

For any countably infinite set, from the definition you can always list their elements as a sequence $ a_1, a_2, a_3, \dots $, but unless the map from $ \mathbb{N} $ is given, we don't know explicitly what the elements are or what the ordering is like.

Answer 5

Yes. For any countable set $S$, there exists an ordering $\prec$ on $S$ for which the ordered set $(S, \prec)$ has a largest element.

---

If that is the case then take as $A= \Bbb Q \cap (0,1)$ for example. What we said above is that since $A$ is countable I can write $A= \Bbb Q \cap (0,1)=\{ x_i | i \in N \}$ with $x_1 >x_2>... $.

But that is absurd, there is no biggest rational in $(0,1)$. It's late, what am I missing?

It's pretty clear that $A$ does have a biggest rational; it's $x_1$.

What you're mixing up is that you are using the same letter $A$ for three different things:

• The set of rational numbers in $(0,1)$
• The ordered set of rational numbers in $(0,1)$ with the usual ordering
• The ordered set of rational numbers in $(0,1)$ with the new ordering you defined

You might ask whether or not each of these has a largest element. For the third, the answer yes. For the second, the answer is no. For the first, the question doesn't even make sense.

But since you describe all three the same way, you are having trouble acknowledging the difference.

---

In practice, we usually only ever consider the usual ordering, so there is no confusion by conflating the set of rational numbers with the ordered set of rational numbers with their usual ordering.

However, as soon as you entertain the idea of a different ordering, this detail becomes critically important, so you need to pay attention to it!

Answer 6

The answer is "no" and here is why. If you could always do that ordering that would mean that any countable set has a largest element. This is clearly not the case; take for example $$ A=\{x_i={i\over 1+i}, i\in \mathbb{N}\} $$ which clearly does not have a largest element.

(Of course there are cases where this is possible, such as $B=\{x_i={1\over 1+i}, i\in \mathbb{N}\}$ where $x_1=1$).

Maybe what you are missing is that the number of permutations of a finite set is itself finite but the permutations of an infinite set are infinite as well.

Answer 7

The right way of dealing with absurd is always to take simpler examples and test it.

In this case, there are two natural and simple examples:

1. $\Bbb Z$, which is easily countable. But has no minimal element.
2. $\Bbb N\cup\{\infty\}$ where $n<\infty$ for all $n\in\Bbb N$. We added one element to the set of the natural numbers, so it is still a countable set, but clearly this order has a maximum element, whereas $\Bbb N$ does not.

We can go even further.

3. Consider the set $\{0,1\}$ ordered by $<$ and the set $\{\{0\},\{1\}\}$ ordered by $\subseteq$. Clearly these two sets are of the same cardinality, but only one of them is linearly ordered.

The key point in all of these examples, as well as the case you raise, is that cardinality is witnessed by a function between the sets, not between the structured sets. There is no reason to expect it will preserve order. And if you so insistent on order, why not require it to preserve addition, or multiplication, or both?

Clearly $f\colon\Bbb{Z\to Z}$ defined by $f(x)=x+1$ is an order preserving function, but $f(0+0)=f(0)=1\neq 2=f(0)+f(0)$. Why is this not an issue? Again, because we don't require an order preserving function to preserve the arithmetic structure on $\Bbb Z$.

---

To sum up, cardinality is witnessed by a bijection which has no reason to preserve any additional structure such as pre-existing order, addition, or anything else.

Answer 8

[...] also suppose a case where there IS a biggest number such as $A=\Bbb Q \cap (0,0.9]$ where the biggest rational is $0.9$. Then we can do $0.9=x_1 >x_2 >x_3>\cdots$. We have no idea what $x_2$ is, but there is a rational closest to $0.9$ than all others??

[I have edited the formulas in the quote slightly, mainly to change $<$ to $>,$ which I think is what you actually meant to write.]

The answer to this last part of the question also is no, there is no such number $x_2.$ The existence of such a number would imply there is also a number $x_{1.5} = \frac12(x_1 + x_2)$ which is in the set $A$ but is greater than $x_2,$ contradicting the assertion that $x_2$ is the next number. So not only can we not name such a number, it cannot even exist.