LemmaStatement: AI-adaptedProof: AI-adaptedprecheck 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 $X$ well-orderable when some relation well-orders it (Well-order and well-ordered set). Work in ZF, with no choice principle. Then:

(a) $X$ is well-orderable if and only if $X \approx α$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ ) for some ordinal $α$ (Ordinal (von Neumann)).

(b) If $X$ is well-orderable there is a least ordinal equinumerous with $X$ . It is written $∣ X ∣$ and called the cardinality of $X$ .

(c) $∣ X ∣$ is a cardinal (Cardinal (initial ordinal) and cardinality).

(d) If $X \approx Y$ and $X$ is well-orderable, then $Y$ is well-orderable and $∣ Y ∣ = ∣ X ∣$ .

(e) $∣ α ∣ \leq α$ for every ordinal $α$ , and $∣ α ∣ = α$ exactly when $α$ is a cardinal.

Assuming the Axiom of Choice (The Axiom of Choice) every set is well-orderable (The well-ordering theorem), so $∣ X ∣$ 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 ∣$ under the hypothesis "Assume the Axiom of Choice", and it needs that hypothesis only to know that $X$ 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]

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

[L4]

For ordinals exactly one of $α \in β$ , $α = β$ , $β \in α$ 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 $α \leq β$ on ordinals is $α \subseteq β$ (Equinumerous sets, $A \approx B$ and $A ⪯ B$ , Ordinal (von Neumann)).

[L6]

An ordinal $κ$ is a cardinal when no $α \in κ$ satisfies $α \approx κ$ ; under the Axiom of Choice, $∣ X ∣$ is the least ordinal equinumerous with $X$ (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.1L1L2

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

1.2L2L3L4

Conversely, if $f : X \to α$ is a bijection then $x <_{X} y : ⟺ f (x) \in f (y)$ is a well-order of $X$ , since $f$ transports irreflexivity, transitivity, trichotomy and the least-element property of $\in$ on $α$ back to $X$ ; this proves claim (a).

1.3L3L5

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

2.1step 1.3L4

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

3.1step 2.1L3L4L5

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

4.1step 3.1L3L5L6

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

4.2step 3.1step 1.2L5

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

5.1step 3.1step 4.1L5L6

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

6.1step 1.1step 3.1L6L7∎

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

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 ∣$ 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 $C$ , which is determined by $C$ and not selected from it. Step 3.1 then shows that the bound $α^{+}$ , which exists only to turn "the least ordinal equinumerous with $X$ " into an instance of Separation over a set, does not affect the answer.

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

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

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources