David Wyde

2020-10-01

What do we learn when we try to list the elements of an infinite set?

Diagonal Arguments and Infinite Sets, 2 pages.

A diagonal argument is a proof technique that creates a contradiction by attempting to list every element of an infinite set.

Georg Cantor used a diagonal argument to prove that the infinite set of real numbers is larger than the infinite set of natural numbers. Alonzo Church used a similar proof to show that some algorithms are impossible to implement.

I think Cantor’s and Church’s diagonal arguments prove only that it is impossible to list every element of an infinite set. In each case, the argument should end before the final step that proves the intended result.