Proving the Power Set of ℕ is Uncountable

Intro to Proofs · Axiom Academy

EXAMPLE Proving is Uncountable Cantor's diagonal argument on subsets instead of decimals — assume the list, then build the set it left out Let denote the power set of — the collection of all subsets of . Prove that is uncountable : no list can contain every subset of . The first five entries of an assumed complete listing of . Each row records, for one listed set, whether 1, 2, 3, 4, 5 belong to it. You ran Cantor's diagonal argument on a completely different kind of object — and the move was identical. The move: assume the complete listing exists, then use it to construct the one object it must have left out. The assumption supplies the raw material that destroys it. The diagonal: D disagrees with S_n about the single element n . One deliberate disagreement per row is all it takes to rule out every row at once. The pivot: D is a perfectly ordinary subset of , so a complete list would have to contain it — and asking whether makes both answers impossible. No representation caveat here: in the decimal version you must draw digits from so that cannot sabotage the argument. Set membership has no such ambiguity — n is either in S_n or it is not — so this version needs no repair at all. Result: is uncountable, so it is strictly larger than itself. This is Cantor's theorem in miniature. The same shape — assume an enumeration of all objects of some kind, then diagonalize out of it — is what shows the halting problem is undecidable.

This is the written version of the interactive lesson above. See the full Intro to Proofs course.