Your browser does not allow JavaScript!
JavaScript is necessary for the proper functioning of this website. Please enable JavaScript or use a modern browser.
Open Science Slovenia
Open Science
DiKUL
slv
|
eng
Search
Browse
New in RUL
About RUL
In numbers
Help
Sign in
Gödlov izrek o nepopolnosti : delo diplomskega seminarja
ID
Herman, Lana
(
Author
),
ID
Bauer, Andrej
(
Mentor
)
More about this mentor...
PDF - Presentation file,
Download
(467,38 KB)
MD5: 0DA0C6B7735EF1BF47648A015F299F0B
Image galllery
Abstract
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
Views:
2016
Downloads:
193
Metadata:
Cite this work
Plain text
BibTeX
EndNote XML
EndNote/Refer
RIS
ABNT
ACM Ref
AMA
APA
Chicago 17th Author-Date
Harvard
IEEE
ISO 690
MLA
Vancouver
:
Copy citation
Share:
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
Similar documents
Similar works from RUL:
Similar works from other Slovenian collections:
Back