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

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

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}^{ 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}^{ 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.
• In definition of $\le_n$ is not clear what means $a \le b$. – Tom Ryddle May 29 at 12:46
• @TomRyddle I think $\mathbb{N}^{<n}$ means $\{0,\dots,n-1 \}$ here. I agree that this is a confusing choice of notation. – Jonathan May 29 at 18:42

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.
• I think define $f$ recursively , I mean $f(0)= min(A)$ and $f(1)=min(A)+1$ so we will get bijection. is it correct? if yes, how we can define it formally? – John D Jun 1 at 9:27