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 is uncountable
Statement
Let be nonempty and perfect (Perfect subset of : closed with no isolated points). Then 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 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 -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 of the rationals once ( 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 . Write for the image of in under . A pair is called good when and , and denotes the set of good pairs.
is perfect: is closed and every is a limit point of , so every punctured neighbourhood of meets (Perfect subset of : closed with no isolated points, Limit point, isolated point, adherent point, derived set, and dense subset of ).
is the set of points every neighbourhood of which meets , and is closed exactly when (The closure equals the set together with its limit points, equals the set of points every neighbourhood of which meets it, and is the smallest closed superset; a set is closed iff it contains its limit points, Open subset of (every point has a neighbourhood inside it), closed subset (complement open), and clopen).
; ; ; and with gives (The -neighbourhood and the punctured -neighbourhood of a point of ).
Intervals: is an open set and is a closed bounded interval, nonempty when (Intervals of : the nine order-convex forms, nondegeneracy, and length, Open subset of (every point has a neighbourhood inside it), closed subset (complement open), and clopen).
A nonempty at most countable set admits a surjection from ; uncountable means not at most countable (A nonempty set is at most countable iff it is a surjective image of , Finite, countably infinite, countable, uncountable).
( is countably infinite); is injective with image and strictly between any two reals lies an element of (The rationals embed densely in the reals); a composition of bijections is a bijection (Injection, surjection, bijection, Equinumerous sets, and ).
Every nonempty subset of has a least element (The well-ordering principle).
Recursion: for a set , an element and a function there is with and (The recursion theorem).
Nested interval property: for nonempty closed bounded intervals with , the intersection is nonempty, and it is a single point exactly when the lengths tend to (A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to ).
Reciprocal Archimedean property: for every real there is a natural with (For every in a complete ordered field there is a natural with , 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.
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); , so and for ; 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.
Convergence of a sequence of reals to is tested against rational (Limits and Cauchy sequences of reals, Sequences of reals: bounded, eventually, frequently, tails, subsequences).
Absolute value: , and whenever (Basic properties of the absolute value).
Proof
Suppose, for contradiction, that the nonempty perfect set is at most countable; by [L5] fix a surjection .
By [L6] fix a bijection and put with , a bijection from onto .
Recall the terminology of the Given: a pair of elements of is good when and , and is the set of good pairs.
Refinement claim. For every good , every and every real there is a good with , and . To see it, fix and, being open, a real with ; since is not isolated, [L1] gives , so and . At least one of differs from ; let be if and otherwise, so and . Put , a positive real by [L11] since each entry is positive, and use [L6] to fix with . Then by [L3], the pair is good because , the point lies outside because , and .
Successor rule. For let be the least natural for which some natural makes good with , and , and let be the least natural with those properties for that ; put . The set of eligible is nonempty by step 2.1 applied with and , since is onto , so both minima exist by [L7] and is a total function defined without any selection.
The recursion. is nonempty, so fix and, by [L6], elements of ; then is good. Apply [L8] with , seed and map to get with and ; an induction on shows the first coordinate of is , so write with every good.
Writing and , the rule of step 3.1 gives, for every : , so the intervals are nested and nonempty; ; ; and , because .
For every real there is with , and moreover : by step 5.1 one has for every , since ; given , [L10] supplies a natural with , and then every satisfies and by [L10] and [L13], which is both assertions, the second by [L12] since a rational is in particular a real one.
By [L9] the nested family of nonempty closed bounded intervals has an intersection that is a single point, since its lengths tend to by step 6.1; write for it, so for every .
: let be real and use step 6.1 to fix with ; by step 5.1 there is , and by step 7.1, so by [L13] and . Every neighbourhood of therefore meets , so by [L1] and [L2].
For every one has by step 7.1 while by step 5.1, so ; thus the element of found in step 8.1 is not a value of , contradicting the surjectivity of the fixed in step 1.1. The assumption is therefore untenable: a nonempty perfect subset of is not at most countable, that is, it is uncountable.
Remarks
-
Which hypothesis does what. Closedness of is used exactly once, at the step that puts the limit point back into ; without it the construction still produces a point, but that point may lie outside and the contradiction evaporates. Having no isolated points is used exactly once, in the refinement claim, to produce a second point of inside a neighbourhood, which is what allows the excluded point to be dodged. Nonemptiness is used to seed the recursion, and it cannot be dropped: is perfect and countable (Perfect subset of : closed with no isolated points).
-
Why rational endpoints. They are what make the construction canonical. The requirement "some good rational-endpoint interval inside misses and is short" is a property of a pair of natural numbers, so it can be minimised by The well-ordering principle; the same requirement stated for arbitrary real endpoints comes with no canonical least witness, and picking one would be a choice made afresh at every stage. This is the same device that keeps Every subset of an at most countable set is at most countable and A nonempty set is at most countable iff it is a surjective image of choice free, transplanted from subsets of to intervals.
-
The shrinking condition is and not . Sequences and recursions here are indexed from (Sequences of reals: bounded, eventually, frequently, tails, subsequences), so the bound available at stage has to be positive at ; is undefined there. The consequence, for , is what step 6.1 uses, and it says nothing about , which is not needed.
-
The result is sharp in both directions. A nondegenerate closed interval is perfect and uncountable (Every nondegenerate closed interval is perfect, giving a second proof that it is uncountable ↗), and deleting the no-isolated-points clause loses the conclusion: a closed set with an isolated point need not be perfect ( is closed, has an isolated point, and is not perfect ↗) and may be countable, as is ( is compact while is not closed ↗). Applied to a nondegenerate closed interval, which Every nondegenerate closed interval is perfect, giving a second proof that it is uncountable ↗ shows to be perfect, the theorem reproves the uncountability of intervals (Every nondegenerate interval of is uncountable) by a different route; the two proofs share nothing but the completeness of , which Every nondegenerate interval of is uncountable spends as a supremum and the argument above spends through A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to .
Depends on
- Perfect subset of $\mathbb{R}$: closed with no isolated points
- A nested sequence of nonempty closed bounded intervals has nonempty intersection, and the intersection is a single point exactly when the lengths tend to $0$
- Finite, countably infinite, countable, uncountable
- A nonempty set is at most countable iff it is a surjective image of $\mathbb{N}$
- The recursion theorem
- Intervals of $\mathbb{R}$: the nine order-convex forms, nondegeneracy, and length
- The $\varepsilon$-neighbourhood and the punctured $\varepsilon$-neighbourhood of a point of $\mathbb{R}$
- The closure equals the set together with its limit points, equals the set of points every neighbourhood of which meets it, and is the smallest closed superset; a set is closed iff it contains its limit points
- Open subset of $\mathbb{R}$ (every point has a neighbourhood inside it), closed subset (complement open), and clopen
- Limit point, isolated point, adherent point, derived set, and dense subset of $\mathbb{R}$
- The rationals embed densely in the reals
- $\mathbb{Q}$ is countably infinite
- The well-ordering principle
- For every $\varepsilon > 0$ in a complete ordered field there is a natural $n \ge 1$ with $1/n < \varepsilon$
- Every complete ordered field is Archimedean
- Injection, surjection, bijection
- Equinumerous sets, $A \approx B$ and $A \preceq B$
- Limits and Cauchy sequences of reals
- Sequences of reals: bounded, eventually, frequently, tails, subsequences
- Canonical naturals are positive and strictly increasing
- Inverses of positives are positive, and reciprocation reverses order
- Basic properties of the absolute value
- Every nonempty finite set of reals has a maximum and a minimum
- Maximum and minimum of a set
- Complete ordered field (least-upper-bound property)
- Ordered field
- The multiplicative identity is positive
- Order is preserved by adding a constant and by adding inequalities
- Sign rules for products and monotonicity of multiplication
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
- Perfect set (Wikipedia) (standard reference, not scraped)
- Cantor-Bendixson theorem (Wikipedia) (standard reference, not scraped)
- W. Rudin, Principles of Mathematical Analysis, 3rd ed., Ch. 2 (Thm 2.43) (standard reference, not scraped)
- Nested intervals (Wikipedia) (standard reference, not scraped)
- A. W. Miller, Tameness notes (standard reference, not scraped)