Gödlov izrek o nepopolnosti : delo diplomskega seminarja

Herman, Lana (author), Bauer, Andrej (mentor)

V diplomski nalogi je predstavljen in dokazan Gödlov izrek o nepopolnosti za Peanovo aritmetiko. To je teorija prvega reda, ki aksiomatizira naravna števila in njihovo aritmetiko. Izrek o nepopolnosti trdi, da Peanova aritmetika ne more biti hkrati popolna in konsistentna. Gödel za dokaz sestavi stavek, ki sam zase pravi, da ni dokazljiv. Ustvari ga s pomočjo Gödlovega kodiranja (povezava med znaki teorije prvega reda in števili) ter diagonalizacije (povezava med formulo in njenim Gödlovim številom). Gödlov stavek sestavlja dvomestna relacija, ki je pravilna natanko tedaj, ko je prvo število Gödlovo število dokaza za diagonalizacijo formule z Gödlovim številom, ki je drugo število. Ker je ta relacija primitivno rekurzivna, je predstavljiva v Peanovi aritmetiki (če je pravilna, je dokazljiva v PA). Torej dokaže, da ne obstaja Gödlovo število dokaza Gödlovega stavka. Ob predpostavki, da je Peanova aritmetika konsistentna, je Gödlov stavek torej pravilen, a nima dokaza. To pomeni, da Peanova aritmetika ni popolna.

• Language: Slovenian
• Keywords: logika prvega reda, Peanova aritmetika, primitivno rekurzivne funkcije, Gödlovo število, Gödlov izrek o nepopolnosti
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2020
• PID: 20.500.12556/RUL-121520
• UDC: 510.6
• COBISS.SI-ID: 58545923
• Publication date in RUL: 13.10.2020

Secondary language

• Language: English
• Title: Gödel's incompleteness theorem

Abstract

Gödel's incompleteness theorem for Peano arithmetic is presented and proved in the diploma thesis. It is a first-order theory that axiomatizes natural numbers and their arithmetic. The incompleteness theorem says that Peano arithmetic cannot be both complete and consistent. For proof, Gödel composes a sentence saying that it is unprovable. It is made possible by Gödel's numbering (associating symbols of first-order theory with numbers) and diagonalization (link between the formula and its Gödel number). A Gödel sentence is consisted of a two-place relation that is true if and only if the first number is Gödel's number for proof of diagonalization of formula with Gödel's number that is the second number. Since this relation is primitive recursive, it is capturable in Peano arithmetic (if it is correct PA can prove it). Therefore it proves that there is no Gödel's number for proof of Gödel's sentence. Assuming Peano arithmetic is consistent, Gödel sentence is therefore true, but has no proof. That means Peano arithmetic is not complete.

• Keywords: first-order logic, Peano arithmetic, primitive recursive functions, Gödel number, Gödel's incompleteness theorem