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 ?
A "Cantor-Schroder-Bernstein" theorem for partially-ordered-sets
-
5Although 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. – 2012-07-20
4 Answers
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.
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.
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$.
One needs additional assumptions:
If $f : A \to B$ is an order-embedding of partial orders with the property that no element of $f(A)$ is comparable with an element of $B \setminus f(A)$, and $g : B \to A$ is a map with the same properties, then $A$ and $B$ are isomorphic. The usual proof of Schröder-Bernstein goes through.
Is this a new observation? Probably not. Any references are appreciated!
-
0The proof is easy. I was asking if this statement appears somewhere in a paper. – 2017-04-12