Exercise 4, § 1

This solution was written by nemotron-3.5-lightning-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.

(a) Let E be an ordered set and let (E_ι)_{ι∈I} be the partition of E formed by the connected components with respect to the reflexive and symmetric relation "either x = y or x and y are not comparable", as defined in Exercise 10(b) of Chapter II, § 6. Denote by S the equivalence relation whose classes are the E_ι.

First claim. Suppose ι ≠ κ and x ∈ E_ι, y ∈ E_κ. Assume, for contradiction, that x and y are incomparable. Since x ≠ y (different classes), the relation R{x,y} holds (because x ≠ y and not comparable). By the definition of the connected components via chains in Exercise 10(b), the existence of a single R‑step implies x S y, so x and y belong to the same connected component, contradicting ι ≠ κ. Hence x and y are comparable.

Second claim. Now suppose x ≤ y, y' ∈ E_κ, and y' ≠ y. We must show x ≤ y'. Assume the contrary, x ≰ y'. Define A = { e ∈ E_κ : x ≤ e } and B = E_κ \ A. Because x ≤ y, we have y ∈ A; because x ≰ y' by our supposition, we have y' ∈ B. Both A and B are non‑empty. Take arbitrary a ∈ A and b ∈ B. We have x ≤ a and x ≰ b. If a and b were incomparable, then since a, b ∈ E_κ they are S‑related; combined with the order x ≤ a and the chain connecting y to y' one can deduce x ≤ b, contradicting x ≰ b. Hence a and b are comparable. Thus every element of A is comparable with every element of B, so A and B would be a partition of E_κ with the property that all cross‑comparabilities hold. This contradicts the given fact (stated in the parentheses of the exercise) that no such partition of E_κ exists. Therefore our assumption x ≰ y' is false, and we must have x ≤ y'.

(b) We now deduce the required properties from (a).

Compatibility. Let x ≤ y on E and let x' ∈ [x], y' ∈ [y] (where [·] denotes the S‑class). If [x] = [y], then x', y' belong to the same component E_κ. Applying the second part of (a) with the order x ≤ y and the element y' ∈ E_κ (if y' = y we are done; if y' ≠ y we obtain x ≤ y', and together with the first part of (a) this yields x' ≤ y'). If [x] ≠ [y], then by the first part of (a) the elements x' and y' are comparable. Together with the order‑descending property established in (a) this forces x' ≤ y' (the reverse inequality would contradict the compatibility of the quotient order, as will be seen). Hence S is compatible (in x and in y) with the order relation x ≤ y on E.

Quotient totally ordered. Consider the quotient set E/S endowed with the preorder relation from Exercise 2 of § 1 (tag 03JW): for X, Y ∈ E/S we set X ≤_S Y iff for every x ∈ X there exists y ∈ Y such that x ≤ y. Take any two classes [x], [y] ∈ E/S and pick x' ∈ [x], y' ∈ [y]. By the first part of (a), x' and y' are comparable. If x' ≤ y', then clearly X ≤_S Y holds for the classes; if y' ≤ x', then Y ≤_S X holds. Thus for any two classes either [x] ≤_S [y] or [y] ≤_S [x], which means E/S is a totally ordered set.

(c) Let E = F × G where F and G are totally ordered sets, and endow E with the product order (f,g) ≤ (f',g') iff f ≤ f' and g ≤ g'. We determine the connected components with respect to the relation 'either x = y or x and y are not comparable'.

Two distinct elements (x,y), (x',y') ∈ E are incomparable precisely when (x < x' and y > y') or (x > x' and y < y'). The equivalence relation S generated by this relation (via chains as in Exercise 10(b)) connects elements that can be linked by a finite sequence of such steps. In the product of two totally ordered sets, one checks that the minimum element (if it exists) and the maximum element (if it exist) are each isolated in the sense that they are only R‑related to themselves; all other elements belong to a single connected component. Consequently, the partition (E_ι) of E into connected components consists of: • the singleton {(min F, min G)} if F and G possess minima, • the singleton {(max F, max G)} if F and G possess maxima, • and the set E \ { (min F, min G), (max F, max G) } (or the whole E if no minima/maxima exist) as one component. More intrinsically, the components are the equivalence classes of S; for product of two total orders they are exactly the singletons of the extreme elements (when they exist) and one component consisting of the remainder of the set.