Countability and diagonal arguments: when no list can suffice

Use natural numbers starting at zero. A countably infinite set has a bijection with the naturals; countable will mean finite or countably infinite. The integers can be listed as zero, one, minus one, two, minus two, and so on. Every integer appears after finitely many steps even though the list has no last step. Removing every negative entry still leaves an infinite subset with the same cardinality, something impossible for proper subsets of finite sets.

For pairs of nonnegative integers, scanning the entire first row before moving to the second fails: the first row never ends. Instead list by increasing coordinate sum, and within each diagonal choose a fixed order. Each diagonal is finite, and a pair with sum s appears after only finitely many earlier diagonals. This argument proves coverage; a consistent within-diagonal order and no repeated coordinates prove uniqueness. A drawing of a few diagonals is evidence for the rule, not the full enumeration proof.

Every rational number can be written as an integer numerator over a positive integer denominator. Enumerate such pairs diagonally, include both numerator signs, and skip repeated fractions after their first occurrence. Each rational has a representative at a finite pair position, so it eventually appears. The reduced-fraction condition offers another way to remove duplicates. Because there are infinitely many integers among the rationals, the rationals are countably infinite rather than finite.

Between any two distinct rational numbers lies another rational, their average, yet countability still holds. Density describes how a set sits inside an ordered space; cardinality compares the set with possible indexing sets. A list need not proceed in increasing numerical order. Indeed, a complete increasing list of positive rationals cannot start, because any proposed first positive rational has a smaller positive half. Failure of one ordering convention says nothing by itself about whether another enumeration exists.

Suppose someone proposes a function listing every subset of the naturals. The nth listed subset either contains n or does not. Form a new subset D by reversing that particular membership decision at every index: include n precisely when the nth listed subset omits n. D differs from the nth listed subset at least at element n. Therefore it differs from every entry, no matter how ingenious the proposed list was.

This argument generalizes to any set A and any function from A to its power set. Define D to contain exactly those a not belonging to their own assigned subset. If D were assigned to some d, membership of d in D would be equivalent to its own negation, a contradiction. Thus no such function is onto. The argument concerns subsets already formed inside A, avoiding an unrestricted set of all sets. A finite display cannot certify the infinite conclusion; the arbitrary-index construction supplies the proof.