Alphabeta Math
TheoremStatement: Literature-sourcedProof: AI-generatedSession-authored (Fable 5 assisted)precheck passaudited 2026-07-27
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 nonempty perfect subset of R\mathbb{R} is uncountable

Statement

Let PRP \subseteq \mathbb{R} be nonempty and perfect (Perfect subset of R\mathbb{R}: closed with no isolated points). Then PP is uncountable (Finite, countably infinite, countable, uncountable).

The selection is canonical, so that this proof spends no dependent choice. The textbook proof shrinks a neighbourhood at every stage by choosing a point of PP and then a radius, a choice made infinitely often and each time depending on the previous one: that is the axiom of dependent choice (The axiom of dependent choice: a relation in which every element is related to something admits an N\mathbb{N}-indexed chain), which is not available at this point in the reading order; only the axiom of countable choice is, and it does not licence a recursive selection. The construction below therefore fixes an enumeration ee of the rationals once (Q\mathbb{Q} is countably infinite, The rationals embed densely in the reals) and, at every stage, takes the interval with least-indexed rational endpoints meeting the requirements. The requirements are met by some rational-endpoint interval, which is what step 2.1 proves, and the least such index is determined by The well-ordering principle, so the whole recursion is a single application of The recursion theorem to a total map and no choice principle is used anywhere.

Facts & Assumptions

Given: A nonempty perfect set PRP \subseteq \mathbb{R}. Write QR\mathbb{Q}_{\mathbb{R}} for the image of Q\mathbb{Q} in R\mathbb{R} under qq^q \mapsto \hat q. A pair (p,q)QR×QR(p,q) \in \mathbb{Q}_{\mathbb{R}} \times \mathbb{Q}_{\mathbb{R}} is called good when p<qp < q and (p,q)P(p,q) \cap P \ne \varnothing, and GG denotes the set of good pairs.

[L1]

PP is perfect: PP is closed and every xPx \in P is a limit point of PP, so every punctured neighbourhood of xx meets PP (Perfect subset of R\mathbb{R}: closed with no isolated points, Limit point, isolated point, adherent point, derived set, and dense subset of R\mathbb{R}).

[L3]

Nε(x)=(xε,x+ε)N_\varepsilon(x) = (x - \varepsilon, x + \varepsilon); xNε(x)x \in N_\varepsilon(x); Nε(x)=Nε(x){x}N^{*}_\varepsilon(x) = N_\varepsilon(x) \setminus \{x\}; and yNε(x)y \in N_\varepsilon(x) with 0<δεyx0 < \delta \le \varepsilon - |y - x| gives Nδ(y)Nε(x)N_\delta(y) \subseteq N_\varepsilon(x) (The ε\varepsilon-neighbourhood and the punctured ε\varepsilon-neighbourhood of a point of R\mathbb{R}).

[L4]
[L5]

A nonempty at most countable set admits a surjection from N\mathbb{N}; uncountable means not at most countable (A nonempty set is at most countable iff it is a surjective image of N\mathbb{N}, Finite, countably infinite, countable, uncountable).

[L6]

QN\mathbb{Q} \approx \mathbb{N} (Q\mathbb{Q} is countably infinite); qq^q \mapsto \hat q is injective with image QR\mathbb{Q}_{\mathbb{R}} and strictly between any two reals lies an element of QR\mathbb{Q}_{\mathbb{R}} (The rationals embed densely in the reals); a composition of bijections is a bijection (Injection, surjection, bijection, Equinumerous sets, ABA \approx B and ABA \preceq B).

[L7]

Every nonempty subset of N\mathbb{N} has a least element (The well-ordering principle).

[L8]

Recursion: for a set YY, an element y0Yy_0 \in Y and a function T:YYT : Y \to Y there is h:NYh : \mathbb{N} \to Y with h(0)=y0h(0) = y_0 and h(σ(k))=T(h(k))h(\sigma(k)) = T(h(k)) (The recursion theorem).

[L9]

Nested interval property: for nonempty closed bounded intervals Ik=[ak,bk]I_k = [a_k,b_k] with Ik+1IkI_{k+1} \subseteq I_k, the intersection is nonempty, and it is a single point exactly when the lengths bkakb_k - a_k tend to 00 (A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to 00).

[L10]

Reciprocal Archimedean property: for every real ε>0\varepsilon > 0 there is a natural n1n \ge 1 with 1/n<ε1/n < \varepsilon (For every ε>0\varepsilon > 0 in a complete ordered field there is a natural n1n \ge 1 with 1/n<ε1/n < \varepsilon, Every complete ordered field is Archimedean); canonical naturals are positive and increasing, and reciprocation of positives reverses the order (Canonical naturals are positive and strictly increasing, Inverses of positives are positive, and reciprocation reverses order). These order-arithmetic facts are stated by their sources for the strict order only; the nonstrict forms used below follow by adjoining the equality case, in which the two sides coincide.

[L11]

Every nonempty finite set of reals has a minimum, which is one of its members (Every nonempty finite set of reals has a maximum and a minimum, Maximum and minimum of a set); 0<10 < 1, so 2:=1+1>02 := 1+1 > 0 and 0<d21<d0 < d \cdot 2^{-1} < d for d>0d > 0; adding a constant and multiplying by a positive preserve inequalities (The multiplicative identity is positive, Order is preserved by adding a constant and by adding inequalities, Sign rules for products and monotonicity of multiplication, Ordered field, Complete ordered field (least-upper-bound property)). These order-arithmetic facts are stated by their sources for the strict order only; the nonstrict forms used below follow by adjoining the equality case, in which the two sides coincide.

[L12]

Convergence of a sequence of reals to 00 is tested against rational ε>0\varepsilon > 0 (Limits and Cauchy sequences of reals, Sequences of reals: bounded, eventually, frequently, tails, subsequences).

[L13]

Absolute value: z0|z| \ge 0, and yxba|y - x| \le b - a whenever x,y[a,b]x, y \in [a,b] (Basic properties of the absolute value).

Proof

technique · contradiction
1.1

Suppose, for contradiction, that the nonempty perfect set PP is at most countable; by [L5] fix a surjection f:NPf : \mathbb{N} \to P.

assume-contraL5choose
1.2

By [L6] fix a bijection β:NQ\beta : \mathbb{N} \to \mathbb{Q} and put e:=ιβe := \iota \circ \beta with ι(q)=q^\iota(q) = \hat q, a bijection from N\mathbb{N} onto QR\mathbb{Q}_{\mathbb{R}}.

L6choose
1.3

Recall the terminology of the Given: a pair (p,q)(p,q) of elements of QR\mathbb{Q}_{\mathbb{R}} is good when p<qp < q and (p,q)P(p,q) \cap P \ne \varnothing, and GG is the set of good pairs.

givenconstruct
2.1

Refinement claim. For every good (p,q)(p,q), every xRx \in \mathbb{R} and every real η>0\eta > 0 there is a good (p,q)(p',q') with [p,q](p,q)[p',q'] \subseteq (p,q), x[p,q]x \notin [p',q'] and qp<ηq' - p' < \eta. To see it, fix y(p,q)Py \in (p,q) \cap P and, (p,q)(p,q) being open, a real ε>0\varepsilon > 0 with Nε(y)(p,q)N_\varepsilon(y) \subseteq (p,q); since yPy \in P is not isolated, [L1] gives zNε(y)Pz \in N^{*}_\varepsilon(y) \cap P, so zP(p,q)z \in P \cap (p,q) and zyz \ne y. At least one of y,zy, z differs from xx; let ww be yy if yxy \ne x and zz otherwise, so wPNε(y)w \in P \cap N_\varepsilon(y) and wxw \ne x. Put δ:=min{εwy, wx, η21}\delta := \min\{\, \varepsilon - |w - y|,\ |w - x|,\ \eta \cdot 2^{-1} \,\}, a positive real by [L11] since each entry is positive, and use [L6] to fix p,qQRp', q' \in \mathbb{Q}_{\mathbb{R}} with wδ<p<w<q<w+δw - \delta < p' < w < q' < w + \delta. Then [p,q]Nδ(w)Nε(y)(p,q)[p',q'] \subseteq N_\delta(w) \subseteq N_\varepsilon(y) \subseteq (p,q) by [L3], the pair (p,q)(p',q') is good because w(p,q)Pw \in (p',q') \cap P, the point xx lies outside Nδ(w)N_\delta(w) because xwδ|x - w| \ge \delta, and qp<2δηq' - p' < 2\delta \le \eta.

step 1.3L1L3L4L6L11choose
3.1

Successor rule. For (k,(p,q))N×G(k,(p,q)) \in \mathbb{N} \times G let mm be the least natural for which some natural nn makes (e(m),e(n))(e(m),e(n)) good with [e(m),e(n)](p,q)[e(m),e(n)] \subseteq (p,q), f(k)[e(m),e(n)]f(k) \notin [e(m),e(n)] and e(n)e(m)<1/(k+1)e(n) - e(m) < 1/(k+1), and let nn be the least natural with those properties for that mm; put T(k,(p,q)):=(σ(k),(e(m),e(n)))T(k,(p,q)) := (\sigma(k), (e(m),e(n))). The set of eligible mm is nonempty by step 2.1 applied with x=f(k)x = f(k) and η=1/(k+1)>0\eta = 1/(k+1) > 0, since ee is onto QR\mathbb{Q}_{\mathbb{R}}, so both minima exist by [L7] and T:N×GN×GT : \mathbb{N} \times G \to \mathbb{N} \times G is a total function defined without any selection.

step 2.1L6L7L10construct
4.1

The recursion. PP is nonempty, so fix y0Py_0 \in P and, by [L6], elements p0<y0<q0p_0 < y_0 < q_0 of QR\mathbb{Q}_{\mathbb{R}}; then (p0,q0)(p_0,q_0) is good. Apply [L8] with Y=N×GY = \mathbb{N} \times G, seed (0,(p0,q0))(0,(p_0,q_0)) and map TT to get h:NN×Gh : \mathbb{N} \to \mathbb{N} \times G with h(0)=(0,(p0,q0))h(0) = (0,(p_0,q_0)) and h(σ(k))=T(h(k))h(\sigma(k)) = T(h(k)); an induction on kk shows the first coordinate of h(k)h(k) is kk, so write h(k)=(k,(pk,qk))h(k) = (k,(p_k,q_k)) with every (pk,qk)(p_k,q_k) good.

step 1.3step 3.1L6L8construct
5.1

Writing Ik:=[pk,qk]I_k := [p_k,q_k] and k:=qkpk>0\ell_k := q_k - p_k > 0, the rule of step 3.1 gives, for every kNk \in \mathbb{N}: Ik+1(pk,qk)IkI_{k+1} \subseteq (p_k,q_k) \subseteq I_k, so the intervals are nested and nonempty; f(k)Ik+1f(k) \notin I_{k+1}; k+1<1/(k+1)\ell_{k+1} < 1/(k+1); and IkPI_k \cap P \ne \varnothing, because (pk,qk)P(p_k,q_k) \cap P \ne \varnothing.

step 3.1step 4.1L4
6.1

For every real ε>0\varepsilon > 0 there is k1k \ge 1 with k<ε\ell_k < \varepsilon, and moreover k0\ell_k \to 0: by step 5.1 one has j<1/j\ell_j < 1/j for every j1j \ge 1, since j=(j1)+1<1/((j1)+1)=1/j\ell_j = \ell_{(j-1)+1} < 1/((j-1)+1) = 1/j; given ε>0\varepsilon > 0, [L10] supplies a natural n1n \ge 1 with 1/n<ε1/n < \varepsilon, and then every knk \ge n satisfies k1k \ge 1 and k0=k<1/k1/n<ε|\ell_k - 0| = \ell_k < 1/k \le 1/n < \varepsilon by [L10] and [L13], which is both assertions, the second by [L12] since a rational ε>0\varepsilon > 0 is in particular a real one.

step 5.1L10L12L13
7.1

By [L9] the nested family (Ik)(I_k) of nonempty closed bounded intervals has an intersection that is a single point, since its lengths tend to 00 by step 6.1; write {x}\{x\} for it, so xIkx \in I_k for every kk.

step 5.1step 6.1L9
8.1

xPx \in P: let ε>0\varepsilon > 0 be real and use step 6.1 to fix k1k \ge 1 with k<ε\ell_k < \varepsilon; by step 5.1 there is yIkPy \in I_k \cap P, and xIkx \in I_k by step 7.1, so yxk<ε|y - x| \le \ell_k < \varepsilon by [L13] and yNε(x)Py \in N_\varepsilon(x) \cap P. Every neighbourhood of xx therefore meets PP, so xP=Px \in \overline{P} = P by [L1] and [L2].

step 5.1step 6.1step 7.1L1L2L3L13
9.1

For every kNk \in \mathbb{N} one has xIk+1x \in I_{k+1} by step 7.1 while f(k)Ik+1f(k) \notin I_{k+1} by step 5.1, so xf(k)x \ne f(k); thus the element xx of PP found in step 8.1 is not a value of ff, contradicting the surjectivity of the ff fixed in step 1.1. The assumption is therefore untenable: a nonempty perfect subset of R\mathbb{R} is not at most countable, that is, it is uncountable.

step 1.1step 5.1step 7.1step 8.1L5discharge-contradiction

Remarks

Depends on

Used by

Dependency tree · next 3 levels

Direct dependencies and their dependencies through the next three levels: 124 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