Understanding order and countability

Question

I am confused with how to defining the order of countable set. Let me express my thoughts by some examples:

$\Bbb{N}$ has a 'natural' order, namely $1\lt2\lt3...$ For any countable set, we can define an order: $\phi(1)\lt\phi(2)\lt...$, where $\phi$ is a injection from $\Bbb{N}$ to the set.

But when I consider $\Bbb{N}\times\Bbb{N}$, which is countable, we have a bijection $f:\Bbb{N}\times\Bbb{N}\to\Bbb{N}$ s.t. $f((a,b))\lt f((c,d))\iff (a=c\,\,and\,\,b\lt d)\,or\, a\lt c$ by suitable permutation. (Am I correct until this step?). Then, what is $f((2,1))$ now?

Whatever $f((2,1))$ is, this will imply that there are only finitely many point in $\Bbb{N}\times\Bbb{N}$ in front of $(2,1)$, which contradict our definition of order of $\Bbb{N}\times\Bbb{N}$ defined above.

Please tell me if I have made any mistake. If the argument above has no problem, then...well, I don't understand what is happened.

Answer 1

The bijection $f : \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ need not be order preserving, so your statement that there will be only finitely many points in $\mathbb{N} \times \mathbb{N}$ in front of $(2,1)$ is false.

Perhaps a more concrete example will help. Consider the following bijection $f : \mathbb{N} \to \mathbb{N}$: $$f(n) = \begin{cases} 17 & \quad\text{if $n=1$} \\ 1 & \quad\text{if $n=17$} \\ n & \quad\text{otherwise} \end{cases} $$ One might want to say: since $f(17) = 1$ has no elements in front of it, then $17$ has no elements in front of it. But this is false if you insist on using the "natural" order in both the domain and range of $f$. This reflects the fact that $f$ does not preserve natural order: it is not true that $m<n$ if and only if $f(m)<f(n)$.

Similarly, in your example, using the natural order on the range $\mathbb{N}$ and the "dictionary order" on the domain $\mathbb{N} \times \mathbb{N}$ (which is the name of the order you describe), it does not follow that $f(m,n) < f(p,q)$ if and only if $(m,n) < (p,q)$. In other words, your function $f$ does not preserve order.

Added to address the comment: In fact, there does not exist any order preserving bijection between $\mathbb{N} \times \mathbb{N}$ with the dictionary ordering and $\mathbb{N}$ with its natural ordering. The latter ordering has the property that for every $n \in \mathbb{N}$ the number of elements less than $n$ is finite. But the dictionary ordering on $\mathbb{N} \times \mathbb{N}$ does not have that property, as observed in the question itself. Clearly that property must be preserved by any order preserving bijection.

Answer 2

If you have a bijection $f: \mathbb N \times \mathbb N \to \mathbb N$, then the function $\phi: \mathbb N \to \mathbb N \times \mathbb N$ does indeed define an order on $\mathbb N \times \mathbb N$: $$ \phi(1) < \phi(2) < \phi(3) < \phi(4) < \cdots . $$

What you have found by contradiction is that this order cannot be an order such that $f((a,b))< f((c,d))$ if and only if ($a=c$ and $b < d$) or $a<c$.

But since a bijection exists, clearly there must be some order that is preserved under a bijection between $\mathbb N \times \mathbb N$ and $\mathbb N$. One such order is $$ f((a,b))< f((c,d)) \text{ if and only if } (a+b=c+d \text{ and } a < c)\text{ or }a+b<c+d. $$ The bijection that preserves this order is \begin{align} (1,1) &\to 1 \\ (1,2) &\to 2 \\ (2,1) &\to 3 \\ (1,3) &\to 4 \\ (2,2) &\to 5 \\ (3,1) &\to 6 \\ (1,4) &\to 7 \\ &\vdots \end{align}