Exercise 820Logic, sets and proofs › Countability and cardinalityL1Added 3 Nov 2026

Cantor's diagonal argument

#diagonal argument#Cantor#uncountability

Statement

Explain the structure of Cantor's diagonal argument.

Hint

Given any enumeration, construct an element not in the list by differing in the $n$ -th position.

Show solutionHide solution

Setup. Suppose $A$ is countable, enumerated $a_1,a_2,\ldots$ ; each $a_n$ has a "representation" with digits.

Diagonal. Build $b$ whose $n$ -th digit differs from the $n$ -th digit of $a_n$ .

Contradiction. $b$ is a valid element but not in the enumeration, contradicting countability.

Conclusion. Cantor's diagonal argument proves uncountability.