LemmaStatement: Literature-sourcedProof: AI-adaptedprecheck passverified 2026-08-04 (gpt-5.6-sol-codex-subscription)

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Comparability of well-orders

Statement

Let $(V, <_{V})$ and $(W, <_{W})$ be well-orders (Well-order and well-ordered set). Then exactly one of the following holds (Order embedding and order isomorphism, Initial segment of a well-order):

(i) $V ≅ W$ ;

(ii) $V ≅ W_{< b}$ for a unique $b \in W$ ;

(iii) $V_{< a} ≅ W$ for a unique $a \in V$ .

In particular any two well-orders are comparable: one of them is order isomorphic to an initial segment of the other. No choice principle is used, which is what makes this the choice-free substitute for cardinal comparability.

Facts & Assumptions

Given: Two well-orders $(V, <_{V})$ and $(W, <_{W})$ , and the axioms of ZF. Write $≅$ for order isomorphism, and note that the defining condition below is symmetric in $V$ and $W$ , so every argument may be repeated with their roles exchanged.

[A1]

The axioms of ZF are available, in particular Separation applied to the set $V \times W$ . No choice principle is assumed.

[L2]

$V_{< v} = {x \in V : x <_{V} v}$ is a proper initial segment and is itself a well-order; $(V_{< v^{'}})_{< v} = V_{< v}$ whenever $v <_{V} v^{'}$ ; and a proper initial segment is $V_{< v}$ for a unique $v$ (Initial segment of a well-order).

[L3]

Order isomorphisms compose, invert, are strictly increasing, and carry the initial segment below a point onto the initial segment below its image (Order embedding and order isomorphism).

[L4]

No well-order is order isomorphic to a proper initial segment of itself (Rigidity of well-orders).

Proof

technique · direct

1.1A1L2L3construct

By Separation applied to $V \times W$ , the collection $f = {(v, w) \in V \times W : V_{< v} ≅ W_{< w}}$ is a set.

2.1step 1.1L2L3L4

$f$ is a function: if $V_{< v} ≅ W_{< w}$ and $V_{< v} ≅ W_{< w^{'}}$ with $w \neq w^{'}$ , say $w <_{W} w^{'}$ , then $W_{< w} = (W_{< w^{'}})_{< w}$ is a proper initial segment of the well-order $W_{< w^{'}}$ and $W_{< w^{'}} ≅ V_{< v} ≅ W_{< w}$ , contradicting [L4]; hence $w = w^{'}$ .

2.2step 1.1L2L3L4

$f$ is injective: the same argument with the roles of $V$ and $W$ exchanged shows that $V_{< v} ≅ W_{< w} ≅ V_{< v^{'}}$ forces $v = v^{'}$ .

3.1step 2.1L2L3

Let $v <_{V} v^{'}$ with $v^{'} \in d o m (f)$ , and let $g : V_{< v^{'}} \to W_{< f (v^{'})}$ be an order isomorphism; then $g$ carries $(V_{< v^{'}})_{< v} = V_{< v}$ onto $(W_{< f (v^{'})})_{< g (v)} = W_{< g (v)}$ , so $V_{< v} ≅ W_{< g (v)}$ , whence $v \in d o m (f)$ with $f (v) = g (v)$ , and $g (v) \in W_{< f (v^{'})}$ gives $f (v) <_{W} f (v^{'})$ .

4.1step 3.1L2

Consequently $d o m (f)$ is an initial segment of $V$ and $f$ is strictly increasing on it.

4.2step 3.1step 2.2L2

By the same argument with the roles of $V$ and $W$ exchanged, applied to the transpose of $f$ , which is a function because $f$ is injective, $r a n (f)$ is an initial segment of $W$ .

5.1step 4.1step 4.2step 2.2L3

$f$ is therefore a strictly increasing bijection from the initial segment $d o m (f)$ of $V$ onto the initial segment $r a n (f)$ of $W$ , hence an order isomorphism between them.

6.1step 5.1step 1.1L2

$d o m (f)$ and $r a n (f)$ are not both proper: if $d o m (f) = V_{< a}$ and $r a n (f) = W_{< b}$ then step 5.1 gives $V_{< a} ≅ W_{< b}$ , so $(a, b) \in f$ and therefore $a \in d o m (f) = V_{< a}$ , that is $a <_{V} a$ , which is impossible.

7.1step 5.1step 6.1L2

Since every initial segment is either the whole set or of the form $V_{< a}$ respectively $W_{< b}$ , exactly three configurations remain, and they give (i) $V ≅ W$ , (ii) $V ≅ W_{< b}$ , and (iii) $V_{< a} ≅ W$ respectively.

8.1step 7.1L3L4

The three are mutually exclusive: (i) with (ii) gives $W ≅ W_{< b}$ ; (i) with (iii) gives $V ≅ V_{< a}$ ; and (ii) with (iii) give an isomorphism $φ : V \to W_{< b}$ whose restriction carries $V_{< a}$ onto $W_{< φ (a)}$ , so $W ≅ V_{< a} ≅ W_{< φ (a)}$ ; each conclusion contradicts [L4].

8.2step 7.1L4L2

The witnesses are unique: $W_{< b} ≅ V ≅ W_{< b^{'}}$ forces $b = b^{'}$ by the argument of step 2.1, and $V_{< a} ≅ W ≅ V_{< a^{'}}$ forces $a = a^{'}$ by the argument of step 2.2.

9.1step 7.1step 8.1step 8.2∎

Exactly one of (i), (ii), (iii) holds, with a unique witness in cases (ii) and (iii).

Remarks

Where no choice enters. The relation $f$ is carved out of $V \times W$ by Separation, and the isomorphisms witnessing $V_{< v} ≅ W_{< w}$ are never selected: by rigidity (Rigidity of well-orders) there is at most one of them, so the definition of $f$ quantifies over them rather than picking one. That is the entire reason comparability of well-orders is a ZF theorem while comparability of arbitrary sets is not.

An alternative proof by recursion. One can instead define $f$ by transfinite recursion (Transfinite recursion), sending $v$ to the least element of $W$ not already in the image of $V_{< v}$ , and stopping when $W$ is exhausted. That route needs the recursion theorem and a little care about where the construction halts; the argument above needs only Separation and is recorded here for that reason.

Comparability is not trichotomy of size. The statement compares well-orders, not sets. Two sets need not be comparable in size in ZF at all; that they always are is equivalent to the Axiom of Choice. What survives choice-free is this lemma together with Hartogs: an ordinal that does not inject into a given set, and the ledger of what each costs is The proved choice ledger: hypotheses, equivalences, and upper bounds.

Reading it as a linear order on order types. Once every well-order is assigned an ordinal (Every well-order has a unique order type), case (ii) reads "the order type of $V$ is smaller than that of $W$ " and case (iii) reads the reverse, so this lemma is the statement that the ordinals are linearly ordered, proved before ordinals are available.

Comparability of well-orders

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources