Lesson 10

Another common method of proving nonexistence is the diagonal argument. Below, we provide the statements of several theorems that can be proven using this method.

Theorem (Cantor, 1874). There is no bijection between \(\mathbb{Z}\) and \(\mathbb{R}\).

Theorem (Turing, 1936). The halting problem is algorithmically unsolvable: there is no computer program that would take as input the source code \(P\) of a program and the input \(I\) and (in finite time) determine whether \(P\) will halt on \(I\).

In other words, it is impossible to write a program that would tell us whether another program will loop indefinitely or not. If such a program existed, we could potentially use it to prove Fermat's Last Theorem: we would simply run an infinite search that would stop upon finding the first counterexample. We write “potentially” here because such a program, even if it existed, could run for millennia and provide no practical benefit. In any case, Turing proved in 1936 that such a program does not exist. Interestingly, from this result, one can derive Gödel's first incompleteness theorem, which Gödel published five years earlier. Informally, it states that no matter which (sufficiently strong) system of axioms we choose, there will always be statements that we cannot prove or disprove within this system of axioms.

Theorem (Gödel's first incompleteness theorem, 1931). If formal arithmetic is consistent, then there exists a formula in it that is neither provable nor refutable.

Proving that something does not exist can be challenging. For most computational problems, it is an open problem whether a fast enough algorithm exists.

• Does there exist an algorithm that multiplies two \(n\)-bit numbers in \(O(n)\) time?


• Does there exist an algorithm that multiplies two \(n \times n\) matrices in \(O(n^{2+o(1)})\) time (i.e., in time that grows only slightly faster than \(n^{2}\), for example, \(O(n^{2}\log^{5}n)\))?


• Does there exist an algorithm that checks whether a graph with \(n\) vertices has a Hamiltonian cycle in \(n^{O(1)}\) time (i.e., in polynomial time with respect to \(n\))?