Exercise 10, § 4

(a) An ordered set E is isomorphic to a subset of a product of $n$ totally ordered sets if and only if the graph of the ordering on E is the intersection of the graphs of $n$ total orderings on E. (To show that the condition is necessary, show that if

is a product of $n$ totally ordered sets, then the graph of the product ordering on F is the intersection of $n$ graphs of lexicographic orderings on F.)

(b) An ordered set E is isomorphic to a subset of a product of two totally ordered sets if and only if the ordering $\Gamma$ on E is such that there exists another ordering $\Gamma'$ on E with the property that any two distinct elements of E are comparable with respect to exactly one of the orderings $\Gamma$, $\Gamma'$.

(c) Let A be a finite set of $n$ elements. Let E be the subset of $\mathfrak{P}(A)$ consisting of all subsets $\{x\}$ and $A - \{x\}$ as $x$ runs through A. Show that $n$ is the smallest integer $m$ such that E, ordered by inclusion, is isomorphic to a subset of a product of $m$ totally ordered sets (use (a)).