Diagonal arguments
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...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | ces |
| Published: |
Karolinum Press
2017-11-01
|
| Series: | Acta Universitatis Carolinae: Philosophica et Historica |
| Subjects: | |
| Online Access: | http://www.karolinum.cz/doi/10.14712/24647055.2017.14 |
| _version_ | 1818502591825313792 |
|---|---|
| author | Jaroslav Peregrin |
| author_facet | Jaroslav Peregrin |
| author_sort | Jaroslav Peregrin |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-10T21:12:19Z |
| format | Article |
| id | doaj.art-5d411737640d45b2aed099c9e1f18a4b |
| institution | Directory Open Access Journal |
| issn | 0567-8293 2464-7055 |
| language | ces |
| last_indexed | 2024-12-10T21:12:19Z |
| publishDate | 2017-11-01 |
| publisher | Karolinum Press |
| record_format | Article |
| series | Acta Universitatis Carolinae: Philosophica et Historica |
| spelling | doaj.art-5d411737640d45b2aed099c9e1f18a4b2022-12-22T01:33:24ZcesKarolinum PressActa Universitatis Carolinae: Philosophica et Historica0567-82932464-70552017-11-0120172334310.14712/24647055.2017.145363Diagonal argumentsJaroslav PeregrinIt 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.http://www.karolinum.cz/doi/10.14712/24647055.2017.14diagonalizationcardinalityRussell’s paradoxincompleteness of arithmetichalting problem |
| spellingShingle | Jaroslav Peregrin Diagonal arguments Acta Universitatis Carolinae: Philosophica et Historica diagonalization cardinality Russell’s paradox incompleteness of arithmetic halting problem |
| title | Diagonal arguments |
| title_full | Diagonal arguments |
| title_fullStr | Diagonal arguments |
| title_full_unstemmed | Diagonal arguments |
| title_short | Diagonal arguments |
| title_sort | diagonal arguments |
| topic | diagonalization cardinality Russell’s paradox incompleteness of arithmetic halting problem |
| url | http://www.karolinum.cz/doi/10.14712/24647055.2017.14 |
| work_keys_str_mv | AT jaroslavperegrin diagonalarguments |