Show that exists $n\in \Bbb{N}$ such that $\langle A,R \rangle$ and $\langle \Bbb{N}^{<n},\le_{n} \rangle$ are isomorphic.

Question

Given $n\in \Bbb{N}$, we mark $\le_{n} = \{\langle a,b \rangle : a,b\in \Bbb{N}^{<n} \text{ and } a\le b \}$.

Let be finite set $A$ and let $R$ be a total order on $A$. Show that exists $n\in \Bbb{N}$ such that $\langle A,R \rangle$ and $\langle \Bbb{N}^{<n},\le_{n} \rangle$ are isomorphic.

Here How I try to prove it and stuck:

We need to show that there exist n a natural number such that exists function $f$ bijective and for all $a,b\in A$, $aRb \text { if and only if } f(a)\le_{n}f(b).$

A is finite set then exist $n\in \Bbb{N}$ such that exists $f:A \to \Bbb{N}^{<n}$ bijective. Left to show that for all $a,b\in A$, $aRb \text { if and only if } f(a)\le_{n}f(b).$

Let $a,b \in A$

• ($\rightarrow$): Assuming $aRb$ we need to show $f(a)\le_{n}f(b)$. ...

• ($\leftarrow$): Assuming $f(a)\le_{n}f(b)$, we need to show $aRb$. ...

In my proof and I do not use that R total order on A which I think this must be in my proof. Moreover, I am not sure if this correct that I show that there are exist function bijective using A is finite set and not give my own function and prove it that is bijective since I think, I can define function $f$ recrusivily so it will be bijective. However, I don`t know how to do it.

If my starting in my proof is correct - How can I continue the proof?

---

Below are some definitions which are relevant to the question.

Let $\langle A_1,R_1 \rangle$ and $\langle A_2,R_2 \rangle$ partially ordered sets.

1. Let $f:A_1 \to A_2$ function. $f$ is isomorphism from $\langle A_1,R_1 \rangle$ to $\langle A_2,R_2 \rangle$ if f is bijective on $A_2$ and for all $a,b\in A_1$, $aR_1b$ if and only if $f(a)R_2f(b)$.
2. if exists function $f$ which isomorphism from from $\langle A_1,R_1 \rangle$ to $\langle A_2,R_2 \rangle$ we say that $\langle A_1,R_1 \rangle$ and $\langle A_2,R_2 \rangle$ are isomorphic.

Answer 1

You assume that you have given a map $f$, and try to find properties for the relation. This won't work, you need to construct $f$.

Try some examples first, maybe with $n = 2,3,4$. Then, you should notice that there is exactly one way to define a bijection $f : \mathbb{N}^{< n} \to A$ such that $R$ satisfies the desired properties (given, of course, that $A$ has exactly $n-1$ elements).

Once you see how that looks like, try to find a general rule to define $f$. Once you have that, proof that this rule will always generate a function satisfying all conditions.