Vai al contenuto

Logica matematica/Incompletezza/Teoremi di incompletezza di Gödel

Wikibooks, manuali e libri di testo liberi.
Indice del libro


In Logica matematica, i teoremi di incompletezza di Gödel sono due famosi teoremi dimostrati da Kurt Gödel nel 1931. Essi fanno parte dei teoremi limitativi, che precisano cioè le proprietà che i sistemi formali non possono avere.

Definizioni preliminari

[modifica | modifica sorgente]

Definizione

  • Sia un sistema formale costruito su un linguaggio del primo ordine , dove è l'insieme degli assiomi di e è l'insieme delle sue regole d'inferenza; è l'alfabeto di e l'insieme delle sue formule ben formate.
  • Sia , il simbolo che lo denota in è rappresentato da , dove è l'alfabeto di .
  • Sia una relazione -aria. In teoria degli insiemi, essa è definita come l'insieme delle liste numerate di lunghezza (-uple), tali che esse siano in grado di soddisfare una determinata proprietà . è il dominio degli elementi , cioè , per ogni .
  • Sia una funzione -aria.

Rappresentabilità

[modifica | modifica sorgente]

Relazione rappresentabile

[modifica | modifica sorgente]

Definizione

è rappresentabile in sse esiste una formula , contenente esattamente variabili libere , tale che, per ogni -upla di elementi :

  1. se , allora ;
  2. se , allora .

Dove indica la sostituzione di ogni variabile con il simbolo , per ogni . Si dice allora che la formula rappresenta la relazione .

Relazione semi-rappresentabile

[modifica | modifica sorgente]

Definizione

è semi-rappresentabile (o debolmente rappresentabile) in sse esiste una formula , contenente esattamente variabili libere , tale che, per ogni -upla di elementi , sse .

Funzione rappresentabile

[modifica | modifica sorgente]

Definizione

è rappresentabile in sse esiste una formula , contenente esattamente variabili libere , tale che, per ogni -upla di elementi , se , allora:

  1. ;
  2. .

Ricorsività

[modifica | modifica sorgente]

Definizione

Una funzione è detta ricorsiva sse essa è esprimibile mediante la teoria della ricorsività. Una relazione (o un insieme) è ricorsiva sse la sua funzione caratteristica è ricorsiva.

  • L'insieme delle formule ben formate di un sistema formale , essendo definito induttivamente, è ricorsivo.
  • Sia l'unione di tutti gli insiemi di tutte le sequenze (-uple) di lunghezza contenenti formule, per ogni . L'insieme delle dimostrazioni di può essere definito induttivamente.
Sia l'insieme degli assiomi di e l'insieme delle sue regole d'inferenza. L'insieme è così definito:
  1. sse ;
  2. sse e , oppure è conseguenza diretta di qualche -upla (i cui elementi sono in ) per qualche .

Gödelizzazione

[modifica | modifica sorgente]

Sia ora una funzione ricorsiva e iniettiva, detta numero di Gödel (in onore al grande logico). La funzione non fa altro che assegnare univocamente ad ogni stringa di , e ad ogni sua sequenza di stringhe (l'insieme ), uno ed un solo numero naturale, detto appunto numero di Gödel o gödeliano. Essendo una funzione iniettiva, essa è invertibile, dunque esiste . Supponiamo che anche sia ricorsiva.

A partire da questa funzione, possiamo ora definire una relazione () e una funzione sui numeri naturali (), a loro volta ricorsive:

Definizione

  • la relazione è definita come . In sostanza, il predicato codifica la relazione "", cioè, vale sse dimostra , ovvero, sse è una dimostrazione in e .
  • la funzione è definita come , cioè, la funzione restituisce il gödeliano della formula ottenuta sostituendo nella formula di gödeliano il simbolo (numerale) di al posto della variabile libera di gödeliano . In sostanza, la funzione aritmetizza la sostituzione di un numerale al posto di una variabile libera in una formula.

e sono ricorsive, essendo definite a partire da funzioni o insiemi ricorsivi, quali , , e , e non contenendo quantificatori nelle loro definizioni.

Definizione

Un sistema formale è ω-coerente sse non esiste una formula tale per cui e, per ogni , .

Lemma di coerenza

[modifica | modifica sorgente]

Se è ω-coerente, allora è coerente.

Dimostrazione

Se fosse incoerente, allora, per definizione, dimostrerebbe qualsiasi formula, pertanto varrebbe, per ogni formula , e, per ogni , . Quindi, se è incoerente, allora è anche ω-incoerente, dunque, per contrapposizione, la tesi è dimostrata.

Primo Teorema di incompletezza

[modifica | modifica sorgente]

Sia un sistema formale in grado di rappresentare le funzioni ricorsive, allora esiste una formula tale per cui:

  1. se è coerente, allora ;
  2. se è ω-coerente, allora .

Dunque, se si verificano tali condizioni, è sintatticamente incompleto.

Dimostrazione

[modifica | modifica sorgente]

Essendo in grado di rappresentare funzioni ricorsive, esso può esprimere la relazione e le funzioni e all'interno del suo linguaggio , che conterrà i simboli di predicato e di funzione , e .

Consideriamo la formula di , contenente libera la variabile :

afferma che non esiste una dimostrazione in per la formula ottenuta dalla formula di gödeliano , sostituendo (all'interno di essa) le occorrenze libere della variabile il cui gödeliano è (cioè ) con il gödeliano della formula stessa, cioè . In breve, essa afferma che la formula ottenuta da tale sostituzione non è dimostrabile.

Supponiamo ora che sia il gödeliano di , cioè: .

Eseguiamo la seguente sostituzione su : sostituiamo la variabile con il numerale di . Otteniamo così la formula chiusa :

afferma che non esiste una dimostrazione in per la formula ottenuta dalla formula di gödeliano , sostituendo (all'interno di essa) le occorrenze libere della variabile con il gödeliano della formula stessa, cioè . In pratica, afferma che la formula che si ottiene tramite tale sostituzione non è dimostrabile, ma tale formula è esattamente , dato che , quindi abbiamo che . Dunque, afferma di non essere un teorema, cioè, è l'aritmetizzazione dell'enunciato metamatematico che afferma l'indimostrabilità di .

  1. Supponiamo che valga , allora esiste un tale per cui esso è il gödeliano di una dimostrazione di . Essendo rappresentabile in , vale . Ma, essendo che , abbiamo che , dunque . Perciò, se è dimostrabile, allora è incoerente.
  2. Supponiamo che sia ω-coerente, ma che, per assurdo, valga , allora abbiamo che . Essendo ω-coerente, per il lemma di coerenza esso è anche coerente, dunque, per il punto 1, vale , cioè . Quindi, essendo rappresentabile in , abbiamo che, per ogni , . Dunque, valendo sia che per ogni , segue che è ω-incoerente, contraddicendo l'ipotesi iniziale.

Perciò, se è ω-coerente, allora è indecidibile all'interno di stesso.

Secondo Teorema di incompletezza

[modifica | modifica sorgente]

Predicato di dimostrabilità

[modifica | modifica sorgente]

Supponiamo che sia il predicato che descrive la proprietà "essere un teorema", in relazione ad una formula (e dunque un gödeliano). Detto formalmente,

ovvero, il predicato è vero sse esiste un tale per cui esso è il gödeliano che rappresenta una dimostrazione della formula rappresentata da .

Per ogni formula , sia .

Il predicato unario , per essere considerato valido, deve godere delle seguenti proprietà.

Date due formule :

T1. Se , allora ;

T2. ;

T3.;

T4. Se , allora .