4
$\begingroup$

Suppose $\left(A,\leq_{A}\right)$ and $\left(B,\leq_{B}\right)$ are Posets and $f:A\to B$ is an order preserving bijection. I'm trying to show that $f^{-1}:B\to A$ is also order preserving. That is I want to show that given $b_{1},b_{2}\in B$ $$b_{1}\leq_{B}b_{2}\Longrightarrow f^{-1}\left(b_{1}\right)\leq_{A}f^{-1}\left(b_{2}\right)$$ Since $f$ is bijective there are uniquely defined $a_{1},a_{2}\in A$ such that $$b_{1}=f\left(a_{1}\right)\Longrightarrow a_{1}=f^{-1}\left(b_{1}\right)$$ $$b_{2}=f\left(a_{2}\right)\Longrightarrow a_{2}=f^{-1}\left(b_{2}\right)$$ If $a_{1},a_{2}$ are comparable and I assume $a_{2}\leq_{A}a_{1}$ I get a contradiction since $f$ is order preserving: $$b_{2}=f\left(a_{2}\right)\leq_{B}\, f\left(a_{1}\right)=b_{1}$$ So I deduce that if $a_{1},a_{2}$ are comparable then necessarily the required inequality holds. My question is whether it's possible that $a_{1},a_{2}$ are not comparable and the claim is actually false?

$\endgroup$
1
  • 1
    $\begingroup$ This is a very good question, and it's very nice to see that you have posted your own attempts on the topic. $\endgroup$ – Asaf Karagila Dec 29 '12 at 21:45
4
$\begingroup$

Let $A=\{0,1\}\times\Bbb N$, and define $\langle i,m\rangle\le_A\langle j,n\rangle$ iff $i=j$ and $m\le n$. Let $B=\Bbb N$ with the usual order. Finally, let

$$f:A\to B:\langle i,n\rangle\mapsto 2n+i\;.$$

Then $f$ is an order-preserving bijection, but $f^{-1}$ is not order-preserving for exactly the reason that you suggest: for any $n\in\Bbb N$, $2n<2n+1$ in $B$, but $f^{-1}(2n)=\langle 0,n\rangle$ and $f^{-1}(2n+1)=\langle 1,n\rangle$ are not comparable in $A$.

$\endgroup$
2
  • $\begingroup$ I had a feeling the claim is false but I couldn't come up with a counter example off the top of my head. This one is quite nice! $\endgroup$ – Serpahimz Dec 29 '12 at 21:50
  • $\begingroup$ @Serpahimz: Thanks! $\endgroup$ – Brian M. Scott Dec 29 '12 at 21:55
3
$\begingroup$

To drive Brian's point further, let's assume for simplicity that $f$ is the identity. This simply means that $\leq_A\subseteq\leq_B$ as sets of ordered pairs.

For example, if $(A,R)$ is any partially ordered set, and $(A,\leq_R)$ is a linearlization of $R$ then the identity is an order-preserving bijection, but its inverse need not be order-preserving.

Even further, if $A$ contains more than one point, then $(A,\mathrm{Id}_A)$ is a partial order (the discrete order) and the identity is an order-preserving map between $(A,R)$ for any partial order $R$. Its inverse, also the identity, is order-preserving if and only if $R=\mathrm{Id}_A$ as well.

$\endgroup$
2
  • $\begingroup$ Thanks Asaf, your replies are always very enriching. I'm not familiar with linearization of partial orders yet but I'll look it up. $\endgroup$ – Serpahimz Dec 29 '12 at 21:50
  • $\begingroup$ @Serpahimz: It simply means that if $(A,R)$ is a partially ordered set then there is some $R'$ such that $R\subseteq R'$ and $(A,R')$ is a linearly ordered set. For finite sets this is provable in ZF, and for general posets this requires the axiom of choice, but this is strictly weaker than the axiom of choice. $\endgroup$ – Asaf Karagila Dec 29 '12 at 21:59

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.