Countability and the Diagonal Argument

Intro to Proofs · Axiom Academy

LESSON Countability and the Diagonal Argument Two proof moves: to show a set is countable, build the list — to show it is not, assume the list and build what it missed. 1. Countable Means There Is a Complete Listing A set is countable if you can arrange every one of its elements into a single infinite list — a first, a second, a third, and so on — that misses nothing and repeats nothing . That list is exactly a bijection from onto the set. A listing IS a bijection with the natural numbers The set itself carries no order — the animation starts with its elements scattered. A listing is the extra structure you supply: a rule that hands you the elements one at a time. Only two things can go wrong. Some element is never reached, no matter how far down the list you read. Then f is not onto , and the listing is incomplete. Two different indices name the same element. Then f is not one-to-one . (Harmless in practice — you can always delete duplicates — but the clean statement needs a bijection.) 2. To Prove a Set IS Countable, Build the List Proving countability is an existence claim: there exists a bijection with . The cleanest way to prove something exists is to hand it over. Take . Its natural order is useless as a listing: start anywhere and walk left and you never reach 1 ; there is no leftmost integer to start from. So build a different order — start at 0 and alternate outward.

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