Teorema lui Gödel

pe tema: "Teorema lui Goedel"

În 1951 Kurt Gödel a primit cea mai înaltă distincție științifică din SUA - premiul Einstein. Într-un articol dedicat acestui eveniment, un alt matematician major al vremii noastre, John von Neumann, a scris [1]. "Contribuția lui Kurt Gödel la logica modernă este cu adevărat monumentală. Acesta este mai mult decât un monument. Acesta este un punct de reper care împarte cele două epoci ... Fără nici o exagerare, se poate spune că lucrarea lui Gödel a schimbat radical subiectul logicii ca știință ".







Teorema lui Gödel despre incompletență

Prima teorema incompletenței

Prima teoremă a lui Gödel despre incompletență. cel mai probabil, este cel mai semnificativ rezultat al logicii matematice. Se citește după cum urmează:

Pentru orice teorie formală și calculabilitate coerente, care se pot dovedi situațiile aritmetice de bază poate fi construit declarația istinnoearifmeticheskoe adevărul care nu poate fi dovedită în cadrul teoriei [1]. Cu alte cuvinte, orice teorie destul de utilă, suficientă pentru a reprezenta media aritmetică nu poate fi atât de coerente și complete.

Aici cuvântul „teorie“ înseamnă „set infinit“ declarații, dintre care unele se bazează adevărate fără dovezi (astfel de declarații sunt numite axiome), și altele (teorema) pot fi derivate din axiome, și să se bazeze, prin urmare, (dovedit) adevărat. Expresia „demonstrabile în teorie“ înseamnă „ieșire de la axiome si a primitivelor teorie (caractere alfabetice constante) folosind logica standard (prima comanda).“ Teoria este consecventă (coerentă) dacă este imposibil să se dovedească o declarație contradictorie în ea. Expresia „poate fi construit“, înseamnă că există o procedură mecanică (algoritm), care se poate construi o propunere bazată pe axiome, primitivele și logica de prim ordin. "Aritmetica elementară" este existența unor operații de adăugare și multiplicare asupra numerelor naturale. Rezultată afirmație este adevărată, dar nedovedit este adesea indicat pentru o anumită teorie ca o „secvență de Gödel“, dar există un număr infinit de alte declarații în teorie, care au aceeași proprietate: nedovedite în validitatea teoriei.

Presupunerea că teoria calculabilitate, înseamnă că, în principiu, este posibil să se realizeze un algoritm de calculator (program de calculator), care (în cazul în care este permis să se calculeze arbitrar vreya lung până la infinit) se va calcula o listă a tuturor teoreme ale teoriei. De fapt, este suficient să se calculeze doar lista axiomelor și toate teoremele pot fi obținute efectiv dintr-o astfel de listă.

Prima teoremă de incompletitudine a fost intitulat ca „Teorema VI» Articolul de Gödel 1931 Pe Formal indecidabila propozitiile Principia Mathematica și sisteme conexe I. originală de înregistrare Gödel suna ca:

"Concluzia generală despre existența unor propoziții insolubile este după cum urmează:

Pentru fiecare # 969; S-consistent class recursive k formula recursivă există SEMNALE rtakie care nu (v Genr) sau ¬ (v Genr) nu aparțin Flg (k) (unde v este r variabila liberă) [2] ".

Denumirea Flg vine de la ea. Folgerungsmenge - un set de secvențe, Genul vine de la el. Generalizare - generalizare.

Aproape vorbind, afirmația lui Gödel spune: "adevărul lui G nu poate fi dovedit". Dacă G ar putea fi dovedit în cadrul teoriei, atunci teoria ar conține o teoremă care se contrazice și, prin urmare, teoria ar fi contradictorie. Dar dacă G este de neatins, atunci este adevărat și, prin urmare, teoria este incompletă (afirmația lui G nu este deductibilă în ea).

Aceasta este o explicație în limbajul natural obișnuit și, prin urmare, nu este strict matematic strictă. Pentru a furniza o dovadă riguroasă, Gödel a numerotat declarațiile cu ajutorul numerelor naturale. În acest caz, teoria care descrie numere, de asemenea, aparține setului de propoziții. Întrebări despre provability declarațiilor reprezentate în acest caz, sub formă de întrebări cu privire la proprietățile numerelor naturale, care trebuie să fie calculabil, în cazul în care teoria este completă. În aceste condiții, afirmația lui Gödel spune că nu există nici un număr cu anumite proprietăți specifice. Numărul cu această proprietate va fi dovada inconsecvenței teoriei. Dacă există un astfel de număr, teoria este contradictorie contrară ipotezei originale. Deci, presupunând că teoria este consecventă (dupa cum implica ipoteza teoremei), se pare că nu există un astfel de număr, și declarația lui Gödel este adevărat, dar în cadrul acestei teorii nu poate fi dovedită (prin urmare, teoria este incompletă). observație conceptuală importantă este că este necesar să se presupună că teoria este consecventă, pentru a anunța declarația lui Gödel adevărată.







Teoria lui Gödel despre a doua incompletență

A doua teoremă a incompletenței lui Gödel este următoarea:

Pentru orice teorie formală T recursiv enumerable (de exemplu, a generat în mod eficient), inclusiv aritmetice de adevăr declarațiile de bază și anumite afirmații despre provability formale, această teorie T include o declarație cu privire la consistența sa, dacă și numai dacă teoria T este inconsecventă.

Cu alte cuvinte, coerența unei teorii suficient de bogate nu poate fi dovedită prin intermediul acestei teorii. Cu toate acestea, se poate dovedi că consistența unei teorii concrete poate fi stabilită printr-o altă teorie formală mai puternică. Dar atunci se pune întrebarea despre coerența acestei a doua teorii, etc.

Pentru a folosi această teoremă pentru a dovedi că activitatea rațională nu este redusă la calcul, mulți au încercat. De exemplu, în 1961, cunoscutul logician John Lucas (John Lucas) a acționat cu un program similar. Motivația sa sa dovedit a fi destul de vulnerabilă - dar a stabilit sarcina mai larg. Roger Penrose folosește o abordare ușor diferită, care este prezentată complet în carte, "de la zero".

Consecințele teoremei afectează filosofia matematicii, în special formalismele care folosesc logica formală pentru a defini principiile lor. Puteți parafraza prima teorema de incompletitudine, după cum urmează: „este imposibil de a găsi un sistem global de axiome, care ar fi în măsură să dovedească toate adevărurile matematice, și nici minciuni“ Pe de altă parte, din punct de vedere al formalităților stricte, această reformulare nu prea are sens, deoarece implică conceptul de „adevărat“ și „false“ într-un anumit sens, absolut, mai degrabă decât în ​​raport cu fiecare sistem particular.

Dar o astfel de reformulare a celei de-a doua teoreme este și mai îngrijorătoare pentru elementele de bază ale matematicii:

Dacă este imposibil să se dovedească coerența și completitudinea sistemului în sine, atunci acest sistem este inconsecvent.

Prin urmare, pentru a stabili că coerența unui sistem S trebuie utilizat sistem T. mai puternic, dar in cadrul T dovada nu poate fi finalizată în totalitate până când se dovedește consistenta T (în plus, fără a utiliza sistemul de S).

La început se părea că teoremele lui Gödel încă nu lasă prea multă speranță, deoarece este posibil să se creeze un algoritm general care să decidă dacă o afirmație dată este soluționabilă sau nu. Acest algoritm va permite matematicienilor să înșele toate problemele insolubile dintr-o dată împreună. Cu toate acestea, un răspuns negativ la problemele de alegere obținute în 1936 a arătat că un astfel de algoritm nu există.

Unii cercetători au sugerat că o declarație care nu poate fi dovedită în cadrul sistemului deductiv, poate fi un fel destul de demonstrabilă de limbaj meta. Ceea ce nu poate fi dovedit pe acest metaj poate fi, la rândul său, dovedit pe un meta-metaj. și așa mai departe ad infinitum. Prin utilizarea acestor sisteme metalanguages ​​tastate împreună cu axioma de reductibilitate, care, prin ipoteza de inducție se aplică la întregul set de limbi, este posibil ca toate domeniile de cunoștințe pentru a eluda problema incompletitudinii.

De asemenea, trebuie remarcat faptul că teoremele lui Gödel sunt aplicabile numai sistemelor suficient de puternice de axiome. „Suficient de puternic“, în acest context, înseamnă că teoria conține fonduri suficiente pentru a furniza datele necesare pentru dovada primei teoremei de incompletitudine. În mod semnificativ, necesitatea acestei axiome de bază care reprezintă plus și operația de înmulțire, cum ar fi, de exemplu, în aritmetică Robinson Q. sistem axiomă Există mai slab ca complete și coerente, de exemplu, aritmetica Presburger care demonstrează validitatea primei ordine numai relativ aserțiuni plus.

Sistemul de axiome poate conține un număr infinit de axiome (cum ar fi, de exemplu, aritmetica Peano de ordinul întâi), dar pentru teorema lui Gödel să fie aplicabilă unui astfel de sistem. Trebuie să existe un algoritm eficient care să vă permită să verificați corectitudinea. De exemplu, putem lua în considerare setul tuturor declarațiilor de ordinul întâi care sunt adevărate în modelul standard al numerelor naturale. Acest sistem este complet, dar teorema lui Gödel este inaplicabilă în acest caz, deoarece nu există o procedură eficientă care să determine dacă o secvență dată este o axiomă. De fapt, aceasta este consecința primei teoreme a lui Gödel despre incompletență.

Un alt exemplu al teoriei, care nu se aplică teorema de incompletitudine prima lui Gödel poate fi construit după cum urmează: este necesar pentru a sorta toate posibile declarații adevărate despre numere naturale pentru prima dată de lungimea șirului, și apoi lexicografic. În plus, sistemul de axiome este construit astfel încât - inițial luat sistemul de axiome Peano, atunci este necesar să se aleagă o listă aprobată de prima declarație comandă care nu pot fi dovedite. Mai mult, această afirmație este inclusă în lista axiomelor noului sistem. Și așa până la capăt. În cele din urmă, acest proces va crea un sistem formal complet, consistent și suficient de puternic, care, cu toate acestea, nu va fi enumerabil.

Gödel însuși a dovedit versiuni mai slabe din punct de vedere tehnic ale teoremelor. Prima dovadă a teoriei în formulările citate în articol a fost dată de D.B. Rosser în 1936.

În esență, dovada primei teoreme conține procesul de construire a instrucțiunii p în cadrul unui sistem formal, care poate fi descris în metalizat după cum urmează:

p = "Această afirmație nu poate fi dovedită în sistemul formal examinat"

Aparent, aceasta este doar o versiune modernă a paradoxului mincinoșilor, care, spre deosebire de formularea clasică, nu este cu totul paradoxală.

Dacă sistemul axiomelor este consecvent, dovada teoremei lui Gödel arată că p (și negarea sa) nu pot fi dovedite în cadrul sistemului. Prin urmare, declarația p este adevărată (aceasta este afirmația că este imposibil de demonstrat și este într-adevăr de neatins). Dacă sistemul de axiome # 969; este consecventă, atunci negația lui p nu poate fi dovedită, deci p nu este calculată. În sisteme care # 969; -conflictind (dar consecvent), sau există o situație similară sau afirmația ¬p poate fi dovedită.

Adăugarea afirmației p ca axiom nu rezolvă problema, deoarece pentru un astfel de sistem extins va exista o altă afirmație Gödel. Astfel de teorii, cum ar fi aritmetica lui Peano, pentru care nu se poate construi o extindere enumerabilă, sunt în esență incomplete.

hedelith teorema matematică de incompleteness

1. V.A. Adormirea Maicii Domnului. Teorema lui Gödel despre incompletență. - M. Nauka, 1982.







Articole similare

Pagina anterioară

Pagina următoare

Trimiteți-le prietenilor: