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

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

  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

Relazione rappresentabile

modifica

  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

  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

  Definizione

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

  1.  ;
  2.  .

Ricorsività

modifica

  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

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.

ω-coerenza

modifica

  Definizione

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

Lemma di coerenza

modifica

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

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

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

Predicato di dimostrabilità

modifica

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  .

Proprietà

modifica

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  .