Exercise 1, § 2

This solution was written by nemotron-3-ultra-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person.

Let $E$ be a set. Denote by $O$ the set of all order relations (i.e., graphs of orderings) on $E$. For $\Gamma, \Gamma' \in O$ we say that $\Gamma$ is coarser than $\Gamma'$ if $\Gamma' \subset \Gamma$; this defines an order relation on $O$. We shall prove that the minimal elements of $(O, \leqslant)$ are exactly the total orders on $E$.

First, suppose $\Gamma$ is a total order. Let $\Gamma' \in O$ with $\Gamma' \leqslant \Gamma$, i.e. $\Gamma \subset \Gamma'$. If $\Gamma' \neq \Gamma$ there exists $(x, y) \in \Gamma' \setminus \Gamma$. Since $\Gamma$ is total, either $(x, y) \in \Gamma$ or $(y, x) \in \Gamma$. The first is impossible, so $(y, x) \in \Gamma \subset \Gamma'$. Then both $(x, y)$ and $(y, x)$ belong to $\Gamma'$ with $x \neq y$, contradicting antisymmetry. Hence $\Gamma' = \Gamma$ and $\Gamma$ is minimal.

Conversely, let $\Gamma$ be a minimal element of $O$. Assume $\Gamma$ is not total. Then there exist $x, y \in E$ such that $(x, y) \notin \Gamma$ and $(y, x) \notin \Gamma$. We construct an order $\Gamma'$ strictly containing $\Gamma$. Define a relation on $E$ by $a \leqslant' b$ iff $(a, b) \in \Gamma$ or ($a \leqslant_\Gamma x$ and $y \leqslant_\Gamma b$) or $(a, b) = (x, y)$. One verifies routinely that $\leqslant'$ is an order relation (reflexivity and transitivity are clear; antisymmetry follows from the fact that $x$ and $y$ are incomparable in $\Gamma$). Since $(x, y) \notin \Gamma$ we have $\Gamma \subset \Gamma'$, so $\Gamma' \in O$ and $\Gamma' \leqslant \Gamma$ with $\Gamma' \neq \Gamma$, contradicting minimality. Hence $\Gamma$ is total.

Now let $\Gamma$ be an arbitrary ordering on $E$. Let $T$ be the set of all total orders on $E$ that are coarser than $\Gamma$, i.e. $\Gamma \subset \Gamma'$ for $\Gamma' \in T$. We prove that $\Gamma = \bigcap_{\Gamma' \in T} \Gamma'$. The inclusion $\Gamma \subset \bigcap_{\Gamma' \in T} \Gamma'$ is obvious. For the reverse, let $(x, y) \notin \Gamma$. We shall find a total order $\Gamma' \supset \Gamma$ with $(x, y) \notin \Gamma'$. Consider the set $S$ of all orders $\Sigma$ on $E$ such that $\Gamma \subset \Sigma$ and $(x, y) \notin \Sigma$. Order $S$ by inclusion. The set $S$ is non-empty because $\Gamma \in S$. If $C$ is a totally ordered subset of $S$, its union $U = \bigcup_{\Sigma \in C} \Sigma$ is an order relation on $E$ (the union of a chain of orders is an order), $U$ extends $\Gamma$, and $(x, y) \notin U$ because $(x, y)$ belongs to no member of $C$. Thus $U \in S$ and is an upper bound of $C$. Hence $S$ is inductive. By Theorem 2 of no. 4 (Zorn's lemma), $S$ has a maximal element $\Gamma_{\max}$.

We claim $\Gamma_{\max}$ is total. Suppose not; then there exist $u, v \in E$ incomparable in $\Gamma_{\max}$. Form the two orders $\Sigma_1, \Sigma_2$ obtained by adding $(u, v)$ respectively $(v, u)$ to $\Gamma_{\max}$ and taking the transitive closure. If both $\Sigma_1$ and $\Sigma_2$ contained $(x, y)$, then from $\Sigma_1$ we would have $x \leqslant_{\max} u$ and $v \leqslant_{\max} y$, and from $\Sigma_2$ we would have $x \leqslant_{\max} v$ and $u \leqslant_{\max} y$. Then $x \leqslant_{\max} u \leqslant_{\max} y$ gives $x \leqslant_{\max} y$, contradicting $(x, y) \notin \Gamma_{\max}$. Hence at least one of $\Sigma_1, \Sigma_2$ belongs to $S$ and strictly contains $\Gamma_{\max}$, contradicting maximality. Therefore $\Gamma_{\max}$ is total. It belongs to $T$ and does not contain $(x, y)$. Consequently $(x, y) \notin \bigcap_{\Gamma' \in T} \Gamma'$, which completes the proof.

Finally, let $(E, \Gamma)$ be an ordered set. By the preceding result, $\Gamma = \bigcap_{i \in I} \Gamma_i$ where each $\Gamma_i$ is a total order on $E$ with $\Gamma \subset \Gamma_i$. Consider the product ordered set $P = \prod_{i \in I} (E, \Gamma_i)$ endowed with the product order (i.e. $(a_i) \leqslant (b_i)$ iff $a_i \leqslant_{\Gamma_i} b_i$ for all $i$). Define $\varphi : E \to P$ by $\varphi(x) = (x)_{i \in I}$. Then $\varphi$ is injective, and for $x, y \in E$ we have

Thus $\varphi$ is an order isomorphism from $(E, \Gamma)$ onto its image $\varphi(E) \subset P$. Hence every ordered set is isomorphic to a subset of a product of totally ordered sets.