>

Il teorema di Gödel sulla logica formale. Curiosità e consigli utili

Teoremi di incompletezza di Gödel

Teoremi di incompletezza di Gödel

Teoremi di incompletezza di Gödel- due teoremi di logica matematica sui limiti fondamentali dell'aritmetica formale e, di conseguenza, di ogni teoria del primo ordine sufficientemente forte.

Il primo teorema afferma che se l'aritmetica formale è coerente, allora contiene una formula inconfutabile e inconfutabile.

Il secondo teorema afferma che se l'aritmetica formale è coerente, allora qualche formula è non derivabile in essa, il che afferma in modo significativo la coerenza di questa teoria.

Il primo teorema di incompletezza di Gödel

L'affermazione del primo teorema di incompletezza di Gödel può essere enunciata come segue:

Se aritmetica formale S è consistente, allora contiene una formula chiusa G tale che né G né la sua negazione ¬G sono derivabili in S .

Nel dimostrare il teorema, Gödel costruì la formula G esplicitamente, a volte è chiamata la formula irrisolvibile di Gödel. Nell'interpretazione standard, la frase G afferma la propria non derivabilità in S. Pertanto, per il teorema di Gödel, se una teoria S è coerente, allora questa formula è effettivamente non derivabile in S e quindi vera nell'interpretazione standard. Quindi, per i numeri naturali, la formula Gè vero, ma non è deducibile in S.

La dimostrazione di Gödel può essere effettuata anche per qualsiasi teoria ottenuta da S aggiungendo nuovi assiomi, ad esempio la formula G come assioma. Pertanto, qualsiasi teoria coerente che sia un'estensione dell'aritmetica formale sarà incompleta.

Per dimostrare il primo teorema di incompletezza, Gödel ha assegnato un numero specifico a ciascun simbolo, espressione e sequenza di espressioni nell'aritmetica formale. Poiché le formule ei teoremi sono enunciati di aritmetica, e le derivazioni formali dei teoremi sono sequenze di formule, divenne possibile parlare di teoremi e dimostrazioni in termini di numeri naturali. Ad esempio, lascia che la formula irrisolvibile di Gödel G ha un numero M, allora è equivalente alla seguente affermazione nel linguaggio dell'aritmetica: "non esiste un tale numero naturale N, Che cosa N c'è un numero di derivazione della formula con numero M". Tale confronto di formule e numeri naturali è chiamato l'aritmetizzazione della matematica ed è stato eseguito per la prima volta da Gödel. Questa idea divenne successivamente la chiave per risolvere molti importanti problemi di logica matematica.

bozzetto di prova

Fissiamo qualche sistema formale PM in cui possono essere rappresentati concetti matematici elementari.

Le espressioni di un sistema formale sono, dall'esterno, sequenze finite di simboli primitivi (variabili, costanti logiche e parentesi o punti) e non è difficile specificare rigorosamente quali sequenze di simboli primitivi sono formule e quali no. Allo stesso modo, da un punto di vista formale, le dimostrazioni non sono altro che sequenze finite di formule (con proprietà strettamente definite). Per considerazioni matematiche, non importa quali oggetti prendere come simboli primitivi, e decidiamo di usare i numeri naturali per questi scopi. Di conseguenza, la formula è una sequenza finita di numeri naturali, la derivazione della formula è una sequenza finita di sequenze finite di numeri naturali. I concetti (asserzioni) matematici diventano così concetti (asserzioni) sui numeri naturali o sulle loro sequenze, e quindi possono essi stessi essere espressi nel simbolismo del sistema PM (almeno in parte). Si può dimostrare, in particolare, che i concetti "formula", "derivazione", "formula derivabile" sono definibili all'interno del sistema PM, ovvero si può recuperare, ad esempio, la formula F(v) in PM con una variabile libera v(il cui tipo è una sequenza numerica) tale che F(v), in un'interpretazione intuitiva, significa: v- formula derivabile. Costruiamo ora una frase indecidibile del sistema PM, cioè la frase UN, per cui nessuno dei due UN, né non A non deducibile, come segue:

Una formula in PM con esattamente una variabile libera il cui tipo è un numero naturale (una classe di classi) verrà chiamata classe di espressione. Organizziamo le espressioni di classe in una sequenza in qualche modo, denota N-e attraverso R(N), e si noti che il concetto di "espressione di classe", così come la relazione di ordinamento R può essere definito nel sistema PM. Sia α un'espressione di classe arbitraria; attraverso [α; N] denotano la formula formata dall'espressione di classe α sostituendo la variabile libera con il simbolo di un numero naturale N. Relazione ternaria X = [si;z.z] risulta definibile anche in PM. Ora definiremo una classe K numeri naturali come segue:

N ∈ K≡ ¬Bew[ R(N);N] (*)

(dove Bew X significa: X- formula derivabile). Poiché tutti i concetti che ricorrono in questa definizione possono essere espressi in PM, lo stesso vale per il concetto K, che è costruito da loro, cioè esiste una tale espressione di classe S che la formula [ S;N], che viene interpretato intuitivamente, significa che un numero naturale N appartiene K. Come espressione di classe, S identico a qualche particolare R(Q) nella nostra numerazione, cioè

S = R(Q)

vale per qualche numero naturale definito Q. Mostriamo ora che la frase [ R(Q);Q] è indecidibile in PM. Quindi, se la frase [ R(Q);Q] si presume derivabile, allora risulta essere vero, cioè, in accordo con quanto detto sopra, Q apparterrà K, cioè, secondo (*), ¬Bew[ R(Q);Q] sarà soddisfatto, il che contraddice la nostra ipotesi. D'altra parte, se la negazione [ R(Q);Q] era derivabile, quindi ¬ N ∈ K, cioè Bew[ R(Q);Q] sarà vero. Quindi, [ R(Q);Q] insieme alla sua negazione sarà derivabile, il che è di nuovo impossibile.

Forma polinomiale

Per ogni teoria coerente T si può specificare un valore intero del parametro K tale che l'equazione (θ + 2 z.z − B 5) 2 + (tu + Tθ − l) 2 + (si + Mθ − e) 2 + (N − Q 16) 2 + ((G + eQ 3 + lQ 5 + (2(e − z.zλ)(1 + G) 4 + λ B 5+λ B 5 Q 4)Q 4)(N 2 − N) + (Q 3 − Bl + l + θλ Q 3 + (B 5 − 2)Q 5)(N 2 − 1) − R) 2 + (P − 2wS 2 R 2 N 2) 2 + (P 2 K 2 − K 2 + 1 - τ 2) 2 + (4(C − KSN 2) 2 + η− K 2) 2 + (R + 1 + HP − H − K) 2 + (UN − (wN 2 + 1)RSN 2) 2 + (2R+ 1 + φ- C) 2 + (Bw + CUN − 2C+ 4αγ − 5γ − D) 2 + ((UN 2 − 1)C 2 + 1 − D 2) 2 + ((UN 2 − 1)io 2 C 4 + 1 − F 2) 2 + (((UN + F 2 (D 2 − UN)) 2 − 1)(2R + 1 + JC) 2 + 1 − (D + oF) 2) 2 + (((z.z + tu + si) 2 + tu) 2 + si − K) 2 = 0 non ha soluzioni in numeri interi non negativi, ma questo fatto non può essere dimostrato in teoria T . Inoltre, per ogni teoria consistente, l'insieme dei valori del parametro K che hanno questa proprietà è infinito e algoritmicamente non enumerabile.

Il secondo teorema di incompletezza di Gödel

Nell'aritmetica formale S, si può costruire una formula che, nell'interpretazione standard, è vera se e solo se la teoria S è consistente. Per questa formula vale l'enunciato del secondo teorema di Gödel:

Se aritmetica formale S è consistente, allora contiene una formula non derivabile che afferma sostanzialmente la consistenza S .

In altre parole, la coerenza dell'aritmetica formale non può essere dimostrata per mezzo di questa teoria. Tuttavia, ci sono prove della coerenza dell'aritmetica formale utilizzando mezzi che sono inesprimibili in essa.

bozzetto di prova

Innanzitutto, viene costruita una formula Contro, esprimendo significativamente l'impossibilità di derivare qualsiasi formula nella teoria S insieme alla sua negazione. Allora l'enunciato del primo teorema di Gödel è espresso dalla formula Contro ⊃ G, Dove G- La formula irrisolvibile di Gödel. Tutti gli argomenti per la dimostrazione del primo teorema possono essere espressi e svolti mediante S, cioè in S la formula è derivabile Contro ⊃ G. Quindi, se S è derivabile Contro, quindi deriviamo in esso e G. Tuttavia, secondo il primo teorema di Gödel, se S è consistente, allora G in esso non è deducibile. Pertanto, se S è coerente, allora la formula Contro.

Appunti

Guarda anche

Collegamenti

  • VA Uspensky Teorema di incompletezza di Gödel. - M.: Nauka, 1982. - 110 p. - (Lezioni popolari sulla matematica).
  • Accademico Yu L. Ershov "Prove in matematica", programma di A. Gordon del 16 giugno 2003
  • AB Sosinsky Il teorema di Gödel // scuola estiva "Matematica moderna". -Dubna: 2006.
  • PJ Cohen Sui fondamenti della teoria degli insiemi // I progressi nelle scienze matematiche. - 1974. - T. 29. - N. 5 (179). - S. 169–176.
  • M. Kordonsky Fine della verità. -ISBN 5-946448-001-04
  • VA Uspensky Il teorema di incompletezza di Gödel e quattro strade che vi conducono // scuola estiva "Matematica moderna". -Dubna: 2007.
  • Zenkin A.A. Principio di condivisione del tempo e analisi di una classe di ragionamento plausibile quasi finito (sull'esempio del teorema di non numerabilità di G. Kantor) // Dan. - 1997. - T. 356. - N. 6. - S. 733-735.
  • Chechulin V.L. Su una breve versione della dimostrazione dei teoremi di Gödel // "Problemi fondamentali di matematica e scienze dell'informazione", materiali del XXXIV seminario della Scuola di Matematica dell'Estremo Oriente intitolato all'Accademico E.V. Zolotova. - Khabarovsk, Russia: 2009. - S. 60-61.

Fondazione Wikimedia. 2010 .

Guarda cosa sono i "teoremi di incompletezza di Gödel" in altri dizionari:

    Questo termine ha altri significati, vedi il Teorema di Gödel. Il teorema di incompletezza di Gödel e il secondo teorema di Gödel [1] sono due teoremi di logica matematica sui limiti fondamentali dell'aritmetica formale e, di conseguenza, qualsiasi ... ... Wikipedia

    I teoremi di incompletezza di Gödel sono due teoremi di logica matematica sull'incompletezza di sistemi formali di un certo tipo. Indice 1 Primo teorema di incompletezza di Gödel 2 Secondo teorema di incompletezza di Gödel ... Wikipedia

    Questo termine ha altri significati, vedi il Teorema di Gödel. Il teorema di Gödel sulla completezza del calcolo dei predicati è uno dei teoremi fondamentali della logica matematica: stabilisce una relazione univoca tra verità logica ... ... Wikipedia

    Nome comune per due teoremi stabiliti da K. Gödel. Il primo G. t. sul n. afferma che in qualsiasi sistema formale coerente contenente un minimo di aritmetica (segni e le solite regole per gestirli), c'è un formalmente indecidibile ... ... Enciclopedia Matematica

L'idea della dimostrazione è costruire un'espressione che ne testimoni

propria indimostrabilità. Questa build può essere eseguita in tre passaggi:

Il primo stadio è l'instaurazione di una corrispondenza tra l'aritmetica formale e l'insieme degli interi (gedelizzazione);

Il secondo stadio è la costruzione di qualche proprietà speciale di cui non si sa se sia o meno un teorema di aritmetica formale;

Il terzo stadio è la sostituzione in invece di x di un certo numero intero associato a se stesso, cioè la sostituzione con questi numeri di tutti

Primo stadio. Godelizzazione dell'aritmetica formale

L'aritmetica formale può essere aritmetizzata (cioè gaedelizzata) nel modo seguente: a ciascuno dei suoi teoremi viene assegnato un certo numero. Tuttavia, poiché ogni numero è anche un teorema, allora ogni teorema può essere considerato, da un lato, come un teorema dell'aritmetica formale, e dall'altro, come un teorema su un insieme di teoremi dell'aritmetica formale, cioè come un metateorema corrispondente alla dimostrazione di un certo teorema.

Quindi, possiamo concludere che il sistema dell'aritmetica formale contiene anche il proprio metasistema.

Presentiamo ora i nostri risultati in modo più concreto e dettagliato.

Innanzitutto, possiamo associare a ciascun simbolo e aritmetica formale una designazione di codice speciale, chiamata in questo caso numero di Gödel

In secondo luogo, assegniamo ad ogni sequenza di caratteri lo stesso numero di Gödel usando una funzione di composizione.Diamo dove sono le sequenze di caratteri che formano

In terzo luogo (e questo è essenziale), ad ogni dimostrazione della sequenza di assiomi e regole di sostituzione (o regole di sostituzione) viene assegnato un numero dove denota la sequenza di teoremi usati nella dimostrazione

Pertanto, qualsiasi dimostrazione in aritmetica formale corrisponde a un certo numero, il suo numero di Gödel, qualsiasi ragionamento in aritmetica formale si trasforma in calcoli sull'insieme dei numeri naturali.

Quindi, invece di manipolare simboli, teoremi, dimostrazioni, puoi usare

calcoli sull'insieme degli interi. Qualsiasi espressione come, ad esempio, la seguente: dimostrabile in aritmetica formale," corrisponde ora a un certo numero, che indicheremo come

Formuliamo la seguente proposizione.

La metaaritmetica formale è contenuta nell'insieme dei numeri naturali, ed è essa stessa contenuta nell'interpretazione dell'aritmetica formale.

Questa situazione con l'aritmetica formale assomiglia alla situazione con il linguaggio naturale: dopotutto, nulla ci impedisce di usarlo per formulare i suoi concetti e regole di base in esso.

Una corretta scelta della funzione consente di effettuare una transizione univoca da A a, cioè di assegnare due diversi numeri-numeri a due diverse prove. Ad esempio, si possono scegliere i numeri di Gödel in modo tale che ogni simbolo dell'alfabeto dell'aritmetica formale abbia un proprio numero primo, come mostrato, ad esempio, nella Tabella. 3.2.

Tabella 3.2

Ogni formula (costituita da simboli variabili da 1 a a sua volta è codificata da una sequenza costituita dai primi numeri primi, cioè il numero

dove è un numero primo.

A sua volta, la dimostrazione, cioè la sequenza di formule, sarà codificata in modo simile dal numero

E viceversa, grazie a questo metodo di costruzione dei numeri, diventa possibile, partendo da un certo numero, scomponendolo in fattori primi (per l'unicità di scomporre i numeri naturali in prodotti di potenze di numeri primi), tornare in due passi agli esponenti, cioè ai simboli primitivi dell'aritmetica formale. Naturalmente, questo è principalmente di importanza teorica, poiché i numeri diventano rapidamente troppo grandi.

in modo che possano essere manipolati. Tuttavia, va notato che la possibilità fondamentale di questa operazione è essenziale.

Esempio. Sia dato il numero T, corrispondente a qualche dimostrazione e rappresentante il prodotto di numeri primi:

Questa scomposizione significa che la dimostrazione del teorema contiene due stadi: uno corrisponde al numero 1981027125 253, e l'altro al numero 1981027125 211. Scomponendo nuovamente in fattori primi ciascuno di questi numeri, otteniamo

Dalla tabella di codifica dell'alfabeto aritmetico formale (Tabella 3.2) troviamo che i nostri numeri di Gödel per Questi due numeri

corrisponderà alla seguente dimostrazione:

La formula segue dalla formula

Così, in metaaritmetica, il valore del numero originale è ottenuto dall'aritmetica formale.

Seconda fase. Lemma di Gödel

Ogni numero T associato a una dimostrazione corrisponde a un teorema dimostrabile in aritmetica formale. L'aritmetica formale "gaudelizzata" è chiamata aritmetica formale aritmetizzata. Poiché ogni assioma e ogni regola dell'aritmetica formale aritmetizzata corrisponde a qualche operazione aritmetica, allora con l'aiuto di un controllo sistematizzato è possibile determinare se un dato numero T corrisponde alla dimostrazione di qualche teorema del Numero T e in questo caso forma una coppia di numeri coniugati. L'espressione e sono coniugate” Rappresentabili nell'aritmetica formale più aritmetizzata. Ciò significa che esiste un numero di Gödel che digitalizza questa affermazione.

Siamo giunti al punto critico della dimostrazione di Gödel. Sia A un'espressione di aritmetica formale aritmetizzata che contiene qualche variabile libera. Invece di esso, puoi fare una sostituzione di qualche termine. In particolare, è possibile sostituire l'espressione A con l'espressione stessa A. In questo caso, l'espressione numerica A svolge contemporaneamente due ruoli diversi (vedi costruzioni sopra

Cantor e Richard): è sia la vera espressione per la sostituzione che il termine risultante. Questa sostituzione speciale sarà indicata come Quindi la formula significa che il numero è il numero di Gödel ottenuto sostituendo - all'espressione A:

Gödel costruisce quindi un'espressione (di cui non si sa se sia un teorema o un non-teorema) in cui introduce questa sostituzione. L'espressione è simile a questa:

Terzo stadio. Sostituzione definitiva

Nell'aritmetica formale aritmetizzata, questa espressione è rappresentata in forma numerica. Sia E il suo numero di Gödel. Poiché l'espressione contiene una variabile libera, abbiamo il diritto di eseguire una sostituzione - sostituendo il numero E e denotando - sostituendo E:

Indichiamo questa seconda espressione con a e il suo numero di Gödel con E. Diamo un'interpretazione dell'espressione e.

Prima interpretazione. Non esiste una coppia del genere per la quale valga simultaneamente quanto segue: da un lato, T è il numero della dimostrazione aritmetizzata del teorema aritmetizzato da solo, e dall'altro, ci sarebbe una sostituzione Ma poiché c'è lo stesso trasformazione come le altre, è rappresentabile in termini e nella loro notazione in codice - numeri di Gödel e, quindi, tale numero esiste. Allora forse il numero T non esiste.

Seconda interpretazione. Non c'è alcuna dimostrazione aritmetizzata T del teorema che sarebbe una sostituzione per E. Quindi, se non c'è una dimostrazione, è perché non è un teorema in sé. Questo porta a una terza interpretazione.

Terza interpretazione. Un'espressione per la quale il numero di Gödel è una -sostituzione di E non è un teorema nell'aritmetica formale aritmetizzata. Ma è qui che sta la contraddizione, poiché per costruzione è esso stesso una sostituzione di E, e il numero per costruzione non è altro che il numero stesso E. Ciò implica l'ultima interpretazione di e.

09sen

Qualsiasi sistema di assiomi matematici, a partire da un certo livello di complessità, è internamente incoerente o incompleto.

Nel 1900 si tenne a Parigi la Conferenza mondiale dei matematici, dove Davide Gilbert(David Hilbert, 1862-1943) ha delineato sotto forma di tesi i 23 compiti più importanti, a suo avviso, che i teorici del ventesimo secolo a venire dovevano risolvere. Il numero due della sua lista era uno di quei semplici problemi che sembrano ovvi fino a quando non si scava un po' più a fondo. In termini moderni, era la domanda: la matematica è sufficiente da sola? Il secondo compito di Hilbert si riduceva alla necessità di dimostrare rigorosamente che il sistema di assiomi - affermazioni di base prese in matematica come base senza dimostrazione - è perfetto e completo, cioè consente la descrizione matematica di tutto ciò che esiste. Era necessario dimostrare che è possibile stabilire un tale sistema di assiomi che, in primo luogo, fossero reciprocamente coerenti e, in secondo luogo, si potesse trarne una conclusione riguardo alla verità o falsità di qualsiasi affermazione.

Facciamo un esempio dalla geometria della scuola. Nella planimetria euclidea standard (geometria su un piano), si può provare incondizionatamente che l'affermazione "la somma degli angoli di un triangolo è 180°" è vera, e l'affermazione "la somma degli angoli di un triangolo è 137° " è falso. Parlando essenzialmente, nella geometria euclidea, qualsiasi affermazione è falsa o vera, e la terza non è data. E all'inizio del ventesimo secolo, i matematici credevano ingenuamente che la stessa situazione dovesse essere osservata in qualsiasi sistema logicamente coerente.

E poi nel 1931 un matematico occhialuto viennese Kurt Godel- ha preso e pubblicato un breve articolo che ha semplicemente ribaltato l'intero mondo della cosiddetta "logica matematica". Dopo lunghi e complessi preamboli matematici e teorici, ha letteralmente stabilito quanto segue. Prendiamo qualsiasi affermazione come: "L'assunzione n. 247 è logicamente indimostrabile in questo sistema di assiomi" e chiamiamola "affermazione A". Quindi, Gödel ha semplicemente dimostrato la seguente straordinaria proprietà di qualsiasi sistema di assiomi:

"Se un'affermazione A può essere dimostrata, allora può essere dimostrata un'affermazione non-A."

In altre parole, se è possibile dimostrare la validità dell'affermazione "l'Assunzione 247 non è dimostrabile", allora è anche possibile provare la validità dell'affermazione "l'Assunzione 247 è dimostrabile". Cioè, tornando alla formulazione del secondo problema di Hilbert, se il sistema di assiomi è completo (cioè ogni sua affermazione può essere dimostrata), allora è incoerente.

L'unico modo per uscire da questa situazione è accettare un sistema incompleto di assiomi. Cioè, dobbiamo sopportare il fatto che nel contesto di qualsiasi sistema logico avremo ancora affermazioni di "tipo A" che sono ovviamente vere o false, e possiamo giudicare la loro verità solo al di fuori del quadro dell'assiomatica che abbiamo adottato. Se non ci sono affermazioni del genere, la nostra assiomatica è contraddittoria e all'interno della sua struttura ci saranno inevitabilmente formulazioni che possono essere sia provate che confutate.

Quindi la formulazione del primo, o debole, teorema di incompletezza di Gödel è: "Ogni sistema formale di assiomi contiene presupposti irrisolti". Ma Gödel non si è fermato qui, formulando e dimostrando il secondo o forte teorema di incompletezza di Gödel: “La completezza logica (o incompletezza) di qualsiasi sistema di assiomi non può essere dimostrata all'interno della struttura di questo sistema. Per dimostrarlo o smentirlo, sono necessari assiomi aggiuntivi (rafforzamento del sistema).

Sarebbe più sicuro pensare che i teoremi di Gödel siano astratti e non ci riguardino, ma solo aree di sublime logica matematica, ma in realtà si è scoperto che sono direttamente correlati alla struttura del cervello umano. Il matematico e fisico inglese Roger Penrose (nato nel 1931) lo ha dimostrato Teoremi di Gödel può essere utilizzato per dimostrare l'esistenza di differenze fondamentali tra il cervello umano e un computer. Il senso del suo ragionamento è semplice. Il computer opera in modo strettamente logico e non è in grado di determinare se l'affermazione A è vera o falsa se va oltre lo scopo dell'assiomatica, e tali affermazioni, secondo il teorema di Gödel, esistono inevitabilmente. Una persona, di fronte a un'affermazione A così logicamente indimostrabile e inconfutabile, è sempre in grado di determinarne la verità o la falsità, sulla base dell'esperienza quotidiana. Almeno in questo, il cervello umano è superiore a un computer incatenato da puri circuiti logici. Il cervello umano è in grado di comprendere tutta la profondità della verità contenuta nei teoremi di Gödel, ma un computer non può mai. Pertanto, il cervello umano è tutt'altro che un computer. È in grado di prendere decisioni e il test di Turing passerà.

I teoremi di incompletezza di Kurt Gödel sono stati un punto di svolta nella matematica del XX secolo. E nei suoi manoscritti, pubblicati dopo la sua morte, si conservava la prova logica dell'esistenza di Dio. In occasione delle ultime letture natalizie, un'interessante relazione su questo patrimonio poco conosciuto è stata fatta dal professore associato del Seminario teologico di Tobolsk, candidato di teologia, sacerdote Dimitri Kiryanov. "NS" ha chiesto di spiegare le idee principali dello scienziato.

I teoremi di incompletezza di Gödel: un buco nella matematica

- Puoi in qualche modo spiegare popolarmente i teoremi di incompletezza di Gödel? Il barbiere rade solo chi non si rade da solo. Il barbiere si rade da solo? Questo famoso paradosso ha qualcosa a che fare con loro?

La tesi principale della prova logica dell'esistenza di Dio, avanzata da Kurt Gödel: "Dio esiste nel pensiero. Ma l'esistenza nella realtà è più grande dell'esistenza nel solo pensiero. Pertanto, Dio deve esistere". Nella foto: l'autore del teorema di incompletezza Kurt Godel con il suo amico, l'autore della teoria della relatività Albert Einstein. Preston. America. 1950

— Sì, certo che l'ha fatto. Prima di Gödel, c'era il problema dell'assiomatizzazione della matematica e il problema di tali frasi paradossali che potevano essere formalmente scritte in qualsiasi lingua. Ad esempio: "Questa affermazione è falsa". Qual è la verità di questa affermazione? Se è vero, allora è falso, se è falso, allora è vero; risultando in un paradosso linguistico. Gödel ha studiato l'aritmetica e ha dimostrato nei suoi teoremi che la sua coerenza non può essere dimostrata dai suoi principi evidenti: gli assiomi di addizione, sottrazione, divisione, moltiplicazione e così via. Abbiamo bisogno di alcuni presupposti aggiuntivi per giustificarlo. Questo si basa sulla teoria più semplice, ma per quanto riguarda quelle più complesse (equazioni fisiche, ecc.)! Per giustificare qualche sistema di ragionamento, siamo sempre costretti a ricorrere a qualche ragionamento aggiuntivo, che non è giustificato nell'ambito del sistema.

Prima di tutto, questo indica i limiti delle pretese della mente umana nella conoscenza della realtà. Cioè, non possiamo dire che costruiremo una sorta di teoria completa dell'universo che spiegherà tutto: una tale teoria non può essere scientifica.

Come si sentono ora i matematici riguardo ai teoremi di Gödel? Nessuno sta cercando di confutarli, in qualche modo andare in giro?

“È come cercare di confutare il teorema di Pitagora. I teoremi hanno una dimostrazione logica rigorosa. Allo stesso tempo, si stanno tentando di trovare limiti all'applicabilità dei teoremi di Gödel. Ma la maggior parte della controversia ruota attorno alle implicazioni filosofiche dei teoremi di Gödel.

Quanto è elaborata la prova di Gödel dell'esistenza di Dio? È finito?

- È stato elaborato in dettaglio, sebbene lo scienziato stesso non abbia osato pubblicarlo fino alla sua morte. Gödel sviluppa un ontologico (metafisico. — "NS") argomento proposto per la prima volta da Anselmo di Canterbury. In forma condensata, questo argomento può essere espresso come segue: “Dio, per definizione, è Colui più grande del quale nulla può essere concepito. Dio esiste nel pensiero. Ma l'esistenza nella realtà è più grande dell'esistenza nel solo pensiero. Pertanto, Dio deve esistere". L'argomentazione di Anselmo fu successivamente sviluppata da René Descartes e Gottfried Wilhelm Leibniz. Quindi, secondo Descartes, pensare l'Essere Perfetto Superiore, che manca di esistenza, significa cadere in una contraddizione logica. Nel contesto di queste idee, Gödel sviluppa la sua versione della dimostrazione; si adatta letteralmente a due pagine. Sfortunatamente, la presentazione della sua argomentazione è impossibile senza introdurre nei fondamenti una logica modale molto complessa.

Naturalmente, l'impeccabilità logica delle conclusioni di Gödel non costringe una persona a diventare credente sotto la pressione della forza dell'evidenza. Non dovremmo essere ingenui e pensare di poter convincere qualsiasi persona ragionevole a credere in Dio mediante argomentazioni ontologiche o altre prove. La fede nasce quando ci si trova faccia a faccia con la presenza evidente della suprema Realtà trascendente di Dio. Ma c'è almeno una persona che l'argomentazione ontologica ha portato alla fede religiosa, ed è lo scrittore Clive Staples Lewis, che lo ha ammesso lui stesso.

Il lontano futuro è il lontano passato

Cosa provavano per lui i contemporanei di Gödel? Era amico di uno dei grandi scienziati?

- L'assistente di Einstein a Princeton testimonia che l'unica persona con cui era amico negli ultimi anni della sua vita era Kurt Gödel. Erano diversi in quasi tutto: Einstein è socievole, allegro e Gödel è estremamente serio, completamente solo e diffidente. Ma avevano una qualità comune: entrambi andavano dritti e sinceri alle questioni centrali della scienza e della filosofia. Nonostante la sua amicizia con Einstein, Gödel aveva la sua visione specifica della religione. Ha rifiutato l'idea di Dio come un essere impersonale, come Dio era per Einstein. In questa occasione Gödel osservava: “La religione di Einstein è troppo astratta, come quella di Spinoza e della filosofia indiana. Il Dio di Spinoza è meno di una persona; il mio Dio è più di una persona; perché Dio può svolgere il ruolo di una persona”. Ci possono essere spiriti che non hanno un corpo, ma possono comunicare con noi e influenzare il mondo”.

Come è finito Gödel in America? In fuga dai nazisti?

- Sì, è venuto in America nel 1940 dalla Germania, nonostante i nazisti lo riconoscessero come un ariano e un grande scienziato, liberandolo dal servizio militare. Lui e sua moglie Adele attraversarono la Russia lungo la Transiberiana. Non ha lasciato ricordi di questo viaggio. Adele ricorda solo la paura costante di notte che si fermeranno e torneranno indietro. Dopo otto anni di vita in America, Gödel divenne cittadino statunitense. Come tutti i richiedenti la cittadinanza, ha dovuto rispondere a domande riguardanti la Costituzione degli Stati Uniti. Essendo una persona scrupolosa, si è preparato per questo esame con molta attenzione. Infine, ha detto di aver trovato un'incoerenza nella Costituzione: "Ho scoperto una possibilità logicamente legittima in cui gli Stati Uniti potrebbero diventare una dittatura". I suoi amici hanno riconosciuto che, indipendentemente dai meriti logici dell'argomentazione di Gödel, questa possibilità era di natura puramente ipotetica e hanno messo in guardia contro lunghe conversazioni sull'argomento durante l'esame.

Gödel ed Einstein usarono le reciproche idee nel lavoro scientifico?

— Nel 1949 Gödel espresse le sue idee cosmologiche in un saggio matematico che, secondo Albert Einstein, fu un importante contributo alla teoria generale della relatività. Gödel credeva che il tempo, "quell'entità misteriosa e allo stesso tempo contraddittoria che costituisce la base del mondo e della nostra stessa esistenza", alla fine sarebbe diventata la più grande illusione. "Un giorno" cesserà di esistere e verrà un'altra forma di essere, che può essere chiamata eternità. Questa idea del tempo ha portato il grande logico a una conclusione inaspettata. Ha scritto: “Sono convinto di un aldilà, indipendentemente dalla teologia. Se il mondo è costruito in modo intelligente, allora ci deve essere un aldilà".

"Il tempo è un'entità contraddittoria." Sembra strano; ha un significato fisico?

Gödel ha mostrato che nell'ambito dell'equazione di Einstein è possibile costruire un modello cosmologico a tempo chiuso, dove il passato remoto e il futuro lontano coincidono. In questo modello, il viaggio nel tempo diventa teoricamente possibile. Sembra strano, ma è matematicamente esprimibile - questo è il punto. Questo modello può o non può avere implicazioni sperimentali. È un costrutto teorico che può o non può essere utile nella costruzione di nuovi modelli cosmologici. La fisica teorica moderna, in particolare la cosmologia quantistica, ha una struttura matematica così complessa che è molto difficile dare a queste strutture una comprensione filosofica univoca. Inoltre, alcune delle sue costruzioni teoriche sono ancora sperimentalmente non verificabili per il semplice motivo che la loro verifica richiede la rivelazione di particelle ad altissima energia. Ricorda come le persone sono andate fuori di testa per il lancio del Large Hadron Collider: i media hanno costantemente spaventato le persone che stava arrivando la fine del mondo. Si stava infatti preparando un serio esperimento scientifico per testare i modelli della cosmologia quantistica e le cosiddette "teorie della grande unificazione". Se fosse possibile rilevare le cosiddette particelle di Higgs, allora questo sarebbe il passo successivo nella nostra comprensione delle prime fasi dell'esistenza del nostro universo. Ma fino a quando non ci saranno dati sperimentali, i modelli concorrenti della cosmologia quantistica continueranno ad essere solo modelli matematici.

Fede e intuito

“…Il mio Dio è più di una persona; poiché Dio può interpretare il ruolo di una persona…” La fede di Gödel è ancora lontana dalla confessione ortodossa?

— Pochissime delle dichiarazioni di Gödel sulla sua fede sono state conservate, sono raccolte a poco a poco. Nonostante Gödel abbia fatto le prime bozze della sua versione dell'argomento già nel 1941, fino al 1970, temendo il ridicolo dei suoi colleghi, non ne parlò. Nel febbraio 1970, sentendo avvicinarsi la sua morte, permise al suo assistente di copiare una versione della sua prova. Dopo la morte di Gödel nel 1978, nei suoi documenti è stata trovata una versione leggermente diversa dell'argomentazione ontologica. La moglie di Kurt Gödel, Adele, ha detto due giorni dopo la morte del marito che Gödel, "sebbene non frequentasse la chiesa, era religioso e leggeva la Bibbia a letto ogni domenica mattina".

Quando parliamo di scienziati come Gödel, Einstein o, diciamo, Galileo o Newton, è importante sottolineare che non erano atei. Hanno visto che dietro l'Universo c'è la Ragione, un certo Potere Superiore. Per molti scienziati, la fede nell'esistenza della Mente Suprema è stata una delle conseguenze della loro riflessione scientifica, e questa riflessione non ha sempre portato all'emergere di una profonda connessione religiosa tra l'uomo e Dio. Riguardo a Gödel, si può dire che sentiva il bisogno di questo collegamento, poiché sottolineava di essere un teista, di pensare a Dio come persona. Ma, naturalmente, la sua fede non può essere definita ortodossa. Era, per così dire, un "luterano domestico".

— Puoi fare degli esempi storici: in che modo diversi scienziati giungono a credere in Dio? Ecco la genetica di Francis Collins, secondo le sue confessioni, lo studio della struttura del DNA ha portato alla fede in Dio...

“Di per sé, la conoscenza naturale di Dio non è sufficiente per la conoscenza di Dio. Non basta scoprire Dio studiando la natura, è importante imparare a conoscerlo attraverso la Rivelazione che Dio ha dato all'uomo. L'avvicinamento alla fede di una persona, che sia o meno uno scienziato, si basa sempre su qualcosa che va oltre le mere argomentazioni logiche o scientifiche. Francis Collins scrive di essere arrivato alla fede all'età di 27 anni dopo una lunga disputa intellettuale con se stesso e sotto l'influenza di Clive Staples Lewis. Due persone si trovano nella stessa situazione storica, nelle stesse condizioni iniziali: una diventa credente, l'altra atea. Lo studio del DNA da solo porta alla credenza nell'esistenza di Dio. L'altro studia e non ci arriva. Due persone guardano l'immagine: una pensa che sia bella e l'altra dice: "Così così, un'immagine normale!" Uno ha gusto, intuizione e l'altro no. Il professore dell'Università umanitaria ortodossa di San Tikhon Vladimir Nikolayevich Katasonov, dottore in filosofia, matematico di prima educazione, afferma: "Nessuna dimostrazione in matematica è possibile senza intuizione: un matematico prima vede un'immagine e poi formula una dimostrazione".

La questione della venuta alla fede di una persona è sempre una questione che va oltre il mero ragionamento logico. Come spiegare cosa ti ha portato alla fede? L'uomo risponde: sono andato al tempio, ho pensato, letto questo e quello, ho visto l'armonia dell'universo; ma il momento più importante, il più eccezionale, in cui una persona prende improvvisamente coscienza di aver incontrato la presenza di Dio, non può essere espresso. È sempre un segreto.

- Riesci a identificare i problemi che la scienza moderna non può risolvere?

- Tuttavia, la scienza è un'impresa sufficientemente sicura, indipendente e ben consolidata per parlare così apertamente. È uno strumento buono e molto utile nelle mani dell'uomo. Dai tempi di Francis Bacon, la conoscenza è davvero diventata una forza che ha cambiato il mondo. La scienza si sviluppa secondo le sue leggi interne: lo scienziato cerca di comprendere le leggi dell'universo e non c'è dubbio che questa ricerca porterà al successo. Ma allo stesso tempo è necessario essere consapevoli dei limiti della scienza. Non bisogna confondere la scienza con quelle questioni ideologiche che possono essere sollevate in relazione alla scienza. I problemi chiave oggi sono collegati non tanto al metodo scientifico quanto agli orientamenti di valore. La scienza nel corso del lungo Novecento è stata percepita dalle persone come un bene assoluto che contribuisce al progresso dell'umanità; e vediamo che il ventesimo secolo è diventato il più crudele in termini di perdite umane. E qui sorge la domanda sui valori del progresso scientifico, della conoscenza in generale. I valori etici non derivano dalla scienza stessa. Un brillante scienziato può inventare un'arma per la distruzione di tutta l'umanità, e qui sorge la questione della responsabilità morale di uno scienziato, a cui la scienza non può rispondere. La scienza non può indicare all'uomo il significato e lo scopo della sua esistenza. La scienza non sarà mai in grado di rispondere alla domanda perché siamo qui? Perché esiste l'universo? Queste domande sono risolte a un diverso livello di conoscenza, come la filosofia e la religione.

— A parte i teoremi di Gödel, ci sono altre prove che il metodo scientifico ha i suoi limiti? Gli stessi scienziati lo riconoscono?

- Già all'inizio del XX secolo i filosofi Bergson e Husserl sottolineavano l'importanza relativa della conoscenza scientifica della natura. È ormai diventata una credenza quasi universale tra i filosofi della scienza che le teorie scientifiche rappresentino modelli ipotetici per spiegare i fenomeni. Uno dei creatori della meccanica quantistica, Erwin Schrödinger, ha affermato che le particelle elementari sono solo immagini, ma possiamo farne a meno. Secondo il filosofo e logico Karl Popper, le teorie scientifiche sono come una rete attraverso la quale cerchiamo di catturare il mondo, non sono come fotografie. Le teorie scientifiche sono in costante sviluppo e cambiamento. I creatori della meccanica quantistica, come Pauli, Bohr, Heisenberg hanno parlato dei limiti del metodo scientifico. Pauli scriveva: "...Fisica e psiche possono essere considerate come aspetti aggiuntivi di una stessa realtà" - e si soffermava sull'irriducibilità dei livelli superiori dell'essere a quelli inferiori. Varie spiegazioni coprono ogni volta solo un aspetto della materia, ma una teoria completa non sarà mai raggiunta.

La bellezza e l'armonia dell'universo presuppongono la possibilità della sua conoscenza con metodi scientifici. Allo stesso tempo, i cristiani hanno sempre compreso l'incomprensibilità del mistero dietro questo universo materiale. L'universo non ha fondamento in sé e indica la fonte perfetta dell'essere: Dio.

Ecologia della vita. Scienza e scoperta: il teorema di incompletezza di Gödel, uno dei teoremi più famosi della logica matematica, è fortunato e sfortunato allo stesso tempo. In questo è simile alla teoria della relatività ristretta di Einstein. Da un lato, quasi tutti ne hanno sentito parlare. Da un'altra interpretazione, la teoria di Einstein "dice che tutto nel mondo è relativo".

Teorema Gödel sull'incompletezza, uno dei teoremi più famosi della logica matematica, fu fortunato e sfortunato allo stesso tempo. In questo è simile alla teoria della relatività ristretta di Einstein.

Da un lato, quasi tutti ne hanno sentito parlare. D'altra parte, nell'interpretazione popolare La teoria di Einstein, come è noto, " dice che tutto nel mondo è relativo". UN Teorema di incompletezza di Gödel(di seguito semplicemente TGN), approssimativamente nella stessa formulazione popolare libera, " dimostra che ci sono cose incomprensibili per la mente umana».

E ora alcuni stanno cercando di adattarlo come argomento contro il tappeto serialismo , mentre altri, al contrario, dimostrano con il suo aiuto, che non c'è dio . È divertente non solo che entrambe le parti non possano avere ragione allo stesso tempo, ma anche che né l'una né l'altra si preoccupino di capire cosa, in effetti, dice questo teorema.

E allora? Di seguito cercherò di "sulle dita" per parlarne. La mia esposizione, ovviamente, non sarà rigorosa e intuitiva, ma chiederò ai matematici di non giudicarmi rigorosamente. È possibile che per i non matematici (a cui, appunto, appartengo anche io), ci sia qualcosa di nuovo e utile in quanto raccontato di seguito.

La logica matematica è davvero una scienza piuttosto complicata e, soprattutto, poco familiare. Richiede manovre attente e rigorose, in cui è importante non confondere il realmente provato con il fatto che "è già chiaro". Tuttavia, spero che per comprendere il seguente "schema della dimostrazione di TGN", il lettore abbia bisogno solo di conoscenze di matematica / informatica scolastica, capacità di pensiero logico e 15-20 minuti di tempo.

Semplificando un po', TGN afferma che in linguaggi sufficientemente complessi ci sono affermazioni non dimostrabili. Ma in questa frase, quasi ogni parola ha bisogno di una spiegazione.

Iniziamo cercando di capire cos'è una dimostrazione. Prendiamo qualche problema scolastico in aritmetica. Ad esempio, sia necessario dimostrare la correttezza della seguente semplice formula: “∀x(x−1)(x−2)−2=x(x−3)” (ricordiamo che il simbolo ∀ si legge “per qualsiasi” ed è chiamato “quantificatore universale”). Può essere dimostrato trasformando in modo identico, diciamo, in questo modo:

    ∀x(x−1)(x−2)−2=x(x−3)

    ∀xx2−3x+2−2=x2−3x

    ∀xx2−3x–x2+3x=0

    ∀x0=0

    VERO

Il passaggio da una formula all'altra avviene secondo alcune regole ben note. Il passaggio dalla 4a formula alla 5a è avvenuto, diciamo, perché ogni numero è uguale a se stesso - tale è l'assioma dell'aritmetica. E l'intera procedura di dimostrazione, quindi, traduce la formula nel valore booleano VERO. Il risultato potrebbe essere FALSO - se confutassimo qualche formula. In questo caso, dimostreremmo la sua negazione. È possibile immaginare un programma (e tali programmi sono effettivamente scritti) che dimostrerebbe tali (e più complesse) proposizioni senza l'intervento umano.

Affermiamo la stessa cosa un po' più formalmente. Supponiamo di avere un insieme costituito da stringhe di caratteri di qualche alfabeto, e ci sono regole in base alle quali un sottoinsieme S può essere selezionato da queste stringhe le cosiddette dichiarazioni - cioè frasi grammaticalmente significative, ognuna delle quali è vera o falsa. Possiamo dire che esiste una funzione P che assegna uno dei due valori alle affermazioni di S: TRUE o FALSE (ovvero le mappa a un insieme booleano B di due elementi).

Chiamiamo questa coppia- un insieme di istruzioni S e una funzione P da >S a B - "linguaggio delle dichiarazioni". Si noti che nel senso quotidiano il concetto di linguaggio è in qualche modo più ampio. Ad esempio, la frase russa " Bene, vieni qui!"non è né vero né falso, cioè, dal punto di vista della logica matematica, non è un enunciato.

Per quanto segue, abbiamo bisogno della nozione di algoritmo. Non ne darò qui la definizione formale: questo ci porterebbe molto lontano. Mi limiterò all'informale: "algoritmo" è una sequenza di istruzioni univoche ("programma"), che, in un numero finito di passaggi, traduce i dati iniziali in un risultato.

Il corsivo è di fondamentale importanza: se il programma si blocca su alcuni dati iniziali, non descrive l'algoritmo. Per semplicità e in applicazione al nostro caso, il lettore può considerare che un algoritmo è un programma scritto in qualsiasi linguaggio di programmazione a lui noto, che, per qualsiasi dato di input da una data classe, è garantito per completare il suo lavoro con un risultato booleano.

Domandiamoci: per ogni funzione P esiste un “algoritmo di dimostrazione” (o, in breve, “ deducibili”) equivalente a questa funzione, ovvero convertire ogni istruzione esattamente nello stesso valore booleano di it? Più sinteticamente, la stessa domanda può essere formulata come segue: Ogni funzione su un insieme di proposizioni è calcolabile?

Come puoi già intuire, dalla validità di TGN segue che no, nessuna - ci sono funzioni non calcolabili di questo tipo. In altre parole, Non tutte le affermazioni corrette possono essere dimostrate.

Può benissimo essere che questa affermazione ti provochi una protesta interna. Ciò è dovuto a diverse circostanze. In primo luogo, quando ci viene insegnata la matematica a scuola, a volte c'è una falsa impressione dell'identità quasi completa delle frasi "Il teorema X è vero" e "È possibile dimostrare o verificare il teorema X".

Ma se ci pensi, non è affatto scontato. Alcuni teoremi sono dimostrati in modo abbastanza semplice (ad esempio, enumerando un piccolo numero di opzioni) e alcuni sono molto difficili. Ricordiamo, ad esempio, il famoso grande Il teorema di Fermat:

Non esistono x,y,z e n>2 naturali tali che xn+yn=zn,

la cui prova è stata trovata solo tre secoli e mezzo dopo la prima formulazione (ed è tutt'altro che elementare). CON È necessario distinguere tra la verità di un enunciato e la sua dimostrabilità. Non segue da nessuna parte che non ci siano affermazioni vere, ma non dimostrabili (e non completamente verificabili).

Il secondo argomento intuitivo contro TGN è più sottile. Supponiamo di avere un'affermazione non dimostrabile (nell'ambito di questa deduzione). Cosa ci impedisce di accettarlo come un nuovo assioma? Pertanto, complicheremo leggermente il nostro sistema di prove, ma questo non è terribile.

Questo argomento sarebbe perfettamente corretto se ci fosse un numero finito di proposizioni non dimostrabili. In pratica, potrebbe accadere quanto segue: dopo aver postulato un nuovo assioma, ti imbatterai in una nuova affermazione non dimostrabile. Prendilo come un altro assioma: ti imbatterai nel terzo. E così all'infinito.

Dicono che la deduzione rimarrà incompleta. Possiamo anche adottare misure energiche in modo che l'algoritmo di dimostrazione termini dopo un numero finito di passaggi con qualche risultato per qualsiasi affermazione del linguaggio. Ma allo stesso tempo inizierà a mentire - portare alla verità per affermazioni errate, oa bugie - per i fedeli.

In tali casi, si dice che il deduttivo è incoerente. Così, un'altra formulazione del TGN suona così: Esistono linguaggi proposizionali per i quali è impossibile una deduzione coerente completa.- da qui il nome del teorema.

A volte chiamato "teorema di Gödel" è l'affermazione che qualsiasi teoria contiene problemi che non possono essere risolti all'interno della struttura della teoria stessa e richiedono la sua generalizzazione. In un certo senso questo è vero, anche se una tale formulazione oscura la questione piuttosto che chiarirla.

Noto anche che se stessimo parlando delle solite funzioni che mappano l'insieme di numeri reali in esso, allora la "non calcolabilità" della funzione non sorprenderebbe nessuno (basta non confondere "funzioni calcolabili" e "numeri calcolabili" - queste sono cose diverse).

Kurt Godel

Qualsiasi scolaro sa che, diciamo, nel caso della funzione sin⁡x, devi essere molto fortunato con l'argomento in modo che il processo di calcolo dell'esatta rappresentazione decimale del valore di questa funzione termini in un numero finito di passi.

E molto probabilmente lo calcolerai usando una serie infinita, e questo calcolo non porterà mai a un risultato esatto, anche se può avvicinarsi quanto vuoi - semplicemente perché il valore del seno della maggior parte degli argomenti è irrazionale. TGN ci dice semplicemente che anche tra funzioni i cui argomenti sono stringhe e i cui valori sono zero o uno, esistono anche funzioni non calcolabili, sebbene disposte in modo completamente diverso.

Per quanto segue, descriveremo il "linguaggio dell'aritmetica formale". Si consideri una classe di stringhe di testo di lunghezza finita, costituita da numeri arabi, variabili (lettere dell'alfabeto latino) che assumono valori naturali, spazi, segni di operazioni aritmetiche, uguaglianza e disuguaglianza, quantificatori ∃ (“esiste”) e ∀ (“per any") e, forse, qualche altro simbolo (il loro numero esatto e la loro composizione non sono importanti per noi).

È chiaro che non tutte queste righe sono significative (ad esempio, "12=+∀x>" non ha senso). Il sottoinsieme di espressioni significative di questa classe (ovvero stringhe che sono vere o false in termini di aritmetica ordinaria) sarà il nostro insieme di istruzioni.

Esempi di istruzioni aritmetiche formali:

    1=1

    2×2=5

    ∃xx>3

    ∀y∀zy×z>y+ z.z

eccetera. Ora chiamiamo una "formula con un parametro libero" (FSP) una stringa che diventa un'istruzione se un numero naturale viene sostituito in essa come questo parametro. Esempi di FSP (con parametro x):

    x=0

    2x2=x

    ∃yx+y>x

eccetera. In altre parole, gli FSP sono equivalenti a funzioni di un argomento naturale con un valore booleano.

Indichiamo l'insieme di tutti gli FSP con la lettera F. È chiaro che può essere ordinato (ad esempio, prima scriviamo formule di una lettera in ordine alfabetico, seguite da formule di due lettere, ecc.; non è fondamentale per noi quale alfabeto avverrà l'ordinamento). Pertanto, qualsiasi FSP corrisponde al suo numero k nell'elenco ordinato e lo indicheremo con Fk.

Passiamo ora a uno schizzo della dimostrazione di TGN nella seguente formulazione:

Per il linguaggio proposizionale dell'aritmetica formale, non esiste una deduzione coerente completa.

Dimostreremo per assurdo.

Quindi supponiamo che esista un tale deduttivo. Descriviamo il seguente algoritmo ausiliario A, che associa un numero naturale k a un valore booleano come segue:

1. Trova la formula k-esima nella lista F.

2. Sostituisci il numero k come argomento.

3. Applichiamo il nostro algoritmo di dimostrazione all'affermazione ricevuta (secondo la nostra ipotesi, esiste), che la traduce in VERO o FALSO.

4. Applicare la negazione logica al risultato.

In poche parole, l'algoritmo restituisce il valore TRUE se e solo se il risultato della sostituzione nell'FSP del proprio numero nella nostra lista fornisce un'affermazione falsa.

Qui arriviamo all'unico punto in cui chiederò al lettore di credermi sulla parola.

Ovviamente, sotto l'ipotesi di cui sopra, qualsiasi FSP da F può essere associato a un algoritmo contenente un numero naturale in ingresso e un valore booleano in uscita.

Meno ovvio è il contrario:

Lemma: qualsiasi algoritmo che converte un numero naturale in un valore booleano corrisponde a qualche FSP dell'insieme F.

La dimostrazione di questo lemma richiederebbe almeno una definizione formale, non intuitiva, della nozione di algoritmo. Tuttavia, se ci pensi un po ', è abbastanza plausibile.

In effetti, gli algoritmi sono scritti in linguaggi algoritmici, tra i quali ce ne sono di esotici come, ad esempio, Brainfuck, che consiste di otto parole di un carattere, in cui, tuttavia, è possibile implementare qualsiasi algoritmo. Sarebbe strano se il linguaggio più ricco di formule aritmetiche formali che abbiamo descritto risultasse più povero, anche se, senza dubbio, non è molto adatto alla programmazione ordinaria.

Dopo aver superato questo luogo scivoloso, arriviamo rapidamente alla fine.

Quindi, sopra abbiamo descritto l'algoritmo A. Secondo il lemma che ti ho chiesto di credere, esiste un FSP equivalente. Ha un numero nella lista F - diciamo n. Chiediamoci, quanto è uguale a Fn(n)? Lascia che sia VERO. Quindi, per la costruzione dell'algoritmo A (e, quindi, della funzione equivalente Fn), ciò significa che il risultato della sostituzione del numero n nella funzione Fn è FALSO.

Il contrario viene controllato nello stesso modo: Fn(n)=FALSE implica Fn(n)=TRUE. Siamo arrivati ​​a una contraddizione, il che significa che l'ipotesi originaria è sbagliata. Pertanto, per l'aritmetica formale, non esiste una deduzione coerente completa. Q.E.D.

Qui è opportuno ricordare Epimenide, il quale, come sapete, dichiarò che tutti i cretesi sono bugiardi, essendo egli stesso cretese. In una formulazione più concisa, la sua affermazione (nota come il "paradosso del bugiardo") può essere formulato così: io mento". È precisamente tale affermazione, che essa stessa proclama la sua falsità, che abbiamo utilizzato per la prova.

In conclusione, voglio sottolineare che TGN non afferma nulla di particolarmente sorprendente. Dopotutto, tutti sono abituati da tempo al fatto che non tutti i numeri possono essere rappresentati come un rapporto di due numeri interi (ricordate, questa affermazione ha una dimostrazione molto elegante che ha più di duemila anni?).E le radici dei polinomi con coefficienti razionali inoltre non sono tutti numeri . E ora si è scoperto che non tutte le funzioni di un argomento naturale sono calcolabili.

Lo schizzo della dimostrazione data era per l'aritmetica formale, ma non è difficile vedere che THN si applica anche a molti altri linguaggi proposizionali. Certo, non tutte le lingue sono così. Ad esempio, definiamo un linguaggio come questo:

"Qualsiasi frase in lingua cinese è un'affermazione vera se è contenuta nel libro delle citazioni del compagno Mao Tse Tung, ed è errata se non è contenuta."

Quindi il corrispondente algoritmo di dimostrazione completo e coerente (può essere chiamato "deduttivo dogmatico") assomiglia a questo:

“Sfoglia il libro delle citazioni del compagno Mao Tse Tung finché non trovi l'affermazione che stai cercando. Se viene trovato, allora è vero, e se il libro delle citazioni è finito e l'affermazione non viene trovata, allora è falso.

Qui siamo salvati dal fatto che ogni citazione è ovviamente finita, quindi il processo di "prova" finirà inevitabilmente. Pertanto, TGN non è applicabile al linguaggio delle affermazioni dogmatiche. Ma stavamo parlando di linguaggi complessi, giusto? pubblicato