Nepotpunost i neodlučivost aritmetike

master's thesis

• Author: Daniel Jelušić
• Mentor: Mladen Vuković (mentor)
• Committee member: Mladen Vuković (predsjednik povjerenstva)
• Committee member: Robert Manger (član povjerenstva)
• Committee member: Zvonimir Bujanović (član povjerenstva)
• Committee member: Mea Bombardelli (član povjerenstva)
• Granter: University of Zagreb; Faculty of Science; (Department of Mathematics); Zagreb
• Defense date and country: 2015-07-13, Croatia
• Scientific / art field, discipline and subdiscipline: NATURAL SCIENCES; Mathematics

Abstract

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.

Abstract (english)

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.

• Keywords: 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
• Keywords (english): Gödel’s incompleteness theorems; Tarski’s nondefinability theorem; Church’s undecidability theorem; arithmetization; arithmetical provability predicates
• Language: croatian
• URN:NBN: urn:nbn:hr:217:310501
• Study programme: Title: Computer Science and Mathematics; Study programme type: university; Study level: graduate; Academic / professional title: magistar/magistra računarstva i matematike (magistar/magistra računarstva i matematike)
• Type of resource: Text
• File origin: Born digital
• Access conditions: Open access
• Created on: 2019-01-31 13:44:57