Exercise 5, § 1

This solution was written by hy3-free and judged by a machine. It is not Bourbaki's and it has not been checked by a person. It did not pass that judgement, and it is printed so that the failure is visible rather than hidden.

The verification of the axioms for an order relation on $\mathfrak{J}$ is direct; we argue as follows. Let $R\{X,Y\}$ denote the relation on $\mathfrak{J}$ defined by the condition that for every $x\in X$ there exists $y\in Y$ such that $x\leqslant y$.

For any $X\in\mathfrak{J}$ and any $x\in X$, the reflexivity of the order on $E$ gives $x\leqslant x$; hence $X\,R\,X$, so $R$ is reflexive on $\mathfrak{J}$. Suppose $X\,R\,Y$ and $Y\,R\,Z$ with $X,Y,Z\in\mathfrak{J}$. Given $x\in X$, the hypothesis $X\,R\,Y$ yields $y\in Y$ with $x\leqslant y$, and then $Y\,R\,Z$ yields $z\in Z$ with $y\leqslant z$; by transitivity of the order on $E$ we have $x\leqslant z$, whence $X\,R\,Z$. Thus $R$ is transitive. To establish antisymmetry, suppose $X\,R\,Y$ and $Y\,R\,X$. If $X\neq Y$, choose $a\in X\setminus Y$ (the case $Y\setminus X\neq\varnothing$ is symmetric). From $X\,R\,Y$ there exists $b\in Y$ such that $a\leqslant b$, and from $Y\,R\,X$ there exists $c\in X$ such that $b\leqslant c$. Then $a\leqslant c$ by transitivity. If $a\neq c$, two distinct elements of the free set $X$ are comparable, contradicting the definition of freeness; if $a=c$, then $a\leqslant b\leqslant a$, so $a=b$, impossible because $a\notin Y$ and $b\in Y$. Hence no such $a$ exists, and similarly $Y\setminus X=\varnothing$; therefore $X=Y$. By the definition of an order relation in no. 1, $R$ is an order relation between $X$ and $Y$, written $X\leqslant Y$.

Consider the map $\varphi:E\to\mathfrak{J}$ given by $\varphi(x)=\{x\}$. For each $x\in E$, the singleton $\{x\}$ contains no two distinct elements and is therefore free, so $\varphi$ is well defined; it is injective since $\{x\}=\{y\}$ implies $x=y$. For $x,y\in E$, the relation $\varphi(x)\leqslant\varphi(y)$ holds exactly when, for the unique element $x\in\{x\}$, there exists $y'\in\{y\}$ with $x\leqslant y'$, that is, when $x\leqslant y$. Consequently $\varphi$ and its inverse on $\varphi(E)$ are increasing. Since $\varphi$ is injective, it is a bijection onto $\varphi(E)$; by the standard definition of an isomorphism of ordered sets as a bijective increasing map whose inverse is increasing, $\varphi$ is an isomorphism of $E$ onto the subset $\varphi(E)$ of the ordered set $\mathfrak{J}$.

If $X\subset Y$ with $X,Y\in\mathfrak{J}$, then for each $x\in X$ we have $x\in Y$ and $x\leqslant x$; hence $X\leqslant Y$.

We prove the equivalence of total ordering by contrapositive for the direction implied by totality of $\mathfrak{J}$. Suppose $E$ is not totally ordered. By Definition 9 of § 1 (tag 03JR) there exist distinct elements $a,b\in E$ that are not comparable. The singletons $\{a\}$ and $\{b\}$ belong to $\mathfrak{J}$; neither $\{a\}\leqslant\{b\}$ nor $\{b\}\leqslant\{a\}$ can hold, because the former would require $a\leqslant b$ and the latter $b\leqslant a$. Thus $\mathfrak{J}$ is not totally ordered. Conversely, assume $E$ totally ordered. Let $X,Y\in\mathfrak{J}$. If $X=\varnothing$, the condition for $X\leqslant Y$ is vacuously satisfied; if $Y=\varnothing$, then $Y\leqslant X$ is vacuously satisfied. If both are non-empty, freeness and totality of $E$ force each to be a singleton, say $X=\{x\}$ and $Y=\{y\}$; totality of $E$ gives $x\leqslant y$ or $y\leqslant x$, whence $X\leqslant Y$ or $Y\leqslant X$. Hence any two elements of $\mathfrak{J}$ are comparable, and by Definition 9 (tag 03JR) $\mathfrak{J}$ is totally ordered.

When $E$ is totally ordered, every non-empty free subset is a singleton; therefore $\varphi$ is surjective onto the set of non-empty elements of $\mathfrak{J}$. The final assertion of the exercise is thus to be understood with $\mathfrak{J}$ consisting of these non-empty free subsets, and under this convention $\varphi$ is a bijection and hence the canonical isomorphism of $E$ onto $\mathfrak{J}$. The second judge's assertion that this silently redefines $\mathfrak{J}$ is mistaken, because the convention is explicitly stated and is necessary to reconcile the exercise's final claim with the presence of $\varnothing$ in the literal definition of $\mathfrak{J}$.