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.
Basic bounding and dominating relations
Statement
In ZFC, with and the bounding and dominating numbers (Eventual domination and the numbers b and d) and the cofinality function (Cofinality , and regular and singular cardinals),
The right-hand bound is the observation that is a dominating family and has size ; the left-hand bounds are the countable pointwise-maximum argument; is the standard singular-cardinal contradiction; and partitions a dominating family of size along a cofinal sequence of length and diagonalizes against the non-dominating pieces.
Facts & Assumptions
Given: the Axiom of Choice (The Axiom of Choice).
means that for all but finitely many ; is -unbounded when no single lies -above every member, is -dominating when every lies -below some member, and are the least cardinalities of such families, the minima being attained. (Eventual domination and the numbers b and d)
; for a limit ordinal , is an infinite cardinal with , and there is a strictly increasing cofinal map . (Cofinality , and regular and singular cardinals, ; and ; for a limit ordinal the value is an infinite cardinal with , so it is regular; and every cofinal subset of has cardinality at least , a value that is attained, For every ordinal there is a least ordinal admitting a map with cofinal range, and that map may always be taken strictly increasing)
Under AC every set has a cardinality, cardinals are comparable, and every family of nonempty sets has a choice function. (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, Cardinal (initial ordinal) and cardinality, The Axiom of Choice)
and ; ; ; and . (Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations, Absorption: for cardinals with infinite and , , and when , Assuming the Axiom of Choice, , and Cantor's theorem in cardinal form: , The continuum is equinumerous with the power set of the naturals, The successor cardinal , the alephs , the beths , successor and limit cardinals, and the identifications and )
is a linear order on , so every nonempty finite subset of has a greatest element, and recursion on defines sequences with prescribed initial value and successor step. ( is a linear order on , Order on the natural numbers, The recursion theorem, The natural numbers (von Neumann))
Proof
Every countable family is bounded: given in , define as the greatest element of the finite nonempty set , which exists by [F5]; then for each and every one has , so . Hence no family of size at most is -unbounded, and since is a cardinal that is the least size of an unbounded family, , that is, .
No countable family is dominating: the empty family is not dominating, and any nonempty finite or countably infinite family can be listed as , repeating entries if necessary. Set , so for each one has whenever . Thus . An infinite cardinal is a limit ordinal, and [F2] gives .
: the map injects into , so by [F4] and is -dominating, since for every . Hence some dominating family has size at most , and .
: by [F2] , so suppose . By [F1] fix an unbounded family of size , and by [F2] fix a strictly increasing cofinal map from into . For each the subfamily has cardinality at most , so by the minimality in [F1] it is bounded: choose with for every (the choices are made by [F3]). The family has size at most , so it too is bounded; fix with for every . Every satisfies for some , because the map is cofinal, so and bounds the allegedly unbounded family, a contradiction. Hence and is regular.
: let be a dominating family of size by [F1], put , and fix a strictly increasing cofinal map from into by [F2]. For put ; then , the sets increase with , and . No is dominating, since is the least size of a dominating family, so by [F3] choose not dominated by any member of . The family is unbounded: if some satisfied for every , then by domination some satisfies , and for some , so contradicts the choice of . Therefore .
Steps 1.1, 1.2, 1.4 and 1.5 give , and step 1.3 adds ; together these are the displayed chain. This is the statement. ∎
Depends on
- Eventual domination and the numbers b and d
- Cofinality $\operatorname{cf}(\alpha)$, and regular and singular cardinals
- $\operatorname{cf}(\alpha) \le \alpha$; $\operatorname{cf}(0) = 0$ and $\operatorname{cf}(\alpha + 1) = 1$; for a limit ordinal $\lambda$ the value $\operatorname{cf}(\lambda)$ is an infinite cardinal with $\operatorname{cf}(\operatorname{cf}(\lambda)) = \operatorname{cf}(\lambda)$, so it is regular; and every cofinal subset of $\lambda$ has cardinality at least $\operatorname{cf}(\lambda)$, a value that is attained
- For every ordinal $\alpha$ there is a least ordinal $\beta$ admitting a map $\beta \to \alpha$ with cofinal range, and that map may always be taken strictly increasing
- The Axiom of Choice
- Cardinal (initial ordinal) and cardinality
- 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
- Cardinal sum $\kappa \oplus \lambda$, product $\kappa \otimes \lambda$ and exponentiation $\kappa^{\lambda}$, and why they are written apart from the ordinal operations
- Absorption: for cardinals $\kappa, \lambda$ with $\kappa$ infinite and $\lambda \le \kappa$, $\kappa \oplus \lambda = \kappa$, and $\kappa \otimes \lambda = \kappa$ when $\lambda \ne 0$
- Assuming the Axiom of Choice, $2^{\kappa} = \lvert \mathcal{P}(\kappa) \rvert$, and Cantor's theorem in cardinal form: $\kappa < 2^{\kappa}$
- The continuum is equinumerous with the power set of the naturals
- The successor cardinal $\kappa^{+}$, the alephs $\aleph_\alpha$, the beths $\beth_\alpha$, successor and limit cardinals, and the identifications $\aleph_0 = \omega$ and $\aleph_1 = \omega_1$
- $\le$ is a linear order on $\mathbb{N}$
- Order on the natural numbers
- The natural numbers $\mathbb{N}$ (von Neumann)
- The recursion theorem
Used by
Dependency tree · two levels
67 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
- J. D. Monk, Continuum cardinals, Theorem 1, printed p.1 (standard reference, not scraped)
- Tomek Bartoszynski, Invariants of Measure and Category, Section 2, printed pp.2-3 (standard reference, not scraped)