Countability and Cantor's Diagonal Argument

Real Analysis · Axiom Academy

LESSON Countability & Cantor's Diagonal Argument and even the dense can be listed. provably cannot — and one diagonal shows why. Cardinality for infinite sets rests on exactly one tool: the bijection. Two sets have the same size when some function pairs them element for element — nothing left over on either side . Applying that to gives the definition the rest of the lesson runs on. A bijection is a list: write a_n = f(n) and every element of A appears exactly once. Countable means listable. There is a second, often handier test. Instead of building a bijection onto A , it is enough to injectively tag the elements of A with natural numbers: The reason is that every subset of is itself countable — list its elements in increasing order — so an injection g makes A match , which is finite or bijective with . Watch what that definition tolerates. Take , which contains and one extra element. Pair each with the index v + 1 : every arrow leans right by exactly one column, and every index still gets used exactly once. looks like "twice , plus zero", and it has no smallest element, so the obvious plan — start at the bottom and count upward — never gets started. The fix is to refuse to walk in one direction. Start at 0 and step alternately right and left , going one unit further out each round. That informal recipe is a genuine function. Writing : even indices sweep out the positives, odd indices the rest an explicit two-sided inverse, so f is a bijection

This is the written version of the interactive lesson above. See the full Real Analysis course.