Readme.it in English  home page
Readme.it in Italiano  pagina iniziale
readme.it by logo SoftwareHouse.it

Ebook in formato Kindle (mobi) - Kindle File Ebook (mobi)

Formato per Iphone, Ipad e Ebook (epub) - Ipad, Iphone and Ebook reader format (epub)

Versione ebook di Readme.it powered by Softwarehouse.it


Il teorema di incompletezza

Questo teoremasi pu˛ enunciare come segue:

Se un sistema formale S Ŕ consistenteallora l'enunciato C(S) che neesprime la consistenza non Ŕ dimostrabile in S.

Dimostrazione

Una volta stabilito il teorema precedentequesto segue quasibanalmente (se - come sempre - non vogliamo essere troppo rigorosi).
Basta osservare che il teorema di indecidibilitÓci dice che C(S) implica VcioŔ ci dice che se S Ŕ consistente allora esisteun enunciato V vero ma non dimostrabile in S. Orase si dimostrasse C(S)sidimostrerebbe anche Vma questo Ŕ escluso proprio dal primo teorema...
Semplice in modo sconcertantevero?

Breve discussione

A dispetto della 'semplicitÓ'questo di G÷del Ŕ unrisultato della massima importanza: da quando la teoria degli insiemi di Cantorcominci˛ ad avere successoverso la fine del secolo scorsomolti matematicicominciarono ad usarne le tecnicheanche utilizzando considerazioni implicantiinsiemi infiniti. Al comparireall'inizio del secolodei primi paradossi (o antinomiequella di RusselŔ del 1902) i matematici cominciarono a pensare che qualcosa fosse sfuggitoloro di manoe si diedero ad una ricerca volta a garantire che i fondamentidella loro scienza fossero (e rimanessero) indenni da simili contraddizioniintrinseche.
Lo stesso Russelinsieme a Whiteheadcominci˛ a scrivere un'opera monumentalenella quale le regole iniziali dovevano essere scelte con cura proprio perevitare che potessero sorgere paradossi. Quest'opera Ŕ Principia Mathematicacitata proprio da G÷del nel titolo del suo lavoro come esempio di sistemaformale intrinsecamente incompleto!
Un altro tentativo fu fatto da uno dei matematici pi¨ influenti di questoperiodoDavidHilbertche propose un programma che doveva garantire matematicamentela consistenza del sistema. Secondo questo programma occorreva appunto trovareuna dimostrazione 'matematica' della consistenza della matematica (o di almenodi alcune sue aree). ╚ proprio quanto G÷del dimostra essere impossibile!

Attenzione: questo fatto non ha niente ache vedere con una presunta impossibilitÓ assoluta didimostrare la consistenza di un sistema formale con metodi che lotrascendano! Nel 1936 GentzenriuscirÓ a dimostrare che l'aritmetica Ŕ consistentema utilizzandometodi che non sono in alcun modo rappresentabili aritmeticamente. Ma sevogliamo essere rompiscatole fino in fondoil problema con similidimostrazioni Ŕ che utilizzano ipotesi che non sono in sÚ pi¨ 'certe'della stessa consistenza del sistema che si vuole dimostrareconsistente...

Insommail lavoro di G÷del non lascia spazio a chi vorrebbeconsiderare la matematica solo un 'gioco' formale completoconsistente in modoformalmente dimostrabile.
Ma questo fatto lascia maggior libertÓ al matematicoche ormai sa non poteresistere alcun sistema formale che possa imprigionare le sue intuizioni. Ilprocedimento di ricerca della veritÓ Ŕ un fatto creativonon sempre e soloriducibile ad un puro gioco formale. A me personalmente (e - ne sono certo - atanti altri) questa cosa fa piacere.

E per finire...

Per finireuna chicca: un bell'enunciato indecidibileservito caldo caldo!
Devo anche questo a Penrose chenella prefazione alla riedizione inglese delsuo capolavoro The Emperor's New Mind presenta questo enunciatofacilmente comprensibiledella cui veritÓ (con un po' di pazienza) ci siriesce a convincerema che Ŕ indecidibile nell'ambito dell'ordinariaaritmetica!

Prendiamo un numero qualsiasi ed esprimiamolo come somma di potenze di 2eventualmente trasformando in potenze di due anche gli esponenti. Ad esempio:

 
3 = 21 + 1

Ora applichiamo ripetutamente questa semplice procedura:

 
(a) incrementiamo la 'base' di 1
(b) sottraiamo 1

ottenendo:

 
31 + 1
31

ripetiamo (trascurando l'esponente '1'):

 
4
4-1=3=3x40

dove ho esplicitamente scritto la 'base' raggiuntain questocaso '4'cheper ottenere il corretto risultato '3'deve essere elevataall'esponente '0' (ricordo cheper ogni aa0=1). Importanteosservare che da qui in poi la nuova base (cheper l'operazione (a) siincrementa di uno ad ogni passo) non avrÓ pi¨ alcuna influenza sul numeroraggiunto ('3' in questo caso) che d'ora in poi non potrÓ fare altro chediminuire di uno ad ogni passoin virt¨ dell'operazione (b). Continuiamo:

 
3x50
3x50-1=2.

Ci convinciamo senza troppa difficoltÓ che il nostro numerodi partenza alla fine arriva a zero. Questo Ŕ vero per qualunque numero dipartenzain virt¨ del ragionamento 'informale' scritto sopra in grassetto. Sevuoi fare l'esperimento col numero 4=22 ti puoiconvincere in prima persona che il ragionamento Ŕ giusto; armati per˛ dipazienza: si incomincia con 27=33 e si continua con26424161608483110... ma prima di poter ragionare come ho fattopoco fail numero diventa tanto grande che occorrerebbero la bellezza di121.210.625 cifre per esprimerlo in notazione decimale!

Ma quello che Ŕ veramente notevole Ŕ che questo enunciatorappresenta un enunciato indecidibileper la normale procedura di induzioneche si utilizza nell'aritmetica ordinaria.

Tengo a osservare esplicitamente chea dispetto della sua indecidibilitÓquesto enunciato non solo Ŕ veroma abbiamo a disposizione ben tre(!)modi per dimostrarlo! Vediamoli:

  1. In fondo Goodstein il suo teorema l'ha dimostrato!Ha usato una tecnica non riconducibile alla normale procedura di induzionema l'ha dimostrato rigorosamenteanche se al di fuori dell'ordinariaaritmetica.

  2. Kirby e Paris hanno dimostrato che il teorema diGoodstein Ŕ una affermazione di G÷del per il 'sistema formale' dellaprocedura di induzione aritmetica. Segue chese noi crediamo alla validitÓdi questa proceduracrediamo anche (con le stesso grado di certezzapercosý dire) al teorema di Goodstein.
    (Nella terminologia utilizzata nella dimostrazione data quiil nostro programma D 'equivale' alla procedura di induzione aritmetica el'affermazione "il programma Pk(k) nontermina" 'equivale' all'enunciato del teorema di Goodstein. Se credonella validitÓ di Dcredo anche all'affermazione "il programma Pk(k)non termina").

  3. Ci convinciamo che il teorema Ŕ vero seguendo ildiscorso (informale) fatto in precedenza. Credo di poter affermare chechiunque (anche chi Ŕ dotato di poco intuito matematico) possa venirconvinto da quel ragionamentopurchÚ lo capisca.Naturalmente Ŕ lecito richiedere una dimostrazione rigorosae qui sopra neho indicate due.