20.500.12556/RUL-121520 Gödlov izrek o nepopolnosti delo diplomskega seminarja Gödel's incompleteness theorem 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. 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. logika prvega reda Peanova aritmetika primitivno rekurzivne funkcije Gödlovo število Gödlov izrek o nepopolnosti first-order logic Peano arithmetic primitive recursive functions Gödel number Gödel's incompleteness theorem true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2020-10-13 12:07:48 2020-10-13 12:07:50 2024-05-29 14:27:43 0000-00-00 00:00:00 2020 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 510.6 113416 58545923 1528.pdf 1528.pdf 1 0DA0C6B7735EF1BF47648A015F299F0B f084ff21b7be71e79c5e70ca81cf3f4a3d24539994dde1ff5216ab23925c1fd8 e764feee-a1ba-11eb-a523-00155dcfd717 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=136455 Fakulteta za matematiko in fiziko 0 0 0