Newsgroup: it.cultura.filosofia
Titolo: godel ?

Il teorema di Godel espresso in maniera normale ?

 Il teorema di Godel espresso in maniera normale ?
Aspetta, parla l'ignorante di turno:
La validità di un sistema non può essere dimostrata con elementi interni
al sistema stesso. Questo è il teorema di Godel scolpito con la motosega
in un tronco d'albero... :-)
Qualcuno sarà lieto di fornirti maggiori dettagli.
Saluti
Sinuhe

 Il teorema di Godel espresso in maniera normale ?
La definizione più comprensibile al grande pubblico è quella nel post di
Sinhue.
Se tuttavia hai bisogno dei chiarimenti approfondisco (leggermente, non è
che ne so più tanto) :
I teoremi formulati da Kurt Godel sono 2 :
Il primo riguarda l'aritmetica formale ed è universalmente il più
conosciuto.
 Data una teoria matematica A di cui sia stata aritmetizzata la sintassi,
esso contiene formule B tali che ne B, nè non B, possono essere dimostrate
internamente ad A.
Il secondo teorema, invece è una estensione del primo.
La solita teoria T non può contenere la dimostrazione della consistenza, ma
richiede una teoria più ampia T1, che a sua volta per essere dimostrata
necessiterebbe di T2, continuando all'infinito in una serie infinita di
teorie.
Se vuoi la dimostrazione di Godel fammelo sapere : vedro' cosa posso fare !
                                                             Kosby

 Il teorema di Godel espresso in maniera normale ?
In un sistema formale che comprenda almeno tutte le formule dimostrabili
dall'aritmetica di Peano, e' possibile creare delle formule che non sono
dimostrabili, di cui, cioe', il sistema non possa dichiarare la verita' o la
falsita'. Questo e' ottenuto tramite la diagonalizzazione, un procedimento
cioe' che permette alle formule di essere auto-referenti. In particolare, le
formule auto-referenti indimostrabili possono essere trasformate in precisi
quesiti algebrici, il che' ha come conseguenza che per ogni sistema
matematico formale esistono dei problemi che non possono essere risolti al
suo interno.
Una conseguenza del primo teorema e' che gli unici sistemi in grado di
produrre tutte le formule vere sono quelli incoerenti, cioe' dai quali e'
possibile dimostrare sia una formula sia la sua negazione. Chiaramente,
questi sistemi formali sono inutili.
Questi teoremi forniscono un limite cognitivo molto serio ad ogni nostro
tentativo di comprendere la verita' matematica, in pratica significando che
non arriveremo mai ad esaurire il soggetto.
Ciao,
     Stefano
--
"Si vis pacem, para bellum"
motto romano

 Il teorema di Godel espresso in maniera normale ?
Altri ti han gia` risposto io aggiungo che da Boringhieri trovi
il libretto (ca. 100 pag.) "La prova di Godel" di Nagel e Newman che, per
quanto ne so io, rimane ancora la migliore "divulgazione" di
quei teoremi.
Prima di giungere alla dimostrazione vera e propria gli autori
inquadrano sinteticamente ma bene la situazione prima di Godel.
Dicono gli autori nell'introduzione:
"Le conclusioni cui Godel arrivo` sono oggi riconosciute come
rivoluzionarie nel loro vasto significato filosofico. Scopo di
questo libro e` quello di rendere accessibili anche ai non
specialisti la sostanza delle scoperte di Godel e il carattere
generale della sua prova".
-- 
"Il bilancio dell'opera dei grandi uomini di recente messi in circolazione
 o tolti di mezzo conferma la teoria che sono cavatori di ragni dal buco"
  Bordiga

Grazie a tutti dello sforzo. Speravo in una "favola" d'esempio. So invece
bene che il teorema di per sè richiede un linguaggio preciso ed articolato.
Non so, pensavo a qualcosa di simile a quello che ho sentito per l'antinomia
di Russell (la definizione di barbiere che è colui che ...)



Forse ti potrà essere d'aiuto sapere - posto sempre che tu non lo
sappia già - che la formula G mediante la cui effettiva costruzione
Goedel dimostra l'incompletezza sintattica del sistema formale, dice:
G non è dimostrabile all'interno del sistema formale. Come puoi vedere
si tratta di una sorta di antinomia del mentitore, nella quale però
alla verità è sostituita la dimostrabilità. Insomma, la formula G
afferma di sè la non dimostrabilità all'interno del sistema formale.
Perciò si potrebbe dire che la dimostrazione di Goedel sfrutta
positivamente l'antinomia del mentitore - fermo restando che essa fa
qui riferimento alla dimostrabilità, e non alla verità della formula.
Ti faccio poi presente - casomai non lo sapessi - che esistono
proposizioni matematicamente significative (proprietà dei numeri
naturali) di cui è stata dimostrata l'indimostrabilità nel sistema di
Peano. Posso citare - ad esempio - una forma specifica del teorema
combinatorio di Ramsey. Non so se oltre questa, la matematica ne
conosca altre...
Sul significato "filosofico" - se mai lo ha - del teorema di Goedel,
ci andrei cautamente nell'affermare, come fa Stefano Crispino, che
esso pone <<limiti cognitivi alla nostra capacità di comprenedere la
verità matematica>>. Anche se questa interpretazione è forse in linea
con la fede filosofica platonizzante di Goedel - convinto com'era
della esistenza degli eterni enti logico-matematici, indipendentemente
dal loro essere pensati. Giunse fino a dare una dimostrazione della
necessità dell'esistenza di Dio - naturalmente sulla base
dell'anselmiano argomento ontologico. Già che ci sono: qualcuno
avrebbe la briga di postarla, questa dimostrazione goedeliana dell'
esitenza necessaria dell'Ens necessarium? 
Un saluto,
Marco

 Grazie a tutti dello sforzo. Speravo in una "favola" d'esempio.

Non demoralizzarti, l' idea di fondo del teorema non è affatto
complicata, bisogna solo trovare il giusto modo do vedere le
cose.
Riposto (riveduto e corretto) un messaggio che postai tempo fa a
qualcuno che fece la tua stessa domanda (approposito andrebbe
messa nelle FAQ, se mai esisteranno delle FAQ). Forse la mia
spiegazione è un po' troppo densa di passaggi logici, quindi
andrebbe letta con un po' di pazienza, comunque spero di chiarire
qualche idea anzichè confonderla:
------
Cominciamo con alcuni esempi:
Esempio 0:
Consideriamo un problema aritmetico di questo tipo:
Definisco un insieme di numeri naturali così:
1) A contiene 1
2) se A contiene x allora A contiene anche x+2
Domanda: A contiene 7?
Risposta: sì.
Dimostrazione:
- da (1): A contiene 1
- da (2): A contiene 1 implica che A contiene 1+2=3
- da (2): A contiene 3 implica che A contiene 3+2=5
- da (2): A contiene 5 implica che A contiene 5+2=7 QED
In realtà si può dimostrare che A contiene ogni numero dispari, e
una dimostrazione diretta del tipo scritto sopra sarà tanto più
lunga quanto più grande è il numero.
I numeri pari non sono in A. Ciò equivale a dire che ad esempio 8
non si ottiene mai come risultato dell' iterazione dell'
operazione x+2 partendo da 1. Questo sembra ovvio ma come lo
dimostriamo? Certo non possiamo calcolare tutti gli infiniti
valori della successione e verificare che nessuno di questi è 8.
In realtà in questo caso la dimostrazione non sarebbe neppure
difficile, ma consideriamo questa leggera complicazione del
problema:
Esempio1:
Elenchiamo alcuni numeri "base":
B={10, 56, 789}
e un insieme di operazioni aritmetiche:
X={somma, prodotto, differenza}
PROBLEMA 1: è possibile ottenere il numero 454251 dai numeri base
mediante le operazioni X (con un numero finito di passi)? Si' o
no?
La risposta può non essere ovvia, potremmo avviare un algoritmo
di ricerca mettendoci ad iterare le operazioni. Potrebbe
continuare senza mai finire, oppure dopo molto tempo arrivare al
numero cercato.
Se la risposta al problema è SI' allora il nostro algoritmo di
ricerca del numero terminerà e l' insieme dei passi compiuti
fornirà una dimostrazione diretta del fatto che la risposta è
SI'.
Ma supponiamo che la risposta sia NO: allora l' algoritmo non
terminerà mai la sua ricerca.
Per convincerci che la risposta è NO dovremo inventarci qualcosa
per dimostrarlo in un tempo finito. E' sempre possibile?
(Godel ci dimostra che: per ogni teoria aritmetica coerente
esiste un
problema del tipo appena detto sopra per cui la risposta è NO e
per cui è
impossibile dimostrare entro la teoria che la risposta è NO.)
Esempio 2:
Consideriamo un problema simile al precedente:
Elenchiamo una serie di stringhe simboliche di base:
S={ABAB, ABXY, AA}
e un insieme di procedure per produrre nuove stringhe da quelle
che abbiamo
già ottenuto:
O={la coppia AB si può rimpiazzare con X, la coppia BX si può
rimpiazzare
con AB}
PROBLEMA2: è possibile ottenere la stringa AAB da S mediante un
numero
finito delle operazioni O?
Il problema è evidentemente simile al precedente, anzi:
codificando opportunamente le stringhe di lettere con numeri si
può trasformare in un problema del tipo numerico discusso prima.
Quindi si tratta di fatto dello stesso tipo di problema. Questa
possibilità di codificare problemi simbolici in problemi numerici
è la chiave di tutta la questione.
Esempio 3:
Elenchiamo una serie di assiomi di una teoria formale (che sono
stringhe di simboli).
Elenchiamo una serie di operazioni logiche dette "di inferenza"
che ci dicono data una stringa che rappresenta un enunciato quali
sono le stringhe che corrispondono a conseguenze logiche
immediate di quell' enunciato.
(Ad esempio, dalla stringa di simboli "per ogni x(x=x)" possiamo
dedurre formalmente le conseguenze logiche espresse dalle
stringhe "0=0", "1=1" e tante altre cose...)
PROBLEMA3: è possibile partendo dagli assiomi arrivare tramite le
regole di inferenza ad una certa stringa S? Ovvero: è possibile
dimostrare S nella teoria che ha quei dati assiomi e quelle date
regole?
La cosa può sembrare sorprendente ma per una teoria completamente
formalizzate il problema 3 è del tutto analogo al problema 2:
come il problema 2, il 3 si può con opportune codifiche formulare
in termini di numeri e ricondurre quindin ad un problema tipo il
problema 1.
E' così che una teoria aritmetica T può *parlare di sè stessa*:
un enunciato della forma "X è dimostrabile nella teoria T" può
essere codificato prima in termini di logica simbolica e diventa
"la stringa X è derivabile con le regole logiche dalle stringhe
degli assiomi mediante le operazioni logiche" (PROBLEMA2) e
questo enunciato può essere a sua volta espresso nella forma
numerica "il numero N è raggiungibile mediante le operazioni O a
partire dai numeri di base" (PROBLEMA1) che parla di numeri ed è
quindi esprimibile nella teoria aritmetica T.
Ora fissiamo la nostra attenzione su una specifica teoria
aritmetica T (non preciso le caratteristiche che deve avere per
non essere noioso, intuitivamente è data da:
- un linguaggio in cui si possono formulare enunciati sui numeri
interi,
- un insieme di assiomi
- regole formali per dedurre conseguenze logiche a partire dagli
assiomi):
Il trucco di Godel è quello di costruire un enunciato che "parla
di sè stesso" e della sua dimostrabilità in T, ecco come:
Iniziamo da un enunciato che esprime la *non risolubilità* di un
problema
analogo al PROBLEMA1, come questo:
(G) "Non è possibile ottenere il numero N dai numeri base B
mediante le
operazioni X (con un numero finito di passi)."
(NB: è un enunciato numerico ed è quindi esprimibile nel
linguaggio di T che è una teoria aritmetica.)
Ora facciamo in modo che:
- il numero N che compare in (G) sia una codifica numerica dello
stesso enunciato (G) (si può fare anche se non è banale)
- i numeri base B codificano gli assiomi di T
- le operazioni X sono una codifica delle regole di inferenza di
T
La codifica di cui parlo è quella che ci permette di convertire
il PROBLEMA3 in un problema numerico come il PROBLEMA1, come
spiegato sopra.
Dunque in questo modo abbiamo costruito un enunciato (G) che di
fatto parla solo di numeri, e più precisamente dice che un certo
problema numerico (simile al PROBLEMA1) non è risolubile.
Tuttavia se "decodificato" (G) ci dice di più: ci dice che lui
stesso non è dimostrabile nella teoria T!!
Conclusione:
Se la teoria aritmetica di cui parla (G) dimostra solo teoremi
veri allora
(G) non è dimostrabile in T, poichè altrimenti sarebbe
dimostrabile una
affermazione che dice il falso.
Poichè (G) dice appunto di non essere dimostrabile in T,
concludiamo anche
che (G) è vera.
Cioè: se T dimostra solo teoremi veri allora (G) è vera e
indimostrabile.
Visto da un altro punto di vista:
Se un giorno io trovassi una dimostrazione di (G) questa
dimostrazione
opportunamente decodificata in termini numerici mi fornirebbe un
procedimento per ottenere N dai numeri base B mediante le
operazioni X con
un numero finito di passi, ma ciò è esattamente la negazione di
quello che afferma (G)!! Quindi (G) dimostrabile implica (G) dice
il falso (e quindi la teoria T sarebbe una teoria da buttare!!).
Sintesi finale: il linguaggio dell' aritmetica formale consente
di *formulare* al suo interno tutti gli enunciati aritmetici, ma
qualunque insieme ragionevole di assiomi scegliamo come base per
dimostrare i nostri teoremi, si potrà sempre trovare un enunciato
vero che non è possibile dedurre dai nostri assiomi seguendo le
regole della logica formale.
(Testi consigliati: "Godel, Escher, Bach", "La mente e l'
infinito".)
Ciao!!
Marco

 esitenza necessaria dell'Ens necessarium?
La riporto io, per come e' contenuta in Odifreddi "Il vangelo secondo la
scienza", Einaudi. E' veramente interessante, state a sentire.
Si definisca una proprieta' positiva come quella proprieta' che:
1) una intersezione di proprieta' positive e' positiva;
2) la proprieta' vuota non e' positiva;
3) se una proprieta' non e' positiva, lo e' la sua negazione;
4) una proprieta' che abbia come sottoinsieme una proprieta' positiva, e'
positiva.
Allora, se il mondo e' finito, si puo' dimostrare che Dio, definito come
cio' che possiede tutte le proprieta' positive, esiste ed e' unico. Inoltre
e' dimostrabile che Dio possiede tutte e sole le proprieta' positive.
Ci sono alcuni problemi curiosi nella dimostrazione. Il primo dei quali e'
l'assoluta vuotezza semantica del termine "positivo": va bene infatti, e la
dimostrazione funziona, con qualunque proprieta' soddisfi 1-4, quindi non e'
che si capisca poi bene cosa significhi avere una proprieta' positiva.
Piu' grave invece e' che la dimostrazione non funziona nel caso in cui il
mondo non sia finito, infatti dobbiamo ricorrere in questo caso ad
un'estensione della proprieta' 1:
1bis) ogni intersezione numerabile (finita o infinita) di proprieta'
positive e' positiva.
Godel maschero' questo cambiamento defininendo come positiva la proprieta'
"essere Dio". Infatti da qui si puo' dimostrare che, se "essere Dio" e' una
proprieta' positiva, allora Dio esiste ed e' unico :-) Notate anche che
questa dimostrazione e' banale: per il punto 2, nessuna proprieta' positiva
e' descritta da un insieme vuoto.
Non dobbiamo dimenticare pero' che questa prova, pur se matematicamente
corretta, non e' soddisfacente per due motivi: il primo e' che le proprieta'
positive sono definite su estensioni ontologiche nel mondo, quindi Dio e'
definito sul mondo, cioe' e' immanente e non trascendente; il secondo e' che
ogni definizione di proprieta' positiva ha il suo Dio, come dice Odifreddi
"piu' che di Dio, si dovrebbe forse parlare di un capoclasse". Infatti, per
esempio, sull'insieme dei numeri naturali minori o uguali a 100 possiamo
definire la proprieta' positiva come la proprieta' di "essere maggiore di un
dato numero naturale". In questo caso, "Dio" di questo universo e' il numero
100.
