Teoreme de incompletitudine ale lui Gödel

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare

În logica matematică , teoremele incompletei lui Gödel sunt două celebre teoreme dovedite de Kurt Gödel în 1930 . Gödel a anunțat prima sa teoremă a incompletitudinii într-o masă rotundă pe marginea celei de-a doua conferințe privind epistemologia științelor exacte din Königsberg . John von Neumann , prezent la discuție, a reușit să demonstreze singur teorema spre sfârșitul anului 1930 și, în plus, a furnizat o dovadă a celei de-a doua teoreme a incompletitudinii, pe care a anunțat-o lui Gödel într-o scrisoare din 20 noiembrie 1930. Între timp, Gödel obținuse o dovadă a celei de-a doua teoreme a incompletitudinii și o includea în manuscrisul primit de revista Monatshefte für Mathematik la 17 noiembrie 1930. [1] . Acestea fac parte din teoremele limitative , care specifică proprietățile pe care sistemele formale nu le pot avea.

Prima teoremă a incompletitudinii

Fie P o formalizare a aritmeticii lui Peano .

Cu incompletitudine a lui Gödel teorema sa demonstrat că această teorie este completă numai pentru axiome logice, adică: pentru fiecare formulă „R“, există o formulă care îi corespunde „r“ , astfel încât:

  • de sine subzistă ;
  • de sine nu exista .

Prima teoremă a incompletitudinii lui Gödel spune că:

În orice teorie matematică T suficient de expresivă pentru a conține aritmetică, există o formulă astfel încât, dacă T este coerent , atunci nici unul nici negarea acesteia Acestea sunt demonstrabile în T.

Cu o oarecare simplificare, prima teoremă afirmă că:

În orice formalizare coerentă a matematicii care este suficient de puternică pentru a putea axiomatiza teoria elementară a numerelor naturale - adică suficient de puternică pentru a defini structura numerelor naturale dotate cu operații de sumă și produs - este posibil să se construiască o propoziție corectă din punct de vedere sintactic asta nu poate fi nici dovedit, nici respins în cadrul aceluiași sistem. [2]

Intuitiv, dovada primei teoreme se învârte în jurul posibilității de definire a unei formule logice ceea ce își neagă propria probabilitate: prin urmare, s-a dovedit că, pentru ca T să fie consecvent, niciuna dintre acestea nici poate fi demonstrabil. Prin urmare, este crucial ca T să permită codificarea formulelor auto-referențiale , adică care vorbesc despre ele însele: această cerință este garantată de faptul că T este cel puțin la fel de expresiv ca aritmetica sau, mai general, că T este capabil să reprezinte toate funcțiile recursive primitive .

Meritul lui Gödel a fost deci de a fi expus această propoziție și adevărata putere a acestei teoreme este că este valabilă „pentru fiecare teorie afină”, adică pentru orice teorie formalizată, la fel de puternică ca aritmetica elementară. În special, Gödel a demonstrat că aritmetica însăși este incompletă: există, prin urmare, unele realități, dar nu demonstrabile.

Această teoremă, care exprimă una dintre cele mai dezbătute limite ale matematicii, este una dintre cele mai frecvent neînțelese. Este o teoremă proprie logicii formale și, dacă este extrapolată din acest context, se poate împrumuta cu ușurință unor interpretări eronate. Există mai multe afirmații aparent similare cu prima teoremă a incompletitudinii lui Gödel, dar care nu sunt de fapt adevărate. Acestea vor fi prezentate mai târziu în secțiunea Concepții greșite despre teorema incompletitudinii lui Gödel .

O construcție axiomatică nu poate satisface în același timp proprietățile coerenței și completitudinii. Dacă întreaga aritmetică este dedusă din axiome, acestea conduc la o contradicție; dacă teoremele derivate nu sunt contradictorii, există cel puțin o teoremă care nu poate fi dovedită pornind doar de la acele axiome, un caz indecidabil al cărui nu este posibil să se spună dacă este adevărat sau fals. Insistând pe postularea adevărului unei teoreme indecidabile cu o nouă axiomă, problema este pur și simplu deplasată și construcția propune un al doilea caz de indecizie. Cazul indeciziei se numește ipoteză și, la fel ca axioma, nu este demonstrabil, dar spre deosebire de acesta, poate fi acceptat sau nu; distincția dintre axiomă și ipoteză depinde de faptul că neacceptarea unei axiome ne obligă imediat să oprim analiza, în timp ce acceptarea este roditoare de consecințe și teoreme. În schimb, acceptarea sau nu a unei ipoteze poate duce la consecințe.

A doua teoremă a incompletitudinii

A doua teoremă a incompletitudinii lui Gödel, care se dovedește prin formalizarea unei părți a dovezii primei teoreme în cadrul sistemului însuși, afirmă că:

Fie T o teorie matematică suficient de expresivă pentru a conține aritmetica: dacă T este consistent, nu puteți demonstra consistența lui T în T.

Cu o simplificare,

Niciun sistem, care este suficient de coerent și expresiv pentru a conține aritmetica, nu poate fi folosit pentru a-și demonstra propria coerență.

Acest rezultat a avut efecte devastatoare asupra acelei abordări filosofice a matematicii cunoscută sub numele de programul Hilbert . David Hilbert credea că coerența sistemelor formale complexe, precum cea a analizei matematice pe câmpul realelor , ar putea fi demonstrată prin descompunerea sistemului în sisteme mai simple. În acest fel, problema coerenței tuturor matematicilor ar fi putut fi urmărită înapoi la coerența aritmeticii elementare. A doua teoremă a incompletitudinii lui Gödel arată că, deoarece nici măcar un sistem deosebit de simplu, cum ar fi cel al aritmeticii elementare, nu poate fi folosit pentru a-și dovedi propria coerență, deci, cu atât mai mult, nu poate fi folosit pentru a demonstra coerența sistemelor mai puternică.

Înțelesul teoremelor lui Gödel

Teoremele lui Gödel sunt teoreme logice de ordinul întâi și trebuie plasate în acest context. În logica formală, atât enunțurile matematice, cât și dovezile sunt scrise într-un limbaj simbolic, unde este posibilă verificarea mecanică a validității probelor și nu poate exista nicio îndoială că o teoremă este o consecință a axiomelor enumerate inițial. În teorie, orice dovadă dezvoltată în cadrul unui sistem formal poate fi verificată de un computer și, de fapt, există programe realizate pentru a verifica validitatea dovezilor sau pentru a căuta noi dovezi (acestea sunt numite verificatoare automate de teoreme sau General Theorem Prover - GTP) .

Pentru a defini o teorie formală este necesar să cunoaștem și să definim câteva axiome de pornire. De exemplu, se poate pleca de la un set finit de axiome, ca în geometria euclidiană sau, mai general, se poate permite să existe un set infinit de axiome. În acest caz, totuși, trebuie să fie posibil să se verifice mecanic dacă orice propoziție este sau nu o axiomă a acelui set (în acest caz vorbim de o schemă de axiome). În informatică se pare că există un set recursiv de axiome. Deși poate părea ciudat să ne imaginăm o listă infinită de axiome, tocmai acest lucru este folosit în axiomatizarea numerelor naturale în logica de ordinul întâi: când vrem să convertim axiomele lui Peano într-un limbaj de ordinul întâi, principiul inducției devine unul schema axiomei - se spune că pentru fiecare proprietate posibilă dacă zero are acea proprietate anume și succesorul oricărui număr natural care are acea proprietate are și acea proprietate , atunci toate numerele naturale au acea proprietate -. Deoarece acest lucru trebuie să fie valabil pentru fiecare proprietate posibilă și în limbajul de prim ordin nu poate fi cuantificat pe proprietăți, singura modalitate posibilă de a defini principiul inducției în acest context este de a lua în considerare un număr infinit de axiome, una pentru fiecare proprietate posibilă care poate fi definită în limba de ordinul întâi. Teoria axiomatică obținută cu această formalizare este cunoscută în domeniul logicii matematice cu acronimul PA (Peano Arithmetic).

Prima teoremă a incompletitudinii lui Gödel demonstrează că orice sistem care ne permite să definim numerele naturale este neapărat incomplet: conține afirmații ale căror adevăr sau falsitate nu pot fi dovedite.

Faptul că pot exista sisteme incomplete nu este o constatare deosebit de surprinzătoare. De exemplu, dacă postulatul paralel este eliminat din geometria euclidiană , se obține un sistem incomplet (în sensul că sistemul nu dovedește toate propozițiile adevărate). A fi incomplet pentru un sistem formal înseamnă pur și simplu - din punct de vedere semantic - că nu include toate axiomele necesare pentru a caracteriza în mod unic un model specific (acesta este cazul, de exemplu, al primelor 4 axiome ale lui Euclid care admit atât geometria euclidiană și geometriile neeuclidiene).

Ce Gödel a demonstrat că este, în multe cazuri importante, cum ar fi în număr de teorie, teoria multimilor sau analiză matematică , niciodată nu este posibil să se definească lista completă de axiome , care ne permite să dovedească toate adevărurile. Ori de câte ori se adaugă o propoziție la setul de axiome, va exista întotdeauna o altă propoziție care nu este inclusă.

Axiomele infinite pot fi oricând adăugate; de exemplu, puteți adăuga toate enunțurile adevărate despre numere naturale la lista axiomelor, dar această listă nu este un set recursiv . Dacă se ia orice afirmație aleatorie, nu va fi posibil să se stabilească dacă este sau nu o axiomă a sistemului. Prin urmare, având în vedere orice demonstrație, în general, nu va mai fi posibilă verificarea corectitudinii acesteia.

Teorema lui Gödel are o altă interpretare care poate fi exprimată în contextul computerului. În logica de ordinul întâi, ansamblul tuturor teoremelor unei teorii este un set recursiv enumerabil : aceasta înseamnă că este posibil să se scrie un algoritm care poate genera, mai devreme sau mai târziu, orice dovadă validă. Se poate întreba dacă aceste teoreme satisfac proprietatea mai restrictivă de a fi recursive . Este posibil să scrieți un program de computer care poate determina cu siguranță dacă o anumită afirmație este adevărată sau falsă? Teorema lui Gödel spune că acest lucru nu este în general posibil.

Mulți cercetători logici susțin că teoremele incompletei lui Gödel au subminat definitiv programul lui David Hilbert care vizează construirea unui formalism matematic universal. Ideea general împărtășită este că în cea de-a doua teoremă găsim răspunsul definitiv care a dat lovitura finală programului lui Hilbert, alții cred că acest răspuns se găsește în prima teoremă, dar există și cei care cred că niciunul dintre ei nu conduce neapărat la acest gen de concluzii despre programul lui Hilbert.

Exemple de propoziții indecidabile

Existența unei propoziții indecidabile în cadrul unui sistem formal nu este un fapt deosebit de surprinzător în sine.

În lucrarea comună ulterioară a lui Gödel și Paul Cohen găsim exemple concrete de propoziții indecidabile (propoziții care nu pot fi nici dovedite, nici infirmate): atât axioma alegerii, cât și ipoteza continuumului sunt indecidabile în axiomatizarea tradițională a teoriei mulțimilor . Aceste rezultate nu se bazează pe teorema incompletitudinii.

În 1936 , Alan Turing a demonstrat că problema opririi - adică dacă o mașină Turing încetează să ruleze un anumit program - este indecidabilă. Acest rezultat a fost generalizat ulterior în domeniul funcțiilor recursive cu teorema lui Rice, care arată cum toate problemele de decizie non-triviale sunt indecidabile într-un sistem complet conform lui Turing .

În 1973 s-a dovedit că problema teoriei de grup a lui Whitehead este indecidabilă în sistemul teoriei mulțimilor. În 1977 , Kirby, Paris și Harrington au arătat că o afirmație combinatorie , o variație a teoremei lui Ramsey , este indecidabilă în axiomatizarea aritmeticii dată de axiomele lui Peano, dar poate fi dovedită în sistemul mai larg al teoriei mulțimilor. Teorema lui Kruskal , care găsește aplicații în informatică, este de asemenea indecidabilă pornind de la axiomele lui Peano, dar poate fi dovedită în teoria mulțimilor. Teorema lui Goodstein propune o afirmație relativ simplă despre numerele naturale, care este indecidabilă în aritmetica lui Peano .

Gregory Chaitin a formulat enunțuri indecidabile în teoria informației algoritmice și, de fapt, și-a dovedit propria teoremă de incompletitudine valabilă în acest domeniu.

Una dintre primele probleme suspectate a fi indecidabile a fost cuvântul problemă pentru grupuri , propus de Max Dehn în 1911 , potrivit căruia există un grup finit generat care nu are algoritm capabil să determine dacă două cuvinte sunt echivalente. Abia în 1952 s-a dovedit indecidabilitatea acestei probleme.

Neînțelegeri despre teorema incompletitudinii lui Gödel

Discuția amplă declanșată de prima teoremă a incompletitudinii lui Gödel a produs, de asemenea, numeroase neînțelegeri. În această secțiune, cele mai frecvente interpretări greșite sunt clarificate:

  1. Teorema se aplică numai acelor sisteme care permit definirea numerelor naturale ca un set. Nu este suficient ca sistemul să conțină numere naturale. De asemenea, este necesar ca, folosind axiomele sistemului și logica primului ordin, să putem exprima conceptul " este un număr natural. "Există numeroase sisteme care conțin numere naturale și care sunt complete. De exemplu, atât numerele reale cât și cele complexe au axiomatizări complete.
  2. Este posibil să se demonstreze o propoziție indecidabilă cu un sistem dat de axiome pur și simplu prin adăugarea de axiome adecvate. De exemplu, este posibil să se demonstreze Teorema lui Goodstein , care se ocupă de numere întregi, acceptând axiomele numerelor transfinite , care sunt clase de infinit mai mari decât infinitul numerelor întregi. Mai clar este posibil să se ridice la rangul unei noi axiome precis afirmația indecidabilă (sau chiar negația sa, care este și indecidabilă), obținându-se astfel o nouă teorie matematică, ca în cazul analizei nestandardizate . Acest mecanism este infinit repetabil. Prin urmare, s-ar putea argumenta că goedelizarea acționează ca un generator de axiome sensibile.
  3. Gödel însuși nu credea că teoremele sale vor distruge credința în matematică: a spus că pur și simplu completitudinea aritmeticii nu poate fi dovedită prin axiomele aritmeticii, ci era nevoie de altceva.

Discuții și implicații

Consecințele incompletitudinii influențează filosofia matematicii și, în special, unele dintre școlile sale de gândire, cum ar fi formalismul , care fundamentează definirea principiilor sale pe logica formală. Prima teoremă poate fi parafrazată spunând că „nu este posibil să construim un sistem axiomatic care să cuprindă totul, care să fie în același timp capabil să demonstreze toate adevărurile matematice și fără falsități”.

Pe de altă parte, din punct de vedere strict formalist, această parafrază ar trebui considerată lipsită de sens, deoarece presupune că „adevărul” și „minciuna” matematică sunt concepte bine definite în sens absolut și nu concepte referitoare la fiecare formă formală specifică. sistem.

Următoarea reformulare a celei de-a doua teoreme este și mai nedumeritoare pentru cei care se ocupă de fundamentele matematicii :

Dacă un sistem axiomatic își poate dovedi propria consistență, atunci trebuie să fie inconsecvent.

Prin urmare, pentru a stabili coerența unui sistem S, este necesar să se utilizeze un alt sistem T. Dar o dovadă în T nu este pe deplin convingătoare decât dacă coerența lui T a fost deja stabilită fără a utiliza sistemul S. De exemplu, coerența axiomelor lui Peano pentru numerele naturale poate fi dovedită în teoria mulțimilor , dar nu doar în teoria numerelor naturale. Acesta oferă un răspuns negativ la problema numărul 2 din celebra listă a lui David Hilbert cu cele mai importante întrebări deschise din matematică (cunoscută sub numele de lista Hilbert a problemelor ).

În principiu, teoremele lui Gödel lasă încă o oarecare speranță: ar putea fi posibil să se creeze un algoritm general care să determine, pentru o propoziție dată, dacă este indecidabilă sau nu, permițând astfel matematicienilor să evite cu totul propozițiile indecidabile. Cu toate acestea, răspunsul negativ dat problemei Entscheidung arată că un astfel de algoritm nu poate exista.

Unii cercetători cred că o propoziție, care nu poate fi dovedită în cadrul unui sistem deductiv, poate fi bine demonstrată cu utilizarea unui limbaj metalic. Și ceea ce nu poate fi dovedit în acel limbaj metalic poate fi probat probabil prin intermediul unui meta- limbaj. Acest proces, în teorie, poate fi reprodus infinit recursiv. Dacă ne referim la un fel de super teorie a tipurilor cu axiomă de reducibilitate - care cu o procedură inductivă se extinde la întregul univers stratificat al limbajelor - ar fi posibil, din când în când, să ocolim obstacolul incompletitudinii.

Trebuie remarcat faptul că teoremele lui Gödel sunt aplicabile numai acelor sisteme axiomatice suficient de puternice .

„Suficient de puternic” înseamnă că teoria conține un număr suficient de reguli aritmetice pentru a permite construirea codării necesare pentru a demonstra prima teoremă a incompletitudinii. În practică, tot ce este necesar sunt câteva reguli elementare referitoare la adunare și multiplicare, așa cum se întâmplă de exemplu în formalizarea aritmeticii lui Robinson . Există și sisteme axiomatice mai slabe care sunt coerente și complete, de exemplu aritmetica Presburger , în care poate fi dovedită orice afirmație adevărată de prim ordin referitoare la adunare.

Sistemul axiomatic poate consta dintr-un număr infinit de axiome (ca în aritmetica de ordinul întâi a lui Peano), dar, pentru a aplica teorema lui Gödel, trebuie să existe un algoritm care să poată verifica efectiv corectitudinea probelor. De exemplu, ansamblul tuturor afirmațiilor de prim ordin care sunt adevărate în modelul numerelor naturale este, desigur, o teorie completă; aici, teorema lui Gödel nu poate fi aplicată deoarece nu există nicio procedură capabilă să decidă dacă o anumită propoziție este sau nu o axiomă. De fapt, acest fapt este o consecință a primei teoreme a incompletitudinii lui Gödel.

Un alt exemplu de teorie specificată în așa fel încât prima teoremă a lui Gödel nu i se poate aplica poate fi construit după cum urmează. Toate afirmațiile posibile privind numerele naturale sunt ordonate mai întâi după lungime, apoi urmând ordinea lexicografică . Plecăm de la un sistem axiomatic inițial echivalent cu sistemul de axiome al lui Peano. Lista propozițiilor este apoi derulată una câte una și, dacă adevărul sau falsitatea propoziției curente nu pot fi dovedite pe baza axiomelor actuale, se adaugă la sistem. Aceasta construiește un sistem care este coerent și suficient de puternic, dar nu recursiv enumerabil .

Gödel însuși a dovedit o versiune a teoremelor anterioare care este din punct de vedere tehnic puțin mai slabă, în timp ce prima dovadă a teoremelor în forma prezentată aici a fost dată de J. Barkley Rosser în 1936 .

Practic, dovada primei teoreme constă în construirea, în cadrul unui sistem axiomatic formal, a unei anumite afirmații p căreia i se poate da următoarea interpretare meta-matematică:

p = "Această afirmație nu poate fi dovedită"

În această calitate, poate fi văzut ca o variantă modernă a paradoxului mincinos . Spre deosebire de afirmația mincinosului, p nu se referă direct la sine; interpretarea anterioară poate fi formulată doar din afara sistemului formal.

Dacă sistemul formal este consecvent, dovada lui Gödel arată că p (și negarea acestuia) nu pot fi dovedite în sistem. Prin urmare, p este „ adevărat ” ( p spune că nu poate fi dovedit și, de fapt, nu poate fi dovedit), dar tocmai nu poate fi dovedit formal în sistem. Rețineți că adăugarea p la lista axiomelor nu ar ajuta la rezolvarea problemei: ar exista o altă afirmație Gödel similară construibilă în sistemul extins.

Potrivit lui Roger Penrose, această diferență între „ceea ce poate fi dovedit mecanic ” și „ceea ce poate fi recunoscut ca fiind adevărat de oameni” arată că inteligența umană nu are o natură algoritmică. Această credință este susținută și de JR Lucas în Minds, Machines și Gödel .

Această viziune nu este în general împărtășită deoarece, așa cum a susținut Marvin Minsky , inteligența umană poate face greșeli și poate include afirmații care sunt de fapt inconsistente sau false. Cu toate acestea, Marvin Minsky a spus că Kurt Gödel i-a spus personal despre credința sa în faptul că ființele umane au un mod intuitiv , nu doar de calcul, de a ajunge la adevăr și că, prin urmare, teorema sa nu pune limite la ceea ce poate fi recunoscut. adevărat de la om.

Întrebarea dacă teorema ar arăta capacitatea oamenilor de a transcende logica formală trece de la matematică la filosofie . Dacă nu ar fi cu adevărat posibil să știm din exterior dacă afirmația p este adevărată în cazul în care sistemul este coerent, nu ar exista nicio posibilitate de încredere chiar și în teorema în sine.

«Principiul lui Godel se aplică numai sistemelor strict formale, dar nu suntem întotdeauna inserate într-un sistem formal, nu efectuăm un monolog, așa cum o face un sistem formal, suntem animale dialogice. Problema este semantică și nu sintactică și se poate demonstra că principiul lui Godel nu este aplicabil unui univers semantic. "

( Heinz von Foerster [3] )

Tot ce se poate ști din faptul că se află în interiorul sistemului este adevărul următoarei afirmații:

Fie p nu este demonstrabil în sistem, fie sistemul este inconsistent.

Această afirmație poate fi dovedită cu ușurință în cadrul sistemului . De fapt, această demonstrație va fi prezentată schematic.

Schema probei primei teoreme

Principala problemă care trebuie confruntată pentru a dezvolta ideea de dovadă formulată anterior este următoarea: pentru a construi o afirmație p echivalentă cu „ p nu se poate dovedi”, p trebuie să conțină cumva o referință la p , adică pentru sine, care ar putea da naștere cu ușurință unui proces infinit de auto-referință. Stratagema ingenioasă a lui Gödel, folosită mai târziu și de Alan Turing pentru a rezolva problema Entscheidungs , este următoarea.

Pentru început, fiecărei formule sau afirmații care pot fi formulate în sistem i se atribuie un număr unic, care se numește numărul său Gödel . Acest lucru se face astfel încât o conversie mecanică între formule și numerele lor Gödel să poată fi efectuată cu ușurință și invers. Deoarece sistemul considerat este suficient de puternic pentru a putea opera cu numere , acum va fi posibil să funcționăm în același mod și cu formule .

O formulă F ( x ) care conține o singură variabilă liberă x se numește formă declarativă . Când x este înlocuit cu un anumit număr, forma declarativă se transformă într-o afirmație potențial adevărată sau falsă care poate sau nu poate fi demonstrată în sistem. Formele declarative nu sunt enunțuri și, prin urmare, nu pot fi dovedite adevărate sau false. Cu toate acestea, fiecare formă declarativă F ( x ) are propriul număr Gödel care poate fi notat prin scrierea G ( F ). Alegerea variabilei libere utilizate în expresia F ( x ) nu este relevantă pentru atribuirea numărului Gödel G ( F ).

Plecând de la o analiză atentă a axiomelor și regulilor sistemului, putem construi o formă declarativă P ( x ) care traduce următorul concept: x este numărul Gödel al unei propoziții care poate fi dovedit în sistem. În mod formal: P ( x ) poate fi dovedit dacă x este numărul Gödel al unei propoziții demonstrabile, iar negarea sa ¬ P ( x ) poate fi dovedită dacă nu este.

(Deși descrierea de mai sus poate fi considerată suficientă pentru a contura schema probei, din punct de vedere tehnic nu este pe deplin exactă. A se vedea articolul lui Gödel pentru problemă și articolul lui Rosser pentru soluția sa. Este „omega-coerență”.)

În acest moment intervine ideea decisivă: numim o formulă autoindemostrabilă care își afirmă meta-matematic propria nedemonstrabilitate . Aplicând această definiție, o formă declarativă F ( x ) este autoindemestrabilă dacă forma F , aplicată propriului număr Gödel, nu este dovedibilă. Acest concept poate fi definit formal, deoarece putem construi o formă declarativă SU ( z ) a cărei interpretare spune că z este numărul Gödel al unei forme declarative auto-demonstrabile. În mod formal, SU ( z ) este definit ca: fie F ( x ) formula pentru care avem z = G ( F ) și fie y numărul Gödel al enunțului F ( G ( F )), apoi SU ( z ) = ¬P ( y ). În acest moment, declarația introdusă anterior p , poate fi definită ca:

p = SU ( G ( SU )).

Intuitiv, atunci când cineva întreabă dacă p este adevărat, apare întrebarea: "Proprietatea de a fi auto-nedemonstrabilă este ea însăși nedemonstrabilă?" Toate acestea amintesc foarte mult de paradoxul frizerului care spune despre acel frizer care bărbiereste doar pe acei oameni care nu se bărbieresc singuri: cine bărbiereste frizerul?

Să presupunem acum că sistemul nostru axiomatic este consistent.

Dacă p ar fi demonstrabil, atunci SU ( G ( SU )) ar fi adevărat și, prin definiția lui SU , z = G ( SU ) ar fi numărul Gödel al unei forme propoziționale auto-demonstrabile. Prin urmare, SU ar fi auto-demonstrabil, iar acest lucru implică, prin însăși definiția auto-demonstrabilității, că SU ( G ( SU )) nu este demonstrabil, dar aceasta este afirmația noastră p : p nu este demonstrabilă. Această contradicție duce la concluzia că p nu poate fi demonstrabil.

Dacă negația lui p = SU ( G ( SU )) ar fi demonstrabilă, atunci prin definiția lui SU acest lucru ar însemna că z = G ( SU ) nu este numărul Gödel al unei forme autoindemestrabile, ceea ce înseamnă că SU nu o face este auto-demonstrabil. Pentru definirea auto-dovezii, se concluzionează că SU ( G ( SU )) este demonstrabil și, prin urmare, p este demonstrabil. Din nou ajungem la o contradicție. Această ultimă contradicție implică faptul că nici negația lui p nu poate fi dovedită.

Prin urmare, afirmația p nu poate fi nici dovedită, nici respinsă în cadrul sistemului nostru.

Schema probei celei de-a doua teoreme

Sia p l' enunciato indecidibile costruito prima, e si assuma che la coerenza del sistema sia dimostrabile all'interno del sistema stesso. Precedentemente si è mostrato che se il sistema è coerente, allora p non è dimostrabile. La dimostrazione di questa implicazione può essere formalizzata nel sistema stesso, e quindi l'affermazione " p non è dimostrabile", o "¬ P ( p )" può essere dimostrata nel sistema.

Ma quest'ultima affermazione è equivalente allo stesso enunciato p (e questa equivalenza può essere dimostrata nel sistema), quindi p può essere dimostrato nel sistema. Questa contraddizione implica che il sistema deve essere incoerente.

Note

  1. ^ John W. Dawson, Jr., Logical Dilemmas: The Life and Work of Kurt Gödel , p. 70, AK Peters, Wellesley Mass, 1997.
  2. ^ L'idea di fondo della dimostrazione può essere così riassunta: Supponiamo esista una proposizione G la cui interpretazione standard sia "G non è dimostrabile in P". Se , cioè se G fosse dimostrabile in P, G risulterebbe falsa. Ma per il teorema di completezza di Gödel, ogni proposizione dimostrabile in P risulta vera, dunque G non può essere dimostrabile in P e quindi è vera. Quindi -G risulta falsa e, per lo stesso motivo, non può essere dimostrabile in P. Pertanto se esiste una proposizione il cui contenuto è "io non sono dimostrabile in P", tale proposizione risulterà vera ma non dimostrabile.
  3. ^ Trad. it. in Mauro Maldonato, Certe estremità della coscienza. Scritti sul sentimento del limite , Effata Editrice, 2005

Bibliografia

Voci correlate

Altri progetti

Collegamenti esterni

Controllo di autorità Thesaurus BNCF 33340 · LCCN ( EN ) sh85055601 · GND ( DE ) 4021417-5 · BNF ( FR ) cb119412145 (data)
Matematica Portale Matematica : accedi alle voci di Wikipedia che trattano di matematica