Omega-incoerenza

[LordBeotian]

Chi mi sa spiegare in cosa consisterebbe l' eventuale "omega-incoerenza"
dell' aritmetica? Perchè "omega"? Se l' aritmetica formalizzata avesse una
tale incoerenza dovremmo concludere che tutte le stringhe sono dimostrabili?
Grazie.

[Saverio Cittadini]

E` passato un bel po' di tempo dalla domanda, ma mi pare che nessuno
abbia risposto, quindi ci provo... (e che volete, puo` succedere di
assentarsi dai newsgroups per un po' ;-)

Una teoria formale T nel linguaggio dell'aritmetica e`
omega-consistente quando per ogni formula A tale che T dimostri
A(0), A(1),..., A(n),... (per ogni numero naturale n), T non dimostra
Ex~A(x) (uso "E" per il quantificatore esistenziale e "~" per la
negazione). Questa proprieta` e` piu` forte della consistenza:
infatti se T e` omega-consistente ha sicuramente almeno un enunciato
non dimostrabile (ad esempio Ex~(x=x)) e dunque e` consistente.
Le due proprieta` non sono comunque equivalenti: esistono infatti
teorie consistenti ma non omega-consistenti. L'esempio canonico e`
un qualsiasi sistema a cui sia applicabile il primo teorema di
Goedel a cui si aggiunga come assioma ~G, ovvero la negazione della
formula goedeliana; piu` in generale, sono consistenti ma
omega-inconsistenti tutte quelle teorie che hanno formule
verificate da tutti i naturali in ogni modello ma non verificate
da qualche elemento non-standard di un qualche modello (ovviamente
non-standard).

Dunque la omega-inconsistenza (o incoerenza, come volete) e`
strettamente piu` debole della inconsistenza, e non implica la
dimostrabilita` di qualsiasi formula. Va notato a questo punto
che la dimostrazione originaria del primo teorema di Goedel
aveva come ipotesi la omega-consistenza del sistema anziche' la
semplice consistenza (cio` per poter dimostrare che ~G non e`
dimostrabile); tuttavia poco dopo Rosser ha ridimostrato il
teorema con una formula leggermente modificata e per la quale
bastava come ipotesi la semplice consistenza (e infatti a voler
essere del tutto rigorosi quando si formula il teorema di Goedel
e si mette come ipotesi la semplice consistenza lo si dovrebbe
chiamare teorema di Goedel-Rosser).

Spero di essermi spiegato.

Saluti,
Saverio

WARNING: To send me e-mail, remove the string "maggio" from the
address (anti-spam measure).

==Saverio Cittadini, Aspirante Cadetto di Guascogna
Home Page: http://www.mat.unisi.it/web/dottorato/cittadini/index.htm
"Mi piace aprir la botte e raccontare
di come a volte il cielo tocca il mare
di come l'infinito sia nel viso della gente
che ha costruito tutto e non ha mai avuto niente..."
(Pierangelo Bertoli)

[LordBeotian]

Saverio Cittadini ha scritto nel messaggio
<357328...@maggio.unisi.it>...

>Una teoria formale T nel linguaggio dell'aritmetica e`
>omega-consistente quando per ogni formula A tale che T dimostri
>A(0), A(1),..., A(n),... (per ogni numero naturale n), T non dimostra
>Ex~A(x) (uso "E" per il quantificatore esistenziale e "~" per la
>negazione). Questa proprieta` e` piu` forte della consistenza:
>infatti se T e` omega-consistente ha sicuramente almeno un enunciato
>non dimostrabile (ad esempio Ex~(x=x)) e dunque e` consistente.
>Le due proprieta` non sono comunque equivalenti: esistono infatti
>teorie consistenti ma non omega-consistenti. L'esempio canonico e`
>un qualsiasi sistema a cui sia applicabile il primo teorema di
>Goedel a cui si aggiunga come assioma ~G, ovvero la negazione della
>formula goedeliana; piu` in generale, sono consistenti ma
>omega-inconsistenti tutte quelle teorie che hanno formule
>verificate da tutti i naturali in ogni modello ma non verificate
>da qualche elemento non-standard di un qualche modello (ovviamente
>non-standard).

Vuoi dire che per queste teorie esiste una dimostrazione della loro
consistenza? Che tipo di dimostrazione? Con i metodi finitisti di Hilbert?
Il programma di Hilbert non è del tutto fallito?
Sai dove posso raccogliere informazioni su quella che Hofstadter chiama
"aritmetica soprannaturale", in cui si accetta l' omega incoerenza e si
introducono i numeri non-standard? (libri, siti...)

>Dunque la omega-inconsistenza (o incoerenza, come volete) e`
>strettamente piu` debole della inconsistenza, e non implica la
>dimostrabilita` di qualsiasi formula. Va notato a questo punto
>che la dimostrazione originaria del primo teorema di Goedel
>aveva come ipotesi la omega-consistenza del sistema anziche' la
>semplice consistenza (cio` per poter dimostrare che ~G non e`
>dimostrabile); tuttavia poco dopo Rosser ha ridimostrato il
>teorema con una formula leggermente modificata e per la quale
>bastava come ipotesi la semplice consistenza (e infatti a voler
>essere del tutto rigorosi quando si formula il teorema di Goedel
>e si mette come ipotesi la semplice consistenza lo si dovrebbe
>chiamare teorema di Goedel-Rosser).

Quindi neanche la versione omega-incoerente dell' aritmetica è incompleta?
E nel secondo teorema si parla solo di consistenza?

> Saluti,
> Saverio

Grazie mille!!
Saluti!!
MarcoDiscens

[Saverio Cittadini]

LordBeotian wrote:

>Vuoi dire che per queste teorie esiste una dimostrazione della loro
>consistenza? Che tipo di dimostrazione? Con i metodi finitisti di
>Hilbert?

Beh, parlavo di teorie che esprimono l'aritmetica, dunque la
dimostrazione della loro consistenza non puo` basarsi sui metodi
finitisti di Hilbert (che sarebbero formalizzabili nella teoria).
La dimostrazione esiste, come esiste per l'aritmetica di Peano,
ma ovviamente richiede metodi piu` complessi (e ovviamente piu`
discutibili).

> Il programma di Hilbert non è del tutto fallito?

Beh, dipende. Ci sono tante teorie matematiche la cui consistenza
si puo` dimostrare con metodi finitisti... Solo che non appena una
e` in grado di esprimere l'aritmetica, siamo fregati, e siccome
l'aritmetica e` decisamente una parte importante della matematica,
il fallimento del programma di Hilbert resta pressoche' totale a
mio avviso.

>Sai dove posso raccogliere informazioni su quella che Hofstadter chiama
>"aritmetica soprannaturale", in cui si accetta l' omega incoerenza e si
>introducono i numeri non-standard? (libri, siti...)

Ora come ora non mi viene in mente un testo che tratti bene e in modo
abbastanza chiaro (e magari divulgativo) il funzionamento delle
arimetiche non-standard. Posso dirti pero` che ho studiato un po' i
modelli non-standard dell'aritmetica sul libro di Richard Kaye, "Models
of Peano Arithmetic", e mi e` parso discreto; potrebbe darti qualche
intuizione in proposito.

>Quindi neanche la versione omega-incoerente dell' aritmetica è
>incompleta?

Volevi dire "anche", immagino. In tal caso, si`, purche' sia
consistente (e ricorsivamente assiomatizzabile...) e` incompleta.

> E nel secondo teorema si parla solo di consistenza?

Parli del teorema di Goedel-Rosser o del secondo teorema di
incompletezza? Nel primo caso, si`, si parla solo di consistenza.
Nel secondo (cioe` nel teorema che afferma che una teoria consistente
non dimostra la propria consistenza), pure; pero` si puo` precisare
che intanto non e` detto che si possa formulare un analogo con la
omega-consistenza (che cosi` a occhio non mi pare sia formalizzabile
nel sistema), ma se fosse possibile sarebbe banale dimostrarlo,
essendo la omega-consistenza piu` forte della consistenza.

[LordBeotian]

Saverio Cittadini ha scritto nel messaggio

<3577D1...@maggio.unisi.it>...

>>Beh, parlavo di teorie che esprimono l'aritmetica, dunque la
>dimostrazione della loro consistenza non puo` basarsi sui metodi
>finitisti di Hilbert (che sarebbero formalizzabili nella teoria).
>La dimostrazione esiste, come esiste per l'aritmetica di Peano,
>ma ovviamente richiede metodi piu` complessi (e ovviamente piu`
>discutibili).

Mi chiedo che senso abbia dimostrare la consistenza di una teoria
sfruttandone un' altra sulla cui consistenza nutro dubbi ancora maggiori.

Grazie mille per le risposte!!
Saluti!! =)
MarcoDiscens
________
"Divino Buddah, qual' è la migliore domanda che si possa fare, e quale la
migliore risposta che le si possa dare?"
"La migliore domanda è quella che mi hai fatto, la migliore risposta questa
che ti sto dando".

[Saverio Cittadini]

LordBeotian wrote:

>Mi chiedo che senso abbia dimostrare la consistenza di una teoria
>sfruttandone un' altra sulla cui consistenza nutro dubbi ancora
>maggiori.

Se lo chiedono in molti. :-)

C'e` una bella discussione in proposito nel libro di Jean-Yves
Girard "Proof Theory and Logical Complexity" (paragrafo 1.1.6). Fra
l'altro vi si cita un anonimo matematico francese che avrebbe detto
la battuta "Gentzen e` quel tizio che ha dimostrato la consistenza
dell'aritmetica, ovvero dell'induzione fino a omega, usando l'induzione
fino a epsilon_0"; c'e` pero` anche l'esposizione dell'opinione di
Kreisel in merito, secondo cui anche se queste dimostrazioni non
hanno grande valore epistemologico questo non vuol dire affatto che
non abbiano valore matematico: spesso infatti da esse si possono
ricavare corollari interessanti, e comunque una migliore conoscenza
della teoria analizzata, e inoltre le tecniche usate possono rivelarsi
fruttifere in altre situazioni.

Saluti
Saverio

WARNING: To send me e-mail, remove the string "maggio." from the