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

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

A1L5construct

2.1

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.

step 1.1L1A1construct

3.1

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

step 2.1L1L3L5

3.2

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

step 2.1L1

4.1

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

step 3.1step 2.1L2L4

5.1

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

step 4.1assume-contra

6.1

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)$ .

step 5.1step 4.1L5construct

7.1

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.

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

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.

Depends on

Used by

Dependency tree · two levels

19 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

Hartogs number (Wikipedia) (standard reference, not scraped)
Ordinal number (Wikipedia) (standard reference, not scraped)
J. T. Moore, MATH 6870: Set Theory (standard reference, not scraped)