---
tag: 0XCH8QVDCQ
kind: concept
name: Cantor's diagonal argument
aliases: [diagonal-argument, diagonalization]
msc: ["03E10"]
uses: [0X55M9XET4, 0ZG61TFBES]
sources:
  - url: https://en.wikipedia.org/wiki/Cantor's_diagonal_argument
    locator: lead section
same_as:
  wikidata: Q729471
  wikipedia: Cantor's diagonal argument
---

## Summary

Cantor's diagonal argument shows that some infinite sets are [[uncountable|0X55M9XET4]].
Given a list $s_0, s_1, s_2, \dots$ of infinite sequences of $0$ and $1$, define a sequence $t$ by $t(n) = 1 - s_n(n)$.
Then $t$ differs from each $s_n$ at position $n$, so $t$ is not in the list.
So the set of all such sequences is not countable.

## Remarks

Georg Cantor published the argument in 1891. His first proof that $\mathbb{R}$ is uncountable, from 1874, used another method.
The same idea proves [[Cantor's theorem|0WTEMGYV2C]] for every set.
Diagonal arguments also appear in the proofs of the halting problem and of Gödel's incompleteness theorems.

## Explanations

### L1 human

Write the list of sequences as the rows of a table.
Go down the diagonal and change each entry.
The new row differs from row $n$ at column $n$, so it cannot be any row of the table.