Lesson 7

For that we need to prove the following two lemmas. Lemma. Let \((S, \leq_{S})\) and \((T, \leq_{T})\) be two correct fragments. Then one of them is an initial segment of the other, and their orders are compatible (any two common elements must still be comparable – either with respect to \(\leq_{S}\) or to \(\leq_{T}\)). Proof. Let \(S\) be isomorphic to an initial segment of \(T\) via an isomorphism \(h : S \to T\) (constructed from one of the previous theorems). The lemma asserts that this isomorphism is, in fact, the identity map, i.e., that \(h(x) = x\) for all \(x \in S\).

We prove this by induction on \(x \in S\) (this is legitimate since \(S\) is well-ordered under the definition of a correct fragment). The inductive assumption guarantees that \(h(y) = y\) for all \(y < x\). We aim to prove that \(h(x) = x\).

Consider the initial segments \([0, x)\) and \([0, h(x))\) (with respect to the orders \(\leq_{S}\) and \(\leq_{T}\), respectively). Both are isomorphic to each other via the restriction of \(h\), and by the inductive hypothesis they coincide as sets. Thus, by the definition of correct fragments, \[x = \varphi([0, x)) \quad \text{and}\quad h(x) = \varphi([0, h(x))),\] which implies \(x = h(x)\). This completes the proof of the Lemma.◼

Let us now consider the union of all correct fragments (as sets). A natural linear order is defined on this union: for any two elements, there exists a fragment to which both belong (each element belongs to some fragment, and we may take the larger one), and hence they can be compared. By the Lemma, the ordering does not depend on the choice of fragment used for the comparison.

Lemma. This union is itself a correct fragment. Proof. Let \(U\) be the union and let \(X \subseteq U\) be non-empty. Choose an element \(x \in X\) and a correct fragment \(F\) containing it. The set \(X \cap F\) is non-empty, so it has a least element \(m\). We claim that \(m\) is the least element of \(X\). Indeed, let \(y \in X\) and choose a correct fragment \(G\) containing \(y\). One of the fragments \(F\) and \(G\) is an initial segment of the other. If \(G\) is an initial segment of \(F\), then \(y \in F\) and hence \(m \leq y\). If \(F\) is an initial segment of \(G\), then either \(y \in F\) or \(y\) lies above every element of \(F\), so again \(m \leq y\). Thus, the order on \(U\) is a well-order.

It remains to verify the correctness condition. Let \(s \in U\) and choose a correct fragment \(F\) containing \(s\). The elements of \(U\) smaller than \(s\) are exactly the elements of \(F\) smaller than \(s\): any other fragment is comparable with \(F\) by inclusion as an initial segment and therefore cannot add a new element below \(s\). Hence, the initial segment \([0,s)\) is the same in \(U\) and in \(F\), and the correctness of \(F\) gives \(s=\varphi([0,s))\). Therefore, \(U\) is a correct fragment.◼ The assertion of the Lemma may be reformulated as follows: there exists a maximal correct fragment.