Gedelove teoreme

Pre nekoliko meseci sam procitao nesto o Gedelovim teoremama i mnogo me je zainteresovalo. Lik je dokazao da je svaki skup aksioma nekonzistentan i nedoluciv ako sam dobro shvatio. E ajde sad neko ko zna vise o tome od mene da prokomentarise malo.

poz.

Ne baš tako, daleko bilo da je svaki skup aksioma nekonzistentan i neodlučiv.

Postoje dve Gödelove teoreme nekompletnosti, od kojih se najšešće pod imenom "Gödelova teorema" misli na prvu. Ona glasi: "U svakoj formalnoj konzistentnoj teoriji u kojoj su osnovne aritmetičke činjenice dokazive moguće je naći tačno tvrđenje koje se ne može dokazati". Da su osnovne aritmetičke činjenice dokazive znači da posmatrana teorija dozvoljava da na neki način definišemo skup prirodnih brojeva. Napomena: nije dovoljno da model posmatrane teorije bude nadskup prirodnih brojeva, primera radi realni i kompleksni brojevi imaju prirodne brojeve kao podskup, a ipak je njihova aksiomatizacija kompletna. Dalje, Gödel je zapravo dokazao nešto slabije tvrđenje - samo za omega-konzistentne teorije (svaka omega-konzistentna teorija mora biti konzistentna, ali obrnuto ne važi), a pojačanje u vidu činjenice da je konzistentnost dovoljna je nekoliko godina kasnije pokazao John Barkley Rosser Sr.

Da vidimo kako otprilike teče Gödelov dokaz (naravno, u potpunosti neformalan pristup). Otprilike rečeno, u svom radu on dolazi do tvrđenja koje kaže:
"Ovo tvrđenje je nedokazivo".
Ukoliko je tvrđenje zaista nedokazivo onda je ono i tačno (jer to zapravo tvrdimo), i pokazali smo to što nam treba. Ukoliko bi, pak, ovo tvrđenje bilo dokazivo onda bi bilo netačno pa bi sistem aksioma zapravo bio nekonzistentan, a to smo isključili uslovom. E sad, kako Gödel tačno konstruiše ovakvo tvrđenje bi mogao da bude predmet diskusije na još mnogo strana, i jedini način da ti pomognem ukoliko te ovo zaista zanima je da ti prosledim originalni dokaz na nemačkom ili engleski prevod pa sam pročitaj.

Druga Gödelova teorema nekompletnosti, vrlo bliska prvoj, kaže: "Svaka formalna teorija sposobna da formuliše sopstvenu konzistenciju može dokazati svoju konzistenciju ako i samo ako je nekonzistentna". Ovo ujedno daje negativan odgovor na drugi Hilbertov problem koji se bavi pitanjem može li se dokazati da su aksiome logike konzistentne, ali pošto stičem osećaj da odlazim predaleko od teme ovde ću stati uz napomenu da slobodno pitaš za dodatno obrazloženje nekog detalja koji te interesuje (znam da nisam preterano razumljivo izložio sve ovo), a ja ću se potruditi da odgovorim što bolje mogu.

Potpis

Ljubičice crvena, što si plava kô zelena trava.

Kakva su aktuelna razmišljanja matematičara u vezi sa prevazilaženjem problema nastalih posle Godelove teoreme o nekompletnosti?

A gde je tu problem ?

Potpis

CHUPCKO

Ne znam, Godel kaže da problem postoji. Ti nisi ništa čuo o tome?

Nije on rekao da ima problema, samo da je peanova aksiomatika nepotpuna
i da bilo koju aksiomatiku uzmes opet ce biti neoptpuna :). A to meni nije problem :). Ja dopustam da neke teorije budu poludolucive :).

Za pocetak ti savetujem da procitas ovu knjigu :) http://en.wikipedia.org/wiki/G%C3%B6del%2C_Escher%2C_Bach

Ajde recimo pokusaj da nekome ko ne zna matematiku bas toliko dobro (na primer nekom ko je bio vrlo dobar u srednjoj skoli i nije upisao faks) pojasnis taj problem :).

Potpis

CHUPCKO

Kada se prevede na običan jezik, zar to ne znači da su sami temelji moderne matematike pomalo ugroženi, t.j. da sistem sa aksiomama i teoremama ne mora dokazano biti tačan (pri čemu se ne može dokazati da je netačan)?

Ne bas, nigde se ne bazira na tome :), samo teorija nije potpuna. Ajde prvo probaj da prostim recima objasnis nekome u cemu je tu problem :). MIslim pa sta ako si nasao formulu koja nije ni tacna ni netacna :)

Potpis

CHUPCKO

Pa evo u prethodnom postu sam prostim rečima objasnio. Ako budem koristio prostije reči to će onda biti psovke a to nije dobro za forum ovog renomea.

Ako nađem jednu formulu koja nije ni tačna ni netačna nije (velik) problem, ali ako imam čitavu teoriju (sa sve setom aksioma) za koju ne znam da li je tačna ili ne, čini mi se da to već jeste problem.

Ti znas da je teorija tacna, jer nije protivurecna :) ili jeste :).

Uostalom sta znaci da je teorija tacna ili ne, to su samo simboli, bitno je da nije protivrecna :).

A sada sto nije potpuna, sta cu :)

Nista spektakularno i ne vidim neku krizu :). Pa ni Rasel nije uzdrmao toliko matematiku :).

Potpis

CHUPCKO

Misliš nije je uzdrmao toliko kao Goedel?

Dakle da li je ta teroija protivrecna ?. Stavimo nepotpunost na stranu trenutno. To sto jos nisi spoznao modalnu logiku, ne znaci da tu nesto ne valja :)).

Dakle ajde zamisli da sam ja zavrsio recimo hemijsku skolu. imao iz matematike 4. Probaj da mi objasnis sta je to goedel prckao :).

I nemoj da mi pricas kako su ugrozeni temelji i slicno, konkretno mi pojasni u cemu je problem ? Ja ne vidim problem, po meni bi bio problem da jednom dobijem da je 2+3 5 a jednom da je 6.

Potpis

CHUPCKO

Pa već sam Ti rekao da ne znam o tome puno. Ni vi niste ništa detaljnije radili Goedela?

Moj naslov teme je bio lepši.

Eto, kada se spoji nekoliko tema, sve bude lepse :)

Potpis

CHUPCKO

Da li to znači da se Hilbertova ideja o aksiomatici ne može realizovati? Mislim, imamo konzistentan (neprotivurečan) sistem aksioma samo ako ne možemo dokazati tačnost (ili netačnost) baš svih teorema iz sistema (t.j. sistem nije kompletan)?

Procitaj malo bolje bojanov post, i takodje ima gomila knjiga o tome :). Ukratko, postoje mnoge lepe formalne teorije, koje su odlucive :).

Potpis

CHUPCKO

Poenta Gedelove teoreme nije u tome da je svaki aksiomatski set neispravan, vec nepotpun. Bez obzira kako formalno zasnovao matematiku, postojat ce tvrdnje ciju istinitost ne mozes utvrditi.


Bas tako.

Mada ima nekih lepih formalnih teorija koje su i odlucive :))), i potpune ;).

Potpis

CHUPCKO

Da li se ovo vidi iz sledeće konstrukcije (nešto slično kao Tjuringov tzv "Halting" problem):

Iskaz A: "Iskaz B je tačan".
Iskaz B: "Iskaz A nije tačan."