Countable sets¶
Level: 201 → 301 · for anyone who has met a limit
One line: Any set that can be written as a list has measure zero — even the rational numbers, which crowd into every interval of the line — because the n-th member can be given an interval of length ε/2ⁿ, and those lengths add up to ε.
The rationals are everywhere¶
Section 2 of the program looks for a fraction between two numbers that are close together. Between 0.41 and 0.42 there is 5/12; between 0.414213 and 0.414214 there is 408/985. No window is too narrow: shrink it as far as you like and a fraction with a larger denominator turns up inside. That is what it means for the rationals to be dense in the line.
If anything ought to have positive length, it is a set found inside every interval there is. It does not.
(Several of the fractions section 2 finds — 5/12, 29/70, 169/408, 408/985 — are the best rational approximations to √2 − 1 there are, its continued-fraction convergents. Every window was placed around √2 − 1, which comes back in section 5.)
What the program prints¶
Verified output of countable_sets.py — regenerated by tools/run_examples.py, never hand-typed.
1. EVERY RATIONAL IN [0,1] GETS A PLACE IN LINE
Order them by denominator, and skip anything not in lowest terms:
1: 0 2: 1 3: 1/2 4: 1/3 5: 2/3
6: 1/4 7: 3/4 8: 1/5 9: 2/5 10: 3/5
11: 4/5 12: 1/6 13: 5/6 14: 1/7 15: 2/7
16: 3/7 17: 4/7 18: 5/7 19: 6/7 20: 1/8
5/12 is number 45.
99/100 is number 3,045.
Every rational in [0,1] has a finite place in this list. A set that
can be listed like this is COUNTABLE.
2. AND THEY ARE EVERYWHERE
Between any two different numbers sits a rational. The simplest one
in some ever-narrower windows:
between 0.41 and 0.42 5/12 = 0.416666667
between 0.414 and 0.415 17/41 = 0.414634146
between 0.4142 and 0.4143 29/70 = 0.414285714
between 0.41421 and 0.41422 169/408 = 0.414215686
between 0.414213 and 0.414214 408/985 = 0.414213198
No window is too narrow to hold one. That is what DENSE means.
3. GIVE THE n-TH RATIONAL AN INTERVAL OF LENGTH (1/10) / 2^n
n rational length interval around it
1 0 1/20 (-1/40, 1/40)
2 1 1/40 (79/80, 81/80)
3 1/2 1/80 (79/160, 81/160)
4 1/3 1/160 (317/960, 323/960)
5 2/3 1/320 (1277/1920, 1283/1920)
6 1/4 1/640 (319/1280, 321/1280)
7 3/4 1/1280 (1919/2560, 1921/2560)
8 1/5 1/2560 (1023/5120, 205/1024)
Every rational sits inside its own interval, so every one is covered.
4. ADD UP THE LENGTHS
1/20 + 1/40 + 1/80 + ... halves each time. After N intervals the
total is exactly 1/10 - 1/(10 x 2^N):
N below 1/10 by
10 9.766e-05
100 7.889e-32
1000 9.333e-303
The total creeps toward 1/10 and never passes it, so the whole
infinite cover has total length at most 1/10. Every rational is
covered, and 9/10 of [0,1] is not. Swap 1/10 for any budget at all
and the same list works, so the rationals have measure zero.
5. SO WHAT IS NOT COVERED?
At least 9/10 of [0,1] -- all of it irrational. One such number is
sqrt(2) - 1 = 0.41421356... Checked exactly against the first 5,000:
intervals containing it: 0
closest call: interval 3, around 1/2
distance from 1/2: 0.08578644
half that interval: 0.00625000
misses by a factor of: 13.7
That check stops at 5,000. The page proves the miss for all of them.
6. WHY 'AN INFINITE LIST', NOT JUST 'FINITELY MANY'
Stop after the first 1,000 intervals, and look at the next rationals:
number 1,001: 56/57 NOT covered
number 1,002: 1/58 covered anyway, by interval 1 around 0
number 1,003: 3/58 NOT covered
number 1,004: 5/58 NOT covered
Every finite stopping point leaves rationals out. Only the whole
infinite list covers them all -- and the page shows why no finite
cover of the rationals in [0,1] can total less than 1.
Step 1: put them in a list¶
Section 1 lists the rationals in [0, 1] by denominator: 0 and 1, then 1/2, then 1/3 and 2/3, then 1/4 and 3/4, skipping any fraction not in lowest terms so nothing appears twice. Every rational gets a finite position — 5/12 is number 45, 99/100 is number 3,045. A set that can be written as a list like this, with every member somewhere in it, is countable.
The list jumps all over [0, 1]. It is not in increasing order and does not need to be; it only needs every member to arrive eventually.
Step 2: give the n-th one an interval of length ε/2ⁿ¶
Take ε = 1/10. The first rational gets an interval of length 1/20, the second 1/40, the third 1/80, each half the one before (section 3). Every rational sits in the middle of its own interval, so every rational is covered.
Now add up the lengths:
After N intervals the total is exactly 1/10 − 1/(10 × 2ᴺ); section 4 checks that with exact fractions up to N = 1000. The series never passes 1/10, so the whole infinite cover has total length at most 1/10. Where intervals overlap, and some do, the length they actually cover is even less.
Nothing depended on 1/10. The same list with ε/2ⁿ meets any budget, so the rationals have measure zero. And the argument never used anything about the rationals except that they can be listed. Every countable set has measure zero: the integers, the square roots of whole numbers, every number that can be written down as a finite string of symbols.
So what is left over?¶
At most 1/10 of [0, 1] is covered, so at least 9/10 is not — and everything uncovered is irrational. It sounds impossible. The rationals are everywhere, each one wrapped in an interval of its own, and still most of the line slips between them.
Section 5 picks one number that slips through, √2 − 1 = 0.41421356…, and checks it exactly against the first 5,000 intervals, using squares instead of square roots so that no rounding is involved. None contains it. The nearest miss is the interval around 1/2, which it misses by a factor of 13.7.
A program can check 5,000 intervals. This is why √2 − 1 misses every one, forever:
Let p/q be a rational in [0, 1] in lowest terms, and write P = p + q, so that p/q + 1 = P/q. Because √2 is irrational, 2q² − P² is a whole number other than 0, so it is at least 1 in size. Then
|(√2 − 1) − p/q| = |√2 − P/q| = |2q² − P²| / (q² (√2 + P/q)) > 1 / (3.5 q²),
because P/q ≤ 2 keeps √2 + P/q below 3.5.
Meanwhile p/q sits at a position n ≥ q in the list, because a fraction for every smaller denominator comes before it. So its interval reaches (1/10) / 2ⁿ⁺¹ ≤ 1 / (10 × 2^(q+1)) either side of p/q. And 10 × 2^(q+1) ≥ 3.5 q² for every q ≥ 1.
So √2 − 1 is always farther from p/q than the interval reaches. It is never inside.
Why the definition says a list, not finitely many¶
Stop after any finite number of intervals and rationals fall out. Section 6 stops after 1,000. Number 1,001, which is 56/57, is not covered by any of the first thousand; number 1,002, which is 1/58, happens to sit inside the very first interval, the one around 0. Every finite stopping point leaves some out.
That is not bad luck: no finite cover can work. Suppose finitely many closed intervals contained every rational in [0, 1]. Their union is a closed set, and a closed set holding every rational in [0, 1] holds every point of [0, 1] too, because each real number is a limit of rationals. So the intervals cover all of [0, 1], and their lengths total at least 1.
So measured with finitely many intervals, the rationals in [0, 1] are as big as [0, 1] itself; measured with a list, they are nothing. Covering with finitely many intervals is the older idea of Jordan content. Allowing an infinite list is the step from Jordan content to Lebesgue measure, and it is what lets a dense set weigh nothing.
Run it yourself¶
From the root of your clone of this repository:
See also¶
- What measure zero means — the definition this page applies
- The Cantor set — countable is enough for measure zero, but it is not necessary
- Probability zero — what this page means for a random number: almost surely irrational
- Countable set ↗ — Wikipedia