AUC Philosophica et Historica (Acta Universitatis Carolinae Philosophica et Historica) is a multidisciplinary academic journal focused on the humanities with more than 50 years of tradition.
The journal is indexed in CEEOL, DOAJ, and EBSCO.
AUC PHILOSOPHICA ET HISTORICA, Vol 2017 No 2 (2017), 33–43
Diagonal arguments
Jaroslav Peregrin
DOI: https://doi.org/10.14712/24647055.2017.14
published online: 14. 11. 2017
abstract
It is a trivial fact that if we have a square table filled with numbers, we can always form a column which is not yet contained in the table. Despite its apparent triviality, this fact can lead us the most of the path-breaking results of logic in the second half of the nineteenth and the first half of the twentieth century. We explain how this fact can be used to show that there are more sequences of natural numbers than there are natural numbers, that there are more real numbers than natural numbers and that every set has more subsets than elements (all results due to Cantor); we indicate how this fact can be seen as underlying the celebrated Russell’s paradox; and we show how it can be employed to expose the most fundamental result of mathematical logic of the twentieth century, Gödel’s incompleteness theorem. Finally, we show how this fact yields the unsolvability of the halting problem for Turing machines.
keywords: diagonalization; cardinality; Russell’s paradox; incompleteness of arithmetic; halting problem
references (10)
1. G. S. Boolos, J. R. Burgess, and R. C. Jeffrey. Computability and Logic (4th edition). Cambridge University Press, 2002. CrossRef
2. G. Cantor. Über eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen. Journal für die reine und angewandte Mathematik, 77: 258–262, 1874.
3. G. Cantor. Über eine elementare Frage der Mannigfaltigkeitslehre. Jahresbericht der Deutschen Mathematiker-Vereingumg, 1: 75–78, 1890.
4. H. Gaifman. Naming and diagonalization, from Cantor to Gödel to Kleene. Oxford Journal of the IGPL, 15: 709–728, 2006. CrossRef
5. K. Gödel. Über formal unentscheidbare Sätze der Principia Mathematica und verwandter Systeme I. Monatshefte für Mathematik und Physik, 38: 173–198, 1931. CrossRef
6. G. Priest. What is so bad about contradictions? The Journal of Philosophy, 95: 410–426, 1998. CrossRef
7. B. Russell. Mathematical logic as based on the theory of types. American Journal of Mathematics, XXX: 222–262, 1908. CrossRef
8. R. M. Smullyan. Diagonalization and self-reference. Clarendon Press, 1994.
9. A. Tarski. Der Wahrheitsbegriff in den Sprachen der deduktiven Disziplinen. Anzeiger der Österreichischen Akademie der Wissenschaften, Mathematisch-Naturwissenschaftliche Klasse, 69: 23–25, 1932.
10. A. M. Turing. On computable numbers, with an application to the entscheidungsproblem. Proceedings of The London Mathematical Society, 42: 230–265, 1937. CrossRef
Diagonal arguments is licensed under a Creative Commons Attribution 4.0 International License.
