Countable and Uncountable Sets
Compare infinite sets by pairing their elements. The rationals pair with the naturals; the reals do not, and the diagonal argument shows why.
What a learner can do afterwards
- Build an explicit bijection showing a set is countable
- Present the diagonal argument for the reals
- Explain why a proper subset can pair with the whole set only for infinite sets
1 · Read
A set is countable when its members can be queued first, second, third and on. Integers queue in a zigzag through positives and negatives. The doubling rule n to 2n pairs every natural number with an even one: 7 pairs with 14. Rationals queue by snaking through a fraction grid and skipping repeats. A full hotel absorbs a newcomer by shifting every guest from room n to room n plus 1, so the guest in room 5 moves to room 6 and room 1 falls free.
Suppose someone lists every real number between 0 and 1. Build a new number that dodges each entry at one digit: differ from entry n in digit n. With r1 equal to 0.141, r2 equal to 0.718 and r3 equal to 0.502, add 1 to each diagonal digit to open 0.223. The dodger lies between 0 and 1 yet matches no entry, so the list was never complete. No surjection from the naturals onto the interval from 0 to 1 exists.
A proper subset can pair perfectly with its whole set, but only for infinite sets. Evens pair with all naturals through doubling, while a finite set always shrinks when members leave. The power set of the naturals climbs higher still: any pairing attempt misses the subset of unpaired members. Listing is the certificate of countability, and diagonalisation defeats every claimed listing of the reals.
Countable means listable, the diagonal number escapes every listing of the reals, and perfect pairing with a proper part marks an infinite set.
2 · Watch
Take it off screen
Where it sits
Where this leads
Jobs that lean on this skill. Follow one to see everything it is built on.
8 questions wait behind this lesson, each with its answer explained. Every answer feeds the sky: stars light as they are learned, and dim when it is time to come back.