Bakalářské práce
Modely Peanovy aritmetiky a jejích fragmentů
Autor
Lenka Čačková
Rok
2012
Typ
Bakalářská práce
Vedoucí
RNDr. Kateřina Trlifajová, Ph.D.
Oponenti
prof. RNDr. Petr Kůrka, CSc.
Katedra
Cantor, Gödel, Turing a paradox lháře
Autor
Martin Slávik
Rok
2020
Typ
Bakalářská práce
Vedoucí
RNDr. Kateřina Trlifajová, Ph.D.
Oponenti
doc. RNDr. Alena Šolcová, Ph.D.
Katedra
Anotace
Tato bakalářská práce se zabývá vysvětlením jednotlivých problémů, zasazením do souvislostí a rozborem důkazů. Cantorova věta, Gödelova věta a problémem zastavení Turingova stroje jsou tři důležitá negativní tvrzení z různých oborů matematiky a informatiky. Spojuje je fakt, že se v jejich důkazech nějakým, avšak rozdílným způsobem využívá metoda diagonalizace. Ve všech případech lze jádro důkazu schematicky ukázat na nekonečné čtvercové tabulce. Pomocí "negace diagonály" se vytvoří nový prvek, jenž v tabulce nemůže být obsažen a z jehož existence vyplývá negativní výsledek těchto tří vět. Způsob vytvoření tabulky a formální popis "negace diagonály" je však odlišný. Jednotlivé důkazy nelze přímočaře mezi sebou převádět. Avšak přes Richardův paradox lze ukázat, jak se z Cantorovy věty odvodí Gödelova věta s použitím paradoxu lháře. Ukazuje také podobnost mezi universálním Turingovým strojem a Gödelovou formulí, která je založena na stejném principu jako je paradox lháře.