My set theory notes define a similarity (or order isomorphism) between two $\textbf{well-ordered}$ sets $(X,\leq_{1})$ and $(Y,\leq_{2})$ as a bijection $f:X\longrightarrow Y$ such that $x_1 \leq_1 x_2 \iff f(x_1) \leq_2 f(x_2)$. Now I do not have any explicit examples of these and I am struggling to think of any, as the definition specifies well-ordered sets as opposed to posets.

I tried showing that the function $f:\mathbb{Z}\longrightarrow \mathbb{N}, f(z)=2z (z>0), f(z)=1-2z (z\leq 0)$ was one, and it turns out its not an order isomorphism, but I forgot that under that usual ordering of $\mathbb{Z}$, it is not a well-ordering.

So, can anyone give a simple example of what I'm looking for?


  • 2
    $\begingroup$ Given any two well ordered sets $X$ and $Y$ either they are isomorphic, or one embeds into the other as an initial segment, so there are plenty of examples, just pick your favourite distinct well ordered sets! $\endgroup$ Apr 20 '20 at 14:20

You may be having a hard time coming up with suitable examples of well-ordered sets. Here’s a simple concrete example to get you started.

Let $X=\Bbb N\times\{0,1\}$, and let $\preceq$ be the lexicographic order on $X$: $\langle m,i\rangle\preceq\langle n,j\rangle$ iff $m<n$, or $m=n$ and $i\le j$. Thus, $\langle 0,0\rangle$ is the $\preceq$-least element of $X$, and the next few in increasing order are $\langle 0,1\rangle,\langle 1,0\rangle,\langle 1,1\rangle$, and $\langle 2,0\rangle$. It’s a straightforward exercise to verify that this is a well-order and that

$$f:X\to\Bbb N:\langle n,i\rangle\mapsto 2n+i$$

is an order-isomorphism whose inverse is

$$f^{-1}:\Bbb N\to X:n\mapsto\left\langle\left\lfloor\frac{n}2\right\rfloor,n-2\left\lfloor\frac{n}2\right\rfloor\right\rangle\;.$$

  • $\begingroup$ You may know about this, but an interesting example of a partially ordered set that is somewhat difficult to prove is linearly/totally ordered, and extremely difficult to prove is well ordered, was given in An ordered set of arithmetic functions representing the least $\varepsilon$-number by Thoralf Skolem (1957). $\endgroup$ Apr 20 '20 at 16:02
  • $\begingroup$ @DaveL.Renfro: Thanks; I don’t think that I had seen that before. $\endgroup$ Apr 20 '20 at 16:06
  • $\begingroup$ Ah, this is a brilliant example! Thank you very much. $\endgroup$
    – Natasha
    Apr 20 '20 at 18:33
  • $\begingroup$ @Natasha: You’re very welcome. $\endgroup$ Apr 20 '20 at 18:48
  • $\begingroup$ @brian M. Scott the inverse function seems to not work for $(2,1)$ ? $\endgroup$ Mar 4 '21 at 18:53

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.