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

  • $\begingroup$ 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? $\endgroup$ – John D Jun 1 at 9:27

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.