Alphabeta Math
LemmaStatement: AI-adaptedProof: AI-adaptedSession-authored (Fable 5 assisted)precheck passjudge pass (z-ai/glm-5.2)verified 2026-07-29 (claude-fable-5)
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.

A set equinumerous with some ordinal has a least such ordinal, that ordinal is a cardinal, and equinumerous sets get the same one; no choice principle is used

Statement

Call a set XX well-orderable when some relation well-orders it (Well-order and well-ordered set). Work in ZF, with no choice principle. Then:

(a) XX is well-orderable if and only if XαX \approx \alpha (Equinumerous sets, ABA \approx B and ABA \preceq B) for some ordinal α\alpha (Ordinal (von Neumann)).

(b) If XX is well-orderable there is a least ordinal equinumerous with XX. It is written X\lvert X \rvert and called the cardinality of XX.

(c) X\lvert X \rvert is a cardinal (Cardinal (initial ordinal) and cardinality).

(d) If XYX \approx Y and XX is well-orderable, then YY is well-orderable and Y=X\lvert Y \rvert = \lvert X \rvert.

(e) αα\lvert \alpha \rvert \le \alpha for every ordinal α\alpha, and α=α\lvert \alpha \rvert = \alpha exactly when α\alpha is a cardinal.

Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem), so X\lvert X \rvert is then defined for every set and is exactly the cardinality of Cardinal (initial ordinal) and cardinality.

Why this item exists. Cardinal (initial ordinal) and cardinality introduces X\lvert X \rvert under the hypothesis "Assume the Axiom of Choice", and it needs that hypothesis only to know that XX carries a well-order at all. Everything below is about well-orderable sets and is a theorem of ZF, which is what makes it possible to state Hessenberg's theorem and Tarski's theorem, one of which is choice-free and the other of which is precisely about the gap between ZF and ZFC.

Facts & Assumptions

Given: The axioms of ZF, in particular Separation and Replacement. No choice principle is assumed except where the Axiom of Choice is named.

[L1]

Every well-order is order isomorphic to exactly one ordinal, its order type (Every well-order has a unique order type).

[L2]

An order isomorphism is in particular a bijection (Order embedding and order isomorphism, Injection, surjection, bijection).

[L3]

α+=α{α}\alpha^{+} = \alpha \cup \{\alpha\} is an ordinal, every element of an ordinal is an ordinal, αα\alpha \notin \alpha, and αβ\alpha \subseteq \beta if and only if αβ\alpha \in \beta or α=β\alpha = \beta (Basic closure properties of ordinals, Ordinal (von Neumann)).

[L4]

For ordinals exactly one of αβ\alpha \in \beta, α=β\alpha = \beta, βα\beta \in \alpha holds, and every nonempty set of ordinals has an \in-least element (Trichotomy and well-ordering of the ordinals).

[L5]

\approx is reflexive, symmetric and transitive, and the order relation αβ\alpha \le \beta on ordinals is αβ\alpha \subseteq \beta (Equinumerous sets, ABA \approx B and ABA \preceq B, Ordinal (von Neumann)).

[L6]

An ordinal κ\kappa is a cardinal when no ακ\alpha \in \kappa satisfies ακ\alpha \approx \kappa; under the Axiom of Choice, X\lvert X \rvert is the least ordinal equinumerous with XX (Cardinal (initial ordinal) and cardinality).

[L7]

Assuming the Axiom of Choice, every set carries a well-order (The Axiom of Choice, The well-ordering theorem).

Proof

technique · direct
1.1

If << well-orders XX then (X,<)(X, <) has an order type α\alpha and the collapsing map is an order isomorphism, hence a bijection XαX \to \alpha, so XαX \approx \alpha.

L1L2
1.2

Conversely, if f:Xαf : X \to \alpha is a bijection then x<Xy:    f(x)f(y)x <_X y :\iff f(x) \in f(y) is a well-order of XX, since ff transports irreflexivity, transitivity, trichotomy and the least-element property of \in on α\alpha back to XX; this proves claim (a).

L2L3L4
1.3

Assume now XαX \approx \alpha for an ordinal α\alpha, and put C={ξα+:ξX}C = \{\xi \in \alpha^{+} : \xi \approx X\}, a set by Separation inside the ordinal α+\alpha^{+}, all of whose elements are ordinals, and nonempty because αα+\alpha \in \alpha^{+} and αX\alpha \approx X.

L3L5
2.1

By [L4] the set CC has an \in-least element κ\kappa, and κX\kappa \approx X.

step 1.3L4
3.1

κ\kappa is least among all ordinals equinumerous with XX: given βX\beta \approx X, trichotomy gives βα+\beta \in \alpha^{+}, in which case βC\beta \in C and κβ\kappa \subseteq \beta by minimality; or else α+β\alpha^{+} \subseteq \beta, in which case αα+β\alpha \in \alpha^{+} \subseteq \beta gives αβ\alpha \subseteq \beta, while αC\alpha \in C gives κα\kappa \subseteq \alpha, so again κβ\kappa \subseteq \beta. This proves claim (b), with X:=κ\lvert X \rvert := \kappa.

step 2.1L3L4L5
4.1

Claim (c): if γκ\gamma \in \kappa had γκ\gamma \approx \kappa then γX\gamma \approx X by [L5], so κγ\kappa \subseteq \gamma by step 3.1, whence γκγ\gamma \in \kappa \subseteq \gamma and γγ\gamma \in \gamma, which [L3] forbids; so κ\kappa is a cardinal.

step 3.1L3L5L6
4.2

Claim (d): if XYX \approx Y then an ordinal is equinumerous with XX exactly when it is equinumerous with YY, by symmetry and transitivity of \approx, so the two least such ordinals coincide; and YκY \approx \kappa makes YY well-orderable by step 1.2.

step 3.1step 1.2L5
5.1

Claim (e): αα\alpha \approx \alpha, so αα\lvert \alpha \rvert \subseteq \alpha by step 3.1; if α\alpha is a cardinal then no ξα\xi \in \alpha is equinumerous with α\alpha, so the least ordinal equinumerous with α\alpha is α\alpha itself; and conversely α=α\lvert \alpha \rvert = \alpha makes α\alpha a cardinal by step 4.1.

step 3.1step 4.1L5L6
6.1

Assuming the Axiom of Choice, every set XX carries a well-order by [L7], hence XXX \approx \lvert X \rvert by step 1.1 and X\lvert X \rvert is defined for every set; and by step 3.1 it is the least ordinal equinumerous with XX, which is what [L6] calls the cardinality of XX.

step 1.1step 3.1L6L7

Remarks

What is choice-free and what is not. Claims (a) to (e) are theorems of ZF: they say what happens for a well-orderable set, and the hypothesis of well-orderability is carried explicitly rather than supplied by an axiom. The Axiom of Choice enters only in the last step, where it removes the hypothesis by making every set well-orderable. Without choice a set may be equinumerous with no ordinal at all, and then X\lvert X \rvert simply does not exist; that is the situation Hartogs: an ordinal that does not inject into a given set is designed for.

Nothing is chosen. The one place a selection might be expected is step 2.1, and there the element taken is the \in-least member of CC, which is determined by CC and not selected from it. Step 3.1 then shows that the bound α+\alpha^{+}, which exists only to turn "the least ordinal equinumerous with XX" into an instance of Separation over a set, does not affect the answer.

Notation. From here on X\lvert X \rvert always means the ordinal of claim (b). For a finite set this is not yet known to agree with the natural number written A\lvert A \rvert in The cardinality A\lvert A\rvert of a finite set; that agreement is a theorem and is proved on this page.

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 64 results over 22 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.

Sources