Suppose that we have a countable set $\mathcal C,$ and there is a total order $R$ on this set. By an analogy with the definition of the natural numbers, I guess that, if $R$ satisfy the following conditions, then $(\mathcal C,R)$ is isomorphic to $\mathbb N.$

$\bf 1)$ $\mathcal C$ has a minimum element with respect to $R$;

$\bf 2)$ $\forall\ x\in \mathcal C,$ there is a minimum element of the set $\left\{y\in\mathcal C|\ x<_R y\right\}$ with respect to $R.$

Question: Is my guess correct? If not, what improvement should me made to the requirements of $R$ ? Any hints are welcomed.


You're asking, practically, that $\cal C$ is a well-ordered set and without a maximum. There are uncountably many different ways to well-order a countable set, and uncountably many of them do not have a maximum either (and in a technical sense "almost all of them").

For example, consider the following ordering on $\Bbb Z$:

$$n\prec m\iff\begin{cases}0\leq n<m &\text{ or }\\m<n<0 & \text{ or }\\m<0\leq n\end{cases}$$

In other word, take all the negative integers, flip their order, and stack them on top of the natural numbers. So you effectively have two copies of $\Bbb N$ one after the other. It's easy to check that this satisfies the condition you impose.

However, you can find a condition that ensures a linear ordering is isomorphic to $\Bbb N$:

  1. There is no maximal element.
  2. Every proper initial segment is finite.

And I will let you prove this yourself, as a fun little exercise in order theory.

  • $\begingroup$ I see what I've missed now. Thanks for your answer :). $\endgroup$ – painday Apr 12 '18 at 16:13

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.