0
$\begingroup$

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?

Thanks

$\endgroup$
1
  • 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, 2020 at 14:20

1 Answer 1

3
$\begingroup$

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\;.$$

$\endgroup$
12
  • $\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, 2020 at 16:02
  • $\begingroup$ @DaveL.Renfro: Thanks; I don’t think that I had seen that before. $\endgroup$ Apr 20, 2020 at 16:06
  • $\begingroup$ Ah, this is a brilliant example! Thank you very much. $\endgroup$
    – Natasha
    Apr 20, 2020 at 18:33
  • $\begingroup$ @Natasha: You’re very welcome. $\endgroup$ Apr 20, 2020 at 18:48
  • $\begingroup$ @brian M. Scott the inverse function seems to not work for $(2,1)$ ? $\endgroup$ Mar 4, 2021 at 18:53

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .