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.
Every set is countable in the intermediate extension
Statement
In , every set is at most countable in the convention of Finite, countably infinite, countable, uncountable. Equivalently, every nonempty set is the range of a map from ; the empty set is finite and is not asserted to be such a range.
Facts & Assumptions
Given: The intermediate Gitik extension .
Gitik's filter system and proper-class forcing: At each regular coordinate , conditions carry finite one-to-one sections from to , and every required successor set belongs to a uniform filter on .
The intermediate extension satisfies ZF minus Power Set plus Collection: has Collection/Replacement and a definable global well-order; hence it satisfies AC and , although Power Set is absent.
For every ordinal there is a least ordinal admitting a map with cofinal range, and that map may always be taken strictly increasing: In ZF, every ordinal has a strictly increasing cofinal map from the least ordinal witnessing its cofinality.
; 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 limit ordinal , is a regular infinite cardinal.
Transfinite induction: A property inherited at each ordinal from all smaller ordinals holds for every ordinal.
Countable unions of at most countable sets, assuming : Under , a countable union of at most countable sets is at most countable.
A nonempty set is at most countable iff it is a surjective image of : A nonempty set is at most countable iff it is a surjective image of .
Finite, countably infinite, countable, uncountable: The empty set is finite, hence at most countable, but there is no map from nonempty onto it.
Proof
Fix an infinite regular ground cardinal . The union is a well-defined one-to-one partial map : two generic conditions have a common refinement, whose section extends both finite sections. For each , support extension followed by finitely many legal successors gives a condition filling the th slot, so the corresponding class is dense and . For each , every successor set in the coordinate filter is unbounded—co-bounded in the small case and of cardinality by uniformity in the ultrafilter cases—so pruning it above and taking the next successor is dense. Hence is cofinal in . It is not claimed to equal .
Let be a nonzero limit ordinal and compute . By F3, choose in an increasing cofinal , and by F4 the ground cardinal is regular and infinite. If , already witnesses countable cofinality in . If , step 1.1 gives a cofinal , so has cofinal range in . A finite map cannot be cofinal in a nonzero limit ordinal, and therefore .
Apply transfinite induction to “ is at most countable in .” The zero ordinal is finite. If is countable, then is countable by adjoining one point to a finite or -enumeration. At a nonzero limit , choose the cofinal map from step 2.1. Every is countable by the induction hypothesis, and . The definable global well-order from F2 supplies , so F6 makes this union countable. F5 now gives that every ordinal of is at most countable.
Let . If , F8 makes it finite and countable. Otherwise the definable global well-order from F2 restricts to a well-order of ; Replacement supplies its ordinal order type and a bijection . Step 3.1 makes , and hence , at most countable. By F7 this is equivalent, in the nonempty case only, to a surjection .
Depends on
- The intermediate extension satisfies ZF minus Power Set plus Collection
- Gitik's filter system and proper-class forcing
- Cofinality $\operatorname{cf}(\alpha)$, and regular and singular cardinals
- 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
- $\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
- Finite, countably infinite, countable, uncountable
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
- Countable unions of at most countable sets, assuming $\mathrm{AC}_\omega$
- A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$
- Transfinite induction
Used by
Nothing in the library uses this result yet.
Dependency tree · two levels
44 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
- Schürz, Gitik's model, abstract and Sections 2 and 5, pages 3–7 and 12 (standard reference, not scraped)