Newsgroup: it.cultura.filosofia
Titolo: teorema di Godel?

Ciao a tutti !
qualcuno conosce almeno in linea generale il procedimento che ha seguito
godel per dismostrare il suo teorema,
scrivetemi a 
timeb...@freemail.it

 ha scritto nel messaggio
news:9a6p6u$lq6$1...@nreadB.inwind.it...

Ti consiglio di porre la domanda su      it.scienza.matematica

Ti consiglio di porre la domanda su      it.scienza.matematica
Pessimo consiglio: qualsiasi cosa dicano su it.scienza.matematica
potrebbe essere incompleto o incoerente.

 ha scritto nel messaggio
news:3ac8125d...@news.nottingham.ac.uk...

Mah, dipende da chi ti risponde: su   it.scienza.matematica   abbiamo NN e
qualche altro che sono bravi.
Cmq, se conosci altre NG di Matematica (in italiano), puoi suggerirmi le
migliori?

 wrote

Provo a darti un' idea.
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={1, 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.
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, da "per ogni x(x=x)" possiamo concludere "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 questo problema è del tutto analogo al 2, soltanto più
complicato. Come il 2 si può con opportune codifiche formulare in termini
di numeri come nell' esempio 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 in
forma numerica "il numero N è raggiungibile mediante le operazioni O a
partire dai numeri di base" che parla di numeri ed è quindi esprimibile
nella teoria aritmetica T.
Ora fissiamo la nostra attenzione su una teoria aritmetica T (non preciso
le caratteristiche che deve avere per non essere noioso, intuitivamente è
una teoria in cui si possono formulare e dimostrare enunciati sui numeri
interi):
Il passo successivo di Godel è quello di costruire un enunciato che "parla
di sè stesso" e della sua dimostrabilità in T.
Iniziamo da un enunciato che esprime la non risolubilità di un problema
analogo al PROBLEMA1:
(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 in T che è una teoria
aritmetica.)
E facciamo in modo che:
- il numero N è una codifica numerica dello stesso enunciato (G)
- 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 (G) di fatto parla di numeri, dice che un certo problema numerico
(simile al PROBLEMA1) non è risolubile, ma interpretato in un certo modo
dice di non essere 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, cioè otterrei che (G) dice il falso!!
(Spero di non aver confuso le idee a chi è riuscito a leggere fin qui.)
Ciao!!
Marco
PS: Gli esempi numerici e simbolici sopra li ho inventati così come mi
venivano, non hanno nessuna pretesa di essere problemi seri!! Diventano
seri solo se complicati con certe scelte di numeri base e di regole.

migliori?
No, il mio commento vale per qualsiasi ng di matematica (infatti era
solo una innocua battuta sui risultati di Godel: cioe' l'incompletezza
e l'impossibilita' di dimostrare la coerenza dei sistemi aritmetici :)

 potrebbe essere incompleto o incoerente.
:-D
Carina questa, me la segno!
Ciao,
     Stefano
--
"When patterns are broken, new worlds emerge."
-- Tuli Kupferberg