Categorie
Scienza

Come capire che i teoremi di Incompletezza di Godel e il suo teorema di Completezza non si contraddicono?

Bentornati ad un'altra incredibile edizione delle domande di cultura generale!

Questa volta abbiamo cercato una curiosità scientifica:

Da laico, sembra che il suo I teoremi di incompletezza e il teorema di completezza sembrano contraddirsi a vicenda, ma risulta che sono entrambi veri.

Il teorema di completezza sembra dire ” tutto ciò che è vero è dimostrabile”. Ma i teoremi di incompletezza sembrano mostrare che ci sono “limiti alla dimostrabilità nelle teorie assiomatiche formali”.

Mi sento come se fossi39;sto interpretando male ciò che dicono questi teoremi, e si scopre che non sono42;t si contraddicono. Qualcuno può aiutarmi a capire perché?

Ed ecco le risposte degli esperti:

Il teorema di completezza dice che ogni conseguenza logica degli assiomi è dimostrabile. Questo significa che non ci mancano regole logiche, quelle che abbiamo sono “complete”. Sono sufficienti per dimostrare tutto ciò che potresti sperare di dimostrare.

Il teorema di incompletezza dice che qualsiasi insieme di assiomi è contraddittorio o non può dimostrare alcuna affermazione vera sui numeri. Puoi ancora provare ogni conseguenza logica degli assiomi che hai, ma non puoi mai ottenere abbastanza assiomi per assicurarti che ogni affermazione vera sui numeri sia una conseguenza logica di essi.

In una parola: la completezza dice che ogni conseguenza logica dei tuoi assiomi è dimostrabile, l'incompletezza dice che ci saranno sempre fatti veri che non sono una conseguenza logica dei tuoi assiomi. (Ci sono alcune precisazioni che devi fare quando enuncia con precisione il teorema di incompletezza;si presume che gli assiomi siano computabili e così via.)

theglandcanyon

I due teoremi parlano di due diversi tipi di completezza.

La completezza semantica, come nel teorema di completezza, significa che il sistema di dimostrazione formale riesce a catturare tutto ciò che consideriamo universalmente vero: Per ogni affermazione, se è valida, allora è dimostrabile, cioè non succede che qualcosa valga universalmente ma non possiamo dimostrarlo.

La completezza sintattica, come nel teorema di incompletezza, è talvolta chiamata anche “completezza di negazione” e significa che il sistema di dimostrazione ha un'opinione su tutto: Per ogni affermazione il sistema o prova l'affermazione o la nega, cioè non succede che ci sia un enunciato che il sistema di prova non può decidere sotto forma di prova o confutazione.

Il teorema di incompletezza afferma che per il sistema formale considerato quest'ultimo non è il caso, cioè ci sono infatti enunciati che non sono né dimostrabili o confutabile. In particolare, ci sono frasi vere ma non dimostrabili.

Il punto cruciale che ti manca è che c'è una differenza tra verità e validità:

La verità in logica è sempre relativa a una situazione particolare (a volte chiamata anche modello, struttura o interpretazione); un'affermazione può essere vera in una struttura (es. nei numeri naturali) ma falsa in un'altra (es. per gli interi). Quando elaboriamo una teoria formale, spesso abbiamo in mente un cosiddetto “modello standard” o “interpretazione intenzionale”; per la teoria aritmetica di cui parla il teorema di incompletezza, questa è la struttura dei numeri naturali con la consueta comprensione dei simboli zero, più, ecc. Quando diciamo che un'affermazione è 'vera'senza ulteriori specificazioni, intendiamo che è vero nel modello standard. Ma è importante tenere a mente che questa è solo una comoda abbreviazione, e tecnicamente non ha senso dire che qualcosa è vero senza dire dove dovrebbe essere vero; l'affermazione può essere vera nel modello standard ma falsa in un'altra interpretazione non standard.

Validità, invece, significa verità universale, cioè verità in ogni possibile interpretazione, ed è quindi una proprietà più forte della semplice verità (nel modello standard).

Pertanto, completezza semantica non significa che ogni affermazione che è vera (secondo l'interpretazione standard) è dimostrabile: Significa solo che ogni l'affermazione che è valida (vera sotto ogni possibile interpretazione) è dimostrabile.

Poiché non tutte le affermazioni vere sono automaticamente vere universalmente, potrebbero esserci affermazioni che sono vere nel modello standard ma non universalmente così e quindi anche non dimostrabile.

Ecco perché la completezza semantica non contraddice l'incompletezza sintattica. La combinazione di completezza semantica + incompletezza sintattica ha direttamente la conseguenza che tali modelli non standard, che differiscono significativamente dall'interpretazione intesa ma tuttavia obbediscono a tutti gli assiomi della teoria, esistono effettivamente.

Come hanno affermato molti altri commentatori, non si contraddicono a vicenda. Vediamo perché.

Il teorema di completezza afferma che per una teoria del primo ordine T, se un'affermazione S è vera in tutti i modelli di T, allora T dimostra S.

Il primo teorema di incompletezza afferma che per una teoria del primo ordine T (con un insieme ricorrente enumerabile di assiomi, cioè qualche programma può enumerarne l'elenco possibilmente infinito), se T è coerente e include l'aritmetica di base, allora c'è qualche affermazione vera G sull'aritmetica che T non può dimostrare.

Mettendo insieme questi due teoremi, ciò che impariamo è che esiste un modello di T in cui G non vale. Lo sappiamo perché il teorema di completezza ci dice che se tutti i modelli di T soddisfano G, allora T dimostrerebbe G. Sappiamo anche che questo modello include numeri non standard. Lo sappiamo perché altrimenti avremmo una confutazione di G all'interno dei numeri naturali standard, il che contraddirebbe il fatto che G è vero.

Nota che non otteniamo una contraddizione complessiva combinando i due teoremi. Tutto ciò che otteniamo è che esiste un modello di T con determinate proprietà.

Per favore fatemi sapere se ho sbagliato un dettaglio in quanto sopra spiegazione.

crislith

Sei sulla strada giusta. Questi teoremi non si contraddicono a vicenda, e il teorema di completezza non significa che nessuna affermazione in nessun sistema formale sia dimostrabile o decidibile, significa solo che le affermazioni logicamente valide in un tale sistema hanno qualche prova che è finitamente enumerabile.

Il teorema di incompletezza usa una diversa nozione di completezza, che è che tutte le frasi sono decidibili, e continua a mostrare che se un sistema formale è coerente e soddisfa altri criteri, possiamo sempre costruire dichiarazioni indecidibili in esso, per le quali non ci sono prove o confutazioni. Se possiamo codificare l'aritmetica e i numeri naturali, possiamo usare una codifica di questi numeri per costruire affermazioni indecidibili come “Questa frase è falsa” o l'equivalente formale.

AntiKamniaChemicalCo

Il teorema di completezza si riferisce esclusivamente agli assiomi di logica del primo ordine. Questi non contengono affermazioni matematiche, solo cose simili al modus ponens.

I due teoremi di incompletezza si riferiscono a raccolte di assiomi sufficientemente complicate prese insieme agli assiomi della logica del primo ordine. Un esempio di tale sistema di assiomi è Peano Arithmetic, che è un tentativo di assiomatizzare la teoria dei numeri naturali.

tuba105