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.
in ZF, by the Cantor set for one injection and by the cuts for the other; so under the Axiom of Choice
Example
Write for the set of functions , the here being the von Neumann natural number, and for the power set of (The natural numbers (von Neumann)). Then:
(a) In ZF, with no choice principle:
(Equinumerous sets, and , The real numbers).
(b) Assuming the Axiom of Choice (The Axiom of Choice):
(Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations, The successor cardinal , the alephs , the beths , successor and limit cardinals, and the identifications and ).
The two injections are the classical ones and neither uses a binary expansion. One direction is the Cantor set: The Cantor set is exactly the set of with every , and this gives a bijection with already supplies a bijection from the sequences with values in onto the Cantor set (The Cantor middle-thirds set as the intersection of the sets obtained by removing open middle thirds). The other is the cut map , injective because is dense in (ℚ is dense in every Archimedean ordered field), and is a copy of because is countable ( is countably infinite). The Schröder-Bernstein theorem closes the loop, and it is choice free, which is what makes clause (a) a theorem of ZF.
Facts & Assumptions
Given: with its order and the canonical embedding ; the Axiom of Choice is assumed only in clause (b).
The order of Order on the reals makes (The real numbers) a totally ordered field (The reals form a totally ordered field) with the least-upper-bound property (The Cauchy-sequence reals have the least-upper-bound property), hence a complete ordered field (Complete ordered field (least-upper-bound property)) and hence Archimedean (Every complete ordered field is Archimedean); and is the unique order-preserving field embedding (The unique embedding of ℚ into an ordered field).
For in an Archimedean ordered field there is a rational with (ℚ is dense in every Archimedean ordered field).
There is a bijection from the set of sequences with values in onto the Cantor set (claim 3 of The Cantor set is exactly the set of with every , and this gives a bijection with , The Cantor middle-thirds set as the intersection of the sets obtained by removing open middle thirds); a sequence of reals is a function (Sequences of reals: bounded, eventually, frequently, tails, subsequences).
If and then (The Schröder-Bernstein theorem).
For a well-orderable set , is the least ordinal equinumerous with and equinumerous sets receive the same one (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); assuming the Axiom of Choice every set has one (The well-ordering theorem).
Assuming the Axiom of Choice, , and (Assuming the Axiom of Choice, , and Cantor's theorem in cardinal form: , Cardinal sum , product and exponentiation , and why they are written apart from the ordinal operations, The successor cardinal , the alephs , the beths , successor and limit cardinals, and the identifications and ).
A subset inclusion is an injection, a composition of injections is an injection, and a map with a two-sided inverse is a bijection (Injection, surjection, bijection).
Verification
The two-element sets and are equinumerous, since in a field, so by [L5].
The set is exactly the set of sequences with values in of [L3], so it is in bijection with , and composing with the inclusion gives an injection .
The map is an injection : for the order is total by [L1], so we may assume , and [L2] supplies a rational with , whence and , so .
by [L4] and [L5].
: the map sending to its characteristic function has the two-sided inverse .
Chaining steps 1.1, 1.2 gives , and chaining steps 1.3, 1.4, 1.5 gives ; so [L6] yields , and with step 1.5 also , which is clause (a) and uses no choice principle.
Assuming the Axiom of Choice, all three sets have cardinalities by [L7], equal by step 2.1, and by [L8] and [L7]; so , which is clause (b).
Remarks
Why binary expansions are avoided. The textbook proof identifies a real in with the set of positions where its binary expansion has a , and then has to deal with the reals having two expansions. Neither injection above meets that difficulty: the Cantor set map is already published as a bijection, and the cut map needs only density. The cost is that the two injections go in opposite directions and The Schröder-Bernstein theorem is required to combine them, which is free, since that theorem is choice free.
Which half needs the Axiom of Choice, and why. Clause (a) is an equinumerosity statement and is a theorem of ZF. Clause (b) writes and as cardinals, that is as ordinals, and in ZF alone need not be well-orderable, so those symbols need not denote anything. The hypothesis buys the notation, not the mathematics.
What is still not decided. Nothing here says which aleph is. The one constraint proved in this development is that its cofinality is uncountable (Assuming the Axiom of Choice: for every infinite cardinal , and ; in particular ), and the question of whether it is is the continuum hypothesis (What each result on this page costs in choice, and where the continuum escapes what ZFC can decide).
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 Cantor middle-thirds set as the intersection of the sets $C_n$ obtained by removing open middle thirds
- $\mathbb{Q}$ is countably infinite
- ℚ is dense in every Archimedean ordered field
- The unique embedding of ℚ into an ordered field
- Every complete ordered field is Archimedean
- Complete ordered field (least-upper-bound property)
- The real numbers
- Order on the reals
- Sequences of reals: bounded, eventually, frequently, tails, subsequences
- The Schröder-Bernstein theorem
- 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
- 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
- Assuming the Axiom of Choice, $2^{\kappa} = \lvert \mathcal{P}(\kappa) \rvert$, and Cantor's theorem in cardinal form: $\kappa < 2^{\kappa}$
- 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$
- Cardinal (initial ordinal) and cardinality
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Injection, surjection, bijection
- The Axiom of Choice
- The well-ordering theorem
- The natural numbers $\mathbb{N}$ (von Neumann)
- Finite, countably infinite, countable, uncountable
- The reals form a totally ordered field
- The Cauchy-sequence reals have the least-upper-bound property
Used by
- Assuming the Axiom of Choice: ℵ₀^ℵ₀ = 2^ℵ₀ and | ℝ^ℝ | = 2^2^ℵ₀, computed from the exponent laws and Hessenberg Example
- Assuming the Axiom of Choice: ℶ₀ = ℵ₀, ℶ₁ = 2^ℵ₀ = | ℝ |, ℶ₂ = | P(ℝ) |, and ℶ_ω has cofinality ℵ₀ Example
- For the lower-limit line, χ=d=L=c=ℵ₀ and w=2^ℵ₀ under choice Example
- ℵ₁ ≤ 2^ℵ₀ under the Axiom of Choice, because 2^ℵ₀ is a cardinal strictly above ℵ₀ and ℵ₁ is the least such; so ω₁ injects into ℝ Example
Dependency tree · next 3 levels
Direct dependencies and their dependencies through the next three levels: 188 results over 36 levels. An arrow runs from a result to what uses it, and this result sits at the bottom with a heavier outline. Click the chart to enlarge it.
Sources
- P. Koellner, Set Theory: The Independence Phenomenon, Exercise 3.8 (standard reference, not scraped)
- Cardinality of the continuum (Wikipedia) (standard reference, not scraped)
- Cantor set (Wikipedia) (standard reference, not scraped)