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.
The Hartogs number of an -element set is
Example
Let for some natural number (Equinumerous sets, and , The natural numbers (von Neumann)). Then the Hartogs number of Hartogs: an ordinal that does not inject into a given set equals : the set of order types of well-orders of subsets of is exactly the set of ordinals with , and is the least ordinal that does not inject into . In particular the cardinality of determines its Hartogs number, and no choice principle is used.
Facts & Assumptions
Given: A set with a bijection onto a natural number , the ordinals of Ordinal (von Neumann), and the Hartogs number of Hartogs: an ordinal that does not inject into a given set, namely the least ordinal that admits no injection into , equal to .
is the least ordinal that does not inject into , and it equals the set of order types of the well-orders of subsets of ; this is proved without choice (Hartogs: an ordinal that does not inject into a given set).
An ordinal is a transitive set on which is a strict well-order, , every element of an ordinal is an ordinal, , and for ordinals one has if and only if or (Ordinal (von Neumann), Basic closure properties of ordinals).
For ordinals exactly one of , , holds; every nonempty set of ordinals has an -least element; and means or (Trichotomy and well-ordering of the ordinals, Ordinal (von Neumann)).
If and then ; the bijection is explicit and no choice is used (The Schröder-Bernstein theorem).
means the existence of a bijection and the existence of an injection (Equinumerous sets, and , Injection, surjection, bijection).
Every natural number is an ordinal, is an ordinal, and every element of is a natural number; is transitive (The natural numbers (von Neumann), is the least limit ordinal).
If with then ; and for every (claims 3 and 4 of The pigeonhole principle on ).
Every well-order is order isomorphic to exactly one ordinal, its order type; an order isomorphism exists exactly when the two well-orders have the same order type (Every well-order has a unique order type).
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 between posets is a surjective order embedding, equivalently a bijection with (Order embedding and order isomorphism).
Verification
Transport of well-orders along an injection: let be an ordinal, let be injective, put and . Then is a well-order of , the map is an order isomorphism of onto , and . Indeed is a bijection onto ; is irreflexive because no ordinal satisfies ; is transitive as a relation and trichotomous because membership on is; and a nonempty has nonempty in , whose -least element gives an -least element of , since any with would have and contradict minimality. By construction if and only if , using injectivity of , so is an order isomorphism and [F8] gives .
For every ordinal : if and only if . First, , so an injection composed with a bijection gives an injection , and conversely an injection composed with a bijection gives an injection ; hence if and only if . Next if and only if : if or then by [F2], so the inclusion is an injection; conversely assume and suppose , so that by the trichotomy of [F3]. Then because is transitive, so by inclusion, and [F4] with gives . If then by [F2], so , while because and is transitive; [F4] then gives , contradicting [F7]. If instead , then is a natural number by [F6], and [F7] applied to gives , so , contrary to and [F2]; hence the supposition fails and .
The set equals : means or by [F3], that is by [F2], and by the von Neumann convention of [F6].
. One inclusion: if for well ordered by , then the order isomorphism of [F8] is injective with image , so . The other: if an ordinal satisfies , witnessed by an injection , then step 1.1 produces and a well-order of with , so belongs to the set displayed in [F1].
Therefore : step 2.1 writes and step 1.2 turns this into , which is by step 1.3. Since is the least ordinal not injecting into by [F1], the ordinal is that least ordinal, and of the subsets of are exactly the ordinals up to .
If then : the hypothesis gives as well, so the same computation yields . Thus the cardinality of a finite set determines its Hartogs number, which is the successor ordinal of its finite size ; nothing was selected at any stage, since the bijections and order types are given or unique by [F8], so no choice principle is used.
Depends on
- Hartogs: an ordinal that does not inject into a given set
- The pigeonhole principle on $\mathbb{N}$
- The Schröder-Bernstein theorem
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Ordinal (von Neumann)
- Basic closure properties of ordinals
- Trichotomy and well-ordering of the ordinals
- $\omega$ is the least limit ordinal
- The natural numbers $\mathbb{N}$ (von Neumann)
- Every well-order has a unique order type
- Injection, surjection, bijection
- Well-order and well-ordered set
- Order embedding and order isomorphism
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
40 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
- A. Marks, Set Theory (Berkeley lecture notes, 2026) (standard reference, not scraped)
- J. T. Moore, MATH 6870: Set Theory (Cornell lecture notes) (standard reference, not scraped)