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 continuum is equinumerous with the power set of the naturals
Statement
In ZF, without any choice principle, there are bijections where and . Assuming the Axiom of Choice, these bijections give the cardinal equality
Facts & Assumptions
Given: The reals and naturals under the library's ZF conventions. Choice is assumed only for the cardinal-equality clause.
Binary sequences are in bijection with the Cantor set (The Cantor set is exactly the set of with every , and this gives a bijection with ).
The reals are a complete ordered field (The reals form a totally ordered field, The Cauchy-sequence reals have the least-upper-bound property), hence Archimedean (Every complete ordered field is Archimedean). Therefore a rational lies strictly between any two distinct reals (ℚ is dense in every Archimedean ordered field), and without Choice ( is countably infinite).
A bijection induces a bijection (Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals the sets and carry explicit well-orders, so their cardinalities exist in ZF). Opposite injections between two sets give a bijection (The Schröder-Bernstein theorem).
Under Choice, every set is well-orderable and has an initial-ordinal cardinality; equinumerous sets have equal cardinalities (The Axiom of Choice, The well-ordering theorem, 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). Also (The successor cardinal , the alephs , the beths , successor and limit cardinals, and the identifications and ) and (Assuming the Axiom of Choice, , and Cantor's theorem in cardinal form: ).
Proof
The inclusion composed with [L1] gives an injection . This construction uses no choice.
For each real , put . If , choose a rational with by [L2]. Then , so injects into . A fixed bijection and [L3] give an injection . No family of choices is made: only the existence of one separating rational is used to prove injectivity.
Sending to its characteristic function is a bijection , with inverse . Combine it with steps 1.1 and 1.2. There are injections in both directions between and , so Schröder–Bernstein [L3] gives in ZF.
Now assume Choice. By [L4], the equinumerous sets in step 2.1 have equal cardinalities, while and . Hence .
Source notes
The proof is adapted from the published Foundations B example on continuum cardinality, using its Cantor-set and rational-cut injections. Its listed external references were not independently read for this draft; the mathematical argument above is checked against the exact published supplier statements.
Depends on
- The Cantor set is exactly the set of $\sum_{k \ge 1} a_k 3^{-k}$ with every $a_k \in \{0,2\}$, and this gives a bijection with $\{0,1\}^{\mathbb{N}}$
- The reals form a totally ordered field
- The Cauchy-sequence reals have the least-upper-bound property
- Every complete ordered field is Archimedean
- ℚ is dense in every Archimedean ordered field
- $\mathbb{Q}$ is countably infinite
- Disjoint union, cartesian product, function space and power set respect equinumerosity, and for ordinals $\alpha, \beta$ the sets $\alpha \sqcup \beta$ and $\alpha \times \beta$ carry explicit well-orders, so their cardinalities exist in ZF
- The Schröder-Bernstein theorem
- Assuming the Axiom of Choice, $2^{\kappa} = \lvert \mathcal{P}(\kappa) \rvert$, and Cantor's theorem in cardinal form: $\kappa < 2^{\kappa}$
- The well-ordering theorem
- 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
- 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$
- The Axiom of Choice
Used by
- Almost inclusion, pseudointersections and towers Definition
- The splitting and reaping numbers Definition
- For the lower-limit line, χ=d=L=c=ℵ₀ and w=2^ℵ₀ under choice Example
- A tower of size at most the continuum exists Lemma
- Basic bounding and dominating relations Lemma
- Elementary bounds on ideal cardinal invariants Lemma
Dependency tree · two levels
89 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.