Suppose $A$ and $B$ are partially ordered sets. We use "$\le$'' to
denote both orders, instead of the more cumbersome "$\le_A$'' and
"$\le_B$'', but keep in mind that the two orders are (potentially)
much different. A bijection $f\colon A\to B$ is called an **isomorphism** if for all $x,y\in A$, $x\le y$ if
and only if $f(x)\le f(y)$. If there is such a function we say $A$
and $B$ are **isomorphic**.

When two partial orders are isomorphic, then *as partial orders*
they are, in an obvious sense, really *the same partial order.* Of
course, $A$ and $B$ may have other properties that make them much
different from each other.

Example 5.5.1 Let $A={\cal P}(\{0,1\})$, ordered by $\subseteq$. Let $B=\{1,2,3,6\}$, with $n\le m$ if and only if $n\vert m$. Then $A$ and $B$ are isomorphic.

Theorem 5.5.2 Suppose $A$, $B$ and $C$ are partially ordered sets.

a) $A$ is isomorphic to itself.

b) If $A$ is isomorphic to $B$, then $B$ is isomorphic to $A$.

c) If $A$ is isomorphic to $B$ and $B$ is isomorphic to $C$, then $A$ is isomorphic to $C$.

**Proof.**

Part (a) is trivial (use the
identity function). Part (b) we leave as an exercise. For part (c),
suppose $f\colon A\to B$ and $g\colon B\to C$ are isomorphisms.
Note that $g\circ f$ is a bijection, and if $x,y\in A$, then
$x\le y$ if and only if $f(x)\le f(y)$ (since $f$ is an isomorphism)
if and only if $g(f(x))\le g(f(y))$ (since $g$ is an isomorphism).

Example 5.5.3 If $a$ is any real number, let $I_a=(-\infty,a]\subseteq \R$, and let $\cal S$ be the collection of all of the intervals $I_a$, ${\cal S}=\{I_a:a\in \R\}\subseteq {\cal P}(\R)$, ordered by inclusion. Define $\phi\,\colon \R\to {\cal S}$ by $\phi(a)=I_a$; $\phi$ is a bijection. Note that $a\le b$ if and only if $(\infty,a]\subseteq (\infty,b]$, so $\phi$ is an isomorphism.

We can generalize this example. Suppose $\le$ is a partial ordering
of a set $A$. If $a\in A$, let $I_a=\{x\in A: x\le a\}$; we call this
the *interval determined by $a$* (but notice that it doesn't
"look like'' an interval in the more familiar sense). Let ${\cal
S}=\{I_a:a\in A\}\subseteq {\cal P}(A)$, ordered by inclusion. Define
$\phi\,\colon A\to {\cal S}$ by $\phi(a)=I_a$; $\phi$ is an
isomorphism, as we prove next.

Theorem 5.5.4 Any partially ordered set is isomorphic to a subset of a power set, ordered by the subset relation.

**Proof.**

Let $\phi$ be as above.
We show first that $\phi$ is bijective. By the definition of
${\cal S}$, $\phi$ is surjective. To show that it is injective,
suppose $a,b\in A$ and $\phi(a)=\phi(b)$. Since $a\le a$, $a\in
I_a=\phi(a)=\phi(b)=I_b$, so $a\le b$. Similarly, $b\le a$, so $a=b$,
and $\phi$ is injective. Now, given $a,b\in A$, we need to show that
$a\le b$ if and only if $I_a\subseteq I_b$. Suppose first that
$I_a\subseteq I_b$; then $a\in I_a\subseteq I_b$ implies that $a\le
b$. Conversely, suppose $a\le b$; then for any $x\in I_a$, $x\le a$
and $a\le b$, so $x\le b$ and hence $x\in I_b$. This shows that
$I_a\subseteq I_b$, and finishes the proof.

Example 5.5.5 Suppose for $a,b\in \N$, $a\le b$ means $a\vert b$. Then $I_6=\{1,2,3,6\}$ and $I_{12}=\{1,2,3,4,6,12\}$. Note that $6\vert 12$ and $I_6\subseteq I_{12}$. The theorem implies that for any $a,b\in \N$, $a$ divides $b$ if and only if the set of divisors of $a$ is a subset of the set of divisors of $b$. You should be able to see that this is true directly, that is, without using the theorem.

## Exercises 5.5

**Ex 5.5.1**
List two isomorphisms from $A$ to $B$ in
example 5.5.1. Give a bijection from
$A$ to $B$ that is *not* an isomorphism.

**Ex 5.5.2**
Let $A=\{1,2,3,4,5,6\}$ using the natural ordering.
Find $\cal S$ and the function $f\colon A\to {\cal S}$.

**Ex 5.5.3**
Let $A=\{1,2,3,4,6,12\}$ ordered by divisibility.
Find $\cal S$ and the function $f\colon A\to {\cal S}$.

**Ex 5.5.4**
Prove that for any $a,b\in \N$, $a$ divides $b$
if and only if the set of divisors of $a$ is a subset of the set of
divisors of $b$. (Prove this directly, without using
theorem 5.5.4.)

**Ex 5.5.5**
Suppose $\cal S$ is a collection of sets
ordered by inclusion.
If $\bigcap_{A\in {\cal S}}A$ is a member of $\cal S$, show
that it is the least element of $\cal S$.

**Ex 5.5.6**
Prove 5.5.2(b).

**Ex 5.5.7**
Suppose $A$ and $B$ are isomorphic and $A$ is totally
ordered. Prove that $B$ is totally ordered.

**Ex 5.5.8**
Suppose $A$ and $B$ are isomorphic and $A$ is well
ordered. Prove that $B$ is well ordered.

**Ex 5.5.9**
Show that $\Q$ and $\Z$ are not isomorphic. (Hint:
think of "order properties'' satisfied by one, but not
the other.)