Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
This is a very good question, and it's very nice to see that you have posted your own attempts on the topic. –  Asaf Karagila Dec 29 '12 at 21:45

2 Answers 2

up vote 2 down vote accepted

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

share|improve this answer
    
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! –  Serpahimz Dec 29 '12 at 21:50
    
@Serpahimz: Thanks! –  Brian M. Scott Dec 29 '12 at 21:55

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.

share|improve this answer
    
Thanks Asaf, your replies are always very enriching. I'm not familiar with linearization of partial orders yet but I'll look it up. –  Serpahimz Dec 29 '12 at 21:50
    
@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. –  Asaf Karagila Dec 29 '12 at 21:59

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.