RNDr. Kateřina Trlifajová, Ph.D.

RNDr. Kateřina Trlifajová, Ph.D.

doc. RNDr. Alena Šolcová, Ph.D.

Department of Theoretical Computer Science

This bachelor's thesis deals with the explanation of individual problems, setting them in context and analyzing how to prove them. Cantor's theorem, Gödel's theorem, and the Halting problem are three important negative statements from various fields of mathematics and computer science. They are united by the fact that the diagonalization method is used in their proof, even though in different ways. In all cases, the core of the proof can be shown schematically on an infinite square table. The "diagonal negation" creates a new element which cannot be included in the table and whose existence results in a negative result of these three theorems. However, the way the table is created and the formal descriptions of the "diagonal negation" are different. The individual pieces of evidence cannot be transferred directly into each other. However, with Richard's paradox, it is possible to show how Gödel's theorem is derived from Cantor's theorem using the Liar's paradox. It also shows the similarity between the universal Turing machine and the Gödel's formula, which is based on the same essence as the Liar's paradox.

Thesis on DSpace

RNDr. Kateřina Trlifajová, Ph.D.

prof. RNDr. Petr Kůrka, CSc.

Department of Theoretical Computer Science