Alphabeta Math
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∈W;

(iii) V<a≅W for a unique a∈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×W. No choice principle is assumed.

[L2]

V<v={x∈V:x<Vv} is a proper initial segment and is itself a well-order; (V<v′)<v=V<v whenever v<Vv′; 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.1

By Separation applied to V×W, the collection f={(v,w)∈V×W:V<v≅W<w} is a set.

A1L2L3construct
2.1

f is a function: if V<v≅W<w and V<v≅W<w′ with w≠w′, say w<Ww′, 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′.

step 1.1L2L3L4
2.2

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′.

step 1.1L2L3L4
3.1

Let v<Vv′ with v′∈dom(f), and let g:V<v′→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∈dom(f) with f(v)=g(v), and g(v)∈W<f(v′) gives f(v)<Wf(v′).

step 2.1L2L3
4.1

Consequently dom(f) is an initial segment of V and f is strictly increasing on it.

step 3.1L2
4.2

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, ran(f) is an initial segment of W.

step 3.1step 2.2L2
5.1

f is therefore a strictly increasing bijection from the initial segment dom(f) of V onto the initial segment ran(f) of W, hence an order isomorphism between them.

step 4.1step 4.2step 2.2L3
6.1

dom(f) and ran(f) are not both proper: if dom(f)=V<a and ran(f)=W<b then step 5.1 gives V<a≅W<b, so (a,b)∈f and therefore a∈dom(f)=V<a, that is a<Va, which is impossible.

step 5.1step 1.1L2
7.1

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.

step 5.1step 6.1L2
8.1

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→W<b whose restriction carries V<a onto W<φ(a), so W≅V<a≅W<φ(a); each conclusion contradicts [L4].

step 7.1L3L4
8.2

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.

step 7.1L4L2
9.1

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

step 7.1step 8.1step 8.2∎

Remarks

Where no choice enters. The relation f is carved out of V×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.

Depends on

Used by

Dependency tree · two levels

11 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources