Alphabeta Math
ExampleConstruction: Literature-sourcedVerification: AI-adaptedPipeline-generatedprecheck passjudge pass (gpt-6.1-sol)
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 n-element set is n+

Example

Let A≈n for some natural number n (Equinumerous sets, A≈B and A⪯B, The natural numbers N (von Neumann)). Then the Hartogs number ℵ(A) of Hartogs: an ordinal that does not inject into a given set equals n+=n∪{n}={0,1,…,n}: the set of order types of well-orders of subsets of A is exactly the set of ordinals α with α≤n, and n+ is the least ordinal that does not inject into A. In particular the cardinality of A determines its Hartogs number, and no choice principle is used.

Facts & Assumptions

Given: A set A with a bijection A≈n onto a natural number n, the ordinals of Ordinal (von Neumann), and the Hartogs number ℵ(A) of Hartogs: an ordinal that does not inject into a given set, namely the least ordinal that admits no injection into A, equal to {ot(S,R):S⊆A, R well-orders S}.

[F1]

ℵ(A) is the least ordinal that does not inject into A, and it equals the set of order types of the well-orders of subsets of A; this is proved without choice (Hartogs: an ordinal that does not inject into a given set).

[F2]

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

[F3]

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

[F4]

If A⪯B and B⪯A then A≈B; the bijection is explicit and no choice is used (The Schröder-Bernstein theorem).

[F5]

≈ means the existence of a bijection and ⪯ the existence of an injection (Equinumerous sets, A≈B and A⪯B, Injection, surjection, bijection).

[F6]

Every natural number is an ordinal, ω=N is an ordinal, and every element of ω is a natural number; N is transitive (The natural numbers N (von Neumann), ω is the least limit ordinal).

[F7]

If n≈m with n,m∈N then n=m; and N≉n for every n∈N (claims 3 and 4 of The pigeonhole principle on N).

[F8]

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

[F9]

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 f with x≤y  ⟺  f(x)≤f(y) (Order embedding and order isomorphism).

Verification

technique · direct
1.1F2F5F8F9

Transport of well-orders along an injection: let α be an ordinal, let j:α→A be injective, put S=j[α] and R={(j(ξ),j(η)):ξ,η∈α, ξ∈η}. Then R is a well-order of S, the map j is an order isomorphism of (α,∈) onto (S,R), and ot(S,R)=α. Indeed j is a bijection onto S; R is irreflexive because no ordinal satisfies ξ∈ξ; R is transitive as a relation and trichotomous because membership on α is; and a nonempty T⊆S has j−1[T] nonempty in α, whose ∈-least element ξ gives an R-least element j(ξ) of T, since any j(η)∈T with j(η)Rj(ξ) would have η∈ξ and contradict minimality. By construction j(ξ)Rj(η) if and only if ξ∈η, using injectivity of j, so j is an order isomorphism and [F8] gives ot(S,R)=α.

1.2F2F3F4F5F6F7

For every ordinal α: α⪯A if and only if α≤n. First, A≈n, so an injection α→A composed with a bijection A→n gives an injection α→n, and conversely an injection α→n composed with a bijection n→A gives an injection α→A; hence α⪯A if and only if α⪯n. Next α⪯n if and only if α≤n: if α∈n or α=n then α⊆n by [F2], so the inclusion is an injection; conversely assume α⪯n and suppose α≰n, so that n∈α by the trichotomy of [F3]. Then n⊆α because α is transitive, so n⪯α by inclusion, and [F4] with α⪯n gives n≈α. If ω≤α then ω⊆α by [F2], so ω⪯α⪯n, while n⪯ω because n∈ω and ω is transitive; [F4] then gives ω≈n, contradicting [F7]. If instead α∈ω, then α is a natural number by [F6], and [F7] applied to n≈α gives α=n, so α≤n, contrary to n∈α and [F2]; hence the supposition fails and α≤n.

1.3F2F3F6

The set {α:α≤n} equals n+: α≤n means α∈n or α=n by [F3], that is α∈n∪{n}=n+ by [F2], and n+=n∪{n}={0,1,…,n} by the von Neumann convention of [F6].

2.1step 1.1F1F5F8

ℵ(A)={α:α is an ordinal and α⪯A}. One inclusion: if α=ot(S,R) for S⊆A well ordered by R, then the order isomorphism α→(S,R) of [F8] is injective with image S⊆A, so α⪯A. The other: if an ordinal α satisfies α⪯A, witnessed by an injection j, then step 1.1 produces S=j[α]⊆A and a well-order R of S with ot(S,R)=α, so α belongs to the set displayed in [F1].

3.1step 2.1step 1.2step 1.3F1

Therefore ℵ(A)=n+: step 2.1 writes ℵ(A)={α:α is an ordinal and α⪯A} and step 1.2 turns this into {α:α≤n}, which is n+ by step 1.3. Since ℵ(A) is the least ordinal not injecting into A by [F1], the ordinal n+ is that least ordinal, and ot of the subsets of A are exactly the ordinals up to n.

4.1step 3.1F1F8F9∎

If B≈A then ℵ(B)=ℵ(A): the hypothesis gives B≈n as well, so the same computation yields ℵ(B)=n+. Thus the cardinality of a finite set determines its Hartogs number, which is the successor ordinal n+ of its finite size n; 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

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