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.

If A and B are partially-ordered-sets, such that there are injective order-preserving maps from A to B and from B to A, is there necessarily an order-preserving bijection between A and B ?

share|improve this question
3  
Although the answer to your question is "no", there is a similar-sounding true proposition (Lindenbaum theorem): If A and B are linearly ordered sets, A is isomorphic to an initial segment of B, and B is isomorphic to a final segment of A, then A and B are isomorphic. –  Vladimir Reshetnikov Jul 20 '12 at 2:39
add comment

3 Answers

up vote 10 down vote accepted

One does not have to go to partially ordered sets for a counterexample. Linear orders are enough: Consider the rationals in the open interval $(0,1)$ and the rationals in the closed interval $[0,1]$.

The two obviously embed into one another but are not isomorphic due to minimum/maximum considerations.


My example shows that linear orders need not have this property; and Brian's example shows that well-founded partially ordered sets need not have this property.

However if we consider the intersection, well-founded linear orders (i.e. well orders) then indeed this is true. Namely, if $(A,<)$ and $(B,\prec)$ are two well ordered sets and $(A,<)$ embeds into $(B,\prec)$ and vice versa then there exists an isomorphism.

share|improve this answer
add comment

No. Let $P$ be the disjoint union of chains of every odd length, and let $Q$ be the disjoint union of chains of every positive even length. Clearly each can be embedded in the other, but the two are not isomorphic.

More formally, let $$P=\{\langle 2n+1,k\rangle:n\in\Bbb N\text{ and }1\le k\le 2n+1\}$$ and $$Q=\{\langle 2n,k\rangle:n\in\Bbb Z^+\text{ and }1\le k\le 2n\}\;,$$

each ordered by the relation $\langle m,k\rangle\preceq\langle n,\ell\rangle$ iff $m=n$ and $k\le\ell$. The map $$f:P\to Q:\langle 2n+1,k\rangle\mapsto\langle 2n+2,k\rangle$$ embeds $P$ into $Q$, and the map $$g:Q\to P:\langle 2n,k\rangle\mapsto\langle 2n+1,k\rangle$$ embeds $Q$ into $P$, but $\langle P,\preceq\rangle$ and $\langle Q,\preceq\rangle$ are clearly not isomorphic, as they contain maximal chains of different lengths.

This shows that there is no such result even for well-founded partial orders.

share|improve this answer
add comment

Here's an example with scattered countable linear orderings: a set of order type $\omega^*\omega$ and a set of order type $1+\omega^*\omega$.

share|improve this answer
add comment

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.