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

$\square$

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.

$\square$

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