Gödlov izrek o nepopolnostiHerman, Lana (Avtor) Bauer, Andrej (Mentor) logika prvega redaPeanova aritmetikaprimitivno rekurzivne funkcijeGödlovo številoGödlov izrek o nepopolnostiV 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.20202020-10-13 12:07:48Delo diplomskega seminarja/zaključno seminarsko delo/naloga121520UDK: 510.6VisID: 113416COBISS_ID: 58545923sl