Nepotpunost i neodlučivost aritmetike

diplomski rad

• Autor: Daniel Jelušić
• Mentor: Mladen Vuković (mentor)
• Član povjerenstva: Mladen Vuković (predsjednik povjerenstva)
• Član povjerenstva: Robert Manger (član povjerenstva)
• Član povjerenstva: Zvonimir Bujanović (član povjerenstva)
• Član povjerenstva: Mea Bombardelli (član povjerenstva)
• Ustanova koja je dodijelila akademski / stručni stupanj: Sveučilište u Zagrebu; Prirodoslovno-matematički fakultet; (Matematički odsjek); Zagreb
• Datum i država obrane: 2015-07-13, Hrvatska
• Znanstveno / umjetničko područje, polje i grana: PRIRODNE ZNANOSTI; Matematika

Sažetak

U ovom radu dokazuju se Gödelovi teoremi nepotpunosti koji ukazuju na fundamentalna ograničenja dokazivosti unutar teorija prvog reda. Nadalje, dokazuje se Tarskijev teorem o nedefinabilnosti aritmetičke istine, te Churchov teorem o neodlučivosti logike prvog reda. U prvom dijelu obrađuje se postupak aritmetizacije sintakse i definiraju se aritmetičke relacije dokazivosti u teorijama. Zatim se dokazuje da se takve relacije mogu reprezentirati u dovoljno jakim teorijama, iz čega lako slijede gore spomenuti rezultati. Na kraju se razmatra pitanje dokazivosti konzistentnosti u teorijama te se dokazuje Gödelov drugi teorem nepotpunosti.

Sažetak (engleski)

The main goal of this thesis is proving Gödel’s incompleteness theorems, which establish fundamental limitations of provability in first-order theories. Additionally, we prove Tarski’s nondefinability theorem and Church’s undecidability theorem. In the first part, we describe the process of arithmetization and define arithmetical provability predicates. Next, we show that such predicates can be represented in all sufficiently strong theories, from which the results mentioned above immediately follow. Finally, we explore the provability of consistency and prove Gödel’s second incompleteness theorem.

• Ključne riječi: Gödelovi teoremi nepotpunosti; Tarskijev teorem o nedefinabilnosti aritmetičke istine; Churchov teorem o neodlučivosti logike prvog reda; aritmetizacija sintakse; aritmetičke relacije dokazivosti u teorijama
• Ključne riječi (engleski): Gödel’s incompleteness theorems; Tarski’s nondefinability theorem; Church’s undecidability theorem; arithmetization; arithmetical provability predicates
• Jezik: hrvatski
• URN:NBN: urn:nbn:hr:217:310501
• Studijski program: Naziv: Računarstvo i matematika; Vrsta studija: sveučilišni; Stupanj studija: diplomski; Akademski / stručni naziv: magistar/magistra računarstva i matematike (mag. inf. et math.)
• Vrsta resursa: Tekst
• Način izrade datoteke: Izvorno digitalna
• Prava pristupa: Otvoreni pristup
• Datum i vrijeme pohrane: 2019-01-31 13:44:57