TheoremStatement: Literature-sourcedProof: AI-adaptedprecheck passjudge pass (deepseek-v4-pro + gpt-5.6-terra)verified 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.

Hartogs: an ordinal that does not inject into a given set

Statement

For every set $A$ there is an ordinal (Ordinal (von Neumann)) that does not inject into $A$ , that is, admits no injective function into $A$ . The least such ordinal is the Hartogs number $ℵ (A)$ , and it is exactly

$ℵ (A) = {o t (S, R) : S \subseteq A and R well-orders S},$

the set of order types (Every well-order has a unique order type) of the well-ordered subsets of $A$ .

The proof is choice free. That is the whole point of the theorem: in ZF alone, with no assumption that $A$ can be well ordered, one still gets an ordinal too long to be laid inside $A$ .

Facts & Assumptions

Given: A set $A$ and the axioms of ZF, in particular Power Set, Separation, Union and Replacement. No choice principle is assumed. " $X$ injects into $A$ " abbreviates "there is an injective function $X \to A$ ".

[A1]

Power Set, Separation, Union and Replacement are available.

[L1]

Every well-order is order isomorphic to a unique ordinal, its order type, and the isomorphism is unique (Every well-order has a unique order type).

[L2]

An ordinal is a transitive set on which $\in$ is a strict well-order (Ordinal (von Neumann)).

[L3]

Every element of an ordinal is an ordinal, no ordinal is a member of itself, and $α \subseteq β$ if and only if $α \in β$ or $α = β$ (Basic closure properties of ordinals).

[L4]

Any two ordinals satisfy exactly one of $α \in β$ , $α = β$ , $β \in α$ , and every set of ordinals is well ordered by $\in$ (Trichotomy and well-ordering of the ordinals).

[L5]

A well-order is a total order in which every nonempty subset has a least element (Well-order and well-ordered set); an order isomorphism carries the initial segment below a point onto the initial segment below its image (Order embedding and order isomorphism, Initial segment of a well-order).

Proof

technique · contradiction

1.1A1L5construct

By Power Set and Separation the collection $W = {(S, R) \in P (A) \times P (A \times A) : R well-orders S}$ is a set, since every well-order of a subset of $A$ is a subset of $A \times A$ .

2.1step 1.1L1A1construct

Each $(S, R) \in W$ has a unique order type $o t (S, R)$ by [L1], so the assignment is given by a formula and Replacement makes $H = {o t (S, R) : (S, R) \in W}$ a set of ordinals; uniqueness is what makes this a definable function, so nothing is selected.

3.1step 2.1L1L3L5

$H$ is a transitive set: let $α = o t (S, R) \in H$ with order isomorphism $g$ from $α$ onto $(S, R)$ , and let $β \in α$ ; then $β$ is an ordinal with $β \subseteq α$ , so $β$ is the initial segment of $α$ below $β$ , and $g$ carries it onto an $R$ -initial segment $S^{'} \subseteq S$ , which $R^{'} = R \cap (S^{'} \times S^{'})$ well-orders with order type $β$ ; hence $(S^{'}, R^{'}) \in W$ and $β \in H$ .

3.2step 2.1L1

Every $α \in H$ injects into $A$ : writing $α = o t (S, R)$ , the order isomorphism from $α$ onto $S$ is in particular an injection of $α$ into $S \subseteq A$ .

4.1step 3.1step 2.1L2L4

$H$ is an ordinal: it is transitive by step 3.1 and $\in$ strictly well-orders it by [L4], since it is a set of ordinals.

5.1step 4.1assume-contra

Suppose, for contradiction, that the ordinal $H$ of step 4.1 injects into $A$ , say by an injective $j : H \to A$ .

6.1step 5.1step 4.1L5construct

Put $S = j [H] \subseteq A$ and $R = {(j (ξ), j (η)) : ξ \in η \in H} \subseteq A \times A$ ; then $j$ is a bijection of $H$ onto $S$ carrying membership to $R$ , so $R$ well-orders $S$ and $j$ is an order isomorphism from $(H, \in)$ onto $(S, R)$ .

7.1step 6.1step 1.1step 2.1step 3.2step 4.1L1L3L4discharge-contradiction∎

Hence $(S, R) \in W$ and $o t (S, R) = H$ by the uniqueness in [L1], so $H \in H$ , which no ordinal satisfies; therefore $H$ does not inject into $A$ , and since every member of $H$ does inject into $A$ by step 3.2, trichotomy leaves $H \leq γ$ for every ordinal $γ$ that fails to inject, so $H = ℵ (A)$ is the least such ordinal.

Remarks

Where choice would have crept in, and why it does not. A careless proof says "for each well-orderable subset of $A$ choose a well-ordering of it", which is a genuine use of choice. The construction above never chooses: it collects all pairs $(S, R)$ , so the well-ordering is part of the datum, and it then maps each pair to its order type, which is unique by Every well-order has a unique order type. The passage from a class of well-orders to a set of ordinals is Replacement, not choice.

What the theorem does and does not say. It does not say $A$ can be well ordered, and it gives no injection of $A$ into an ordinal. It says only that the ordinals run out of room to sit inside $A$ . Under the Axiom of Choice, $A$ is well orderable (The well-ordering theorem) and $ℵ (A)$ is the least ordinal that does not inject into $A$ , that is the least cardinal strictly larger than the cardinality of $A$ -- not merely the least ordinal strictly larger than an ordinal equinumerous with $A$ , since for $A = N$ that would be $ω + 1$ , which still injects into $N$ ; without choice, $ℵ (A)$ may be incomparable with $A$ in size, and that is still enough for the applications.

The ZF substitute for cardinal comparability. "Any two sets are comparable in size" is equivalent to the Axiom of Choice, so it is unavailable here. What survives is this theorem together with Comparability of well-orders: well-orders are always comparable, and every set has an ordinal it cannot absorb. Hartogs proved in 1915 that cardinal comparability implies the well-ordering theorem, and this construction is the engine of that proof.

A crude bound is not enough. Burali-Forti: there is no set of all ordinals already shows that the ordinals are not a set, so no set can contain them all, but that alone does not produce a single ordinal failing to inject into a given $A$ . The content here is that the failure happens at a definable, and indeed least, place.

Hartogs: an ordinal that does not inject into a given set

Statement

Facts & Assumptions

Proof

Remarks

Depends on

Dependency tree · 2 levels

Sources