uso dell'induzione transfinita nella dimostrazione della consistenza dell'aritmetica
gnappa
ho letto questo articolo di Gentzen sulla dimostrazione della
consistenza dell'aritmetica:
http://www.cs.unibo.it/~corsi/FolderDidattica/Dispense_on_line/Gentzen_infinito.pdf
La questione fondamentale mi sembra che sia non tanto la dimostrazione,
ma il fatto che essa venga fatta usando strumenti accettati da tutti,
quindi anche dagli intuizionisti. Gentzen dice che gli intuizionisti non
accettano l'infinito in atto, e la sua dimostrazione la evita:
"Il concetto di numero ordinale transfinito risale a G. Cantor e in
realtà appartiene alla teoria degli insiemi. Comunque noi avremo bisogno
solo di una porzione molto limitata dei numeri ordinali sviluppati in
quella teoria - un segmento della seconda classe di numeri nella
terminologia della teoria degli insiemi - un segmento che
può essere costruito in modo strettamente costruttivo e che non ha
niente in comune con gli aspetti discutibili dell'interpretazione
attualista che sono particolarmente evidenti nella teoria degli insiemi
e che devono essere evitati nella dimostrazione di
consistenza."
Poi però introduce gli ordinali transfiniti così:
"I numeri ordinali transfiniti sono costruiti nel seguente modo: prima
viene la successione dei numeri naturali: 1, 2, 3, ecc. Poi viene
introdotto un nuovo numero w, che per definizione si trova dopo tutti i
numeri naturali. w è seguito da w+1, quindi da w+2, w+3, ecc. Al di là
di tutti i numeri della forma w+n segue w*2, poi w*2+1, w*2+2, ecc.,
dopo di questi w*3, quindi w*3+1, w*3+2, ecc. Al di là di tutti i numeri
della forma w*n+n segue il numero w^2, quindi ancora w^2+1, w^2+2, ...,
w^w+w, ecc, e finalmente w^3, e ancora avanti in questo modo per formare
w^4, ..., w^5, ..., e finalmente w^w, e ancora altri numeri, se si
desidera."
Il mio problema è che non riesco a capire come l'uso di espressioni "si
trova dopo tutti i numeri naturali", "Al di là di tutti i numeri della
forma..." non corrisponda a concepire l'infinito in atto. Inoltre non ho
capito se gli ordinali transfiniti sono numerabili.
grazie e ciao
--
GN/\PPA
"E' meglio accendere una candela che maledire l'oscurità"
http://amnestypiacenza.altervista.org
Errori nei test di ammissione alla SSIS
http://gnappa.netsons.org/quesitissis/index.php
maitre Aliboron
> tutti i numeri naturali.
A me pare che da qualche parte si contraddice.
Come lo costruisce w?
Da' per scontato che esiste un numero oltre i naturali
(o meglio, lo definisce lui). Mica e' tanto costruttivo.
--
maitre Aliboron
"Pliiss..., visits..., uebsaits...,
batt pliiss..., visits..., itali..."
Topo Gigio Rutelli - 2007
gnappa
>> Poi viene introdotto un nuovo numero w, che per definizione si trova dopo
>> tutti i numeri naturali.
>
> A me pare che da qualche parte si contraddice.
> Come lo costruisce w?
> Da' per scontato che esiste un numero oltre i naturali
> (o meglio, lo definisce lui). Mica e' tanto costruttivo.
>
infatti è quel che penso anch'io, e non riesco a capire la sua precisazione:
"La preoccupazione che questa procedura sia non-costruttiva poiché la
concezione attualista di successione completa dei numeri naturali già
sembra entrare nella formazione di w, si rivela infondata. Il concetto
di infinito può, senza dubbio, essere qui interpretato in modo
potenziale dicendo, ad esempio: non importa quanto lontano possiamo
andare nella formazione costruttiva di nuovi numeri naturali, il numero
w sta nella relazione n < w con ogni tale numero naturale n. E le
successioni infinite che nascono nella formazione di altri numeri
ordinali dovrebbero essere interpretate precisamente nello stesso modo."
maitre Aliboron
l'autore, ma personalmente mi sembra poco corretto.
Io defiisco un numero tale che n<w qualunque n in N
ma a questo punto faccio prima a dire "definisco una
aritmetica consistente" (in base alla propieta' che ha
di "essere consistente" che e' una proprieta' "attuale"),
e si risparmia tutta la commedia. L'evidente errore di
ragionamento insito nella frase sopra mi pare che e' lo
stesso in cui cade il tizio.
E poi una osservazione. w non puo' essere un naturale.
Allora come e' possibile stabilire una relazione "<" sic
et simpliciter, senza alcuna giustificazione, tra un naturale
e un transfinito? Almeno dovrebbe prima far vedere che
eventualmente N appartiene ad un insieme piu' ampio e
poi estendere la relazione in questo insieme e far vedere
che e' equivalente alla analoga "<" in N.
Che w esista in senso attuale ci posso pure credere,
pero' uno straccetto di dimostrazione aiuta. Senno'
ritorniamo ai tempi dell'aria fritta. Anche io sono buono
a fare il matematico cosi'.
Matisse
> Il mio problema è che non riesco a capire come l'uso di espressioni
> "si trova dopo tutti i numeri naturali", "Al di là di tutti i numeri
> della forma..." non corrisponda a concepire l'infinito in atto.
Si può pensare di poter collocare qualcosa dopo "tutti i..." anche senza
pensare "tutti i..." come completati. Ad esempio, uno può - e così di
fatto definisce un ordinamento - dire che preferisce una ciliegia a n
pesche, qualunque sia il numero naturale n, e questo non comporta
affatto il concepire una infinità attuale di pesche.
> Inoltre non ho capito se gli ordinali transfiniti sono numerabili.
Anche i cardinali, e in particolare anche quelli non numerabili, sono
(pensabili come) ordinali. Quindi se intendevi *tutti* gli ordinali,
allora no, non sono numerabili.
Se però intendevi, ad esempio, quelli fino a w^w (= omega^omega), allora
sì, quelli sono senz'altro numerabili.
Giovanni
Matisse
> Se però intendevi, ad esempio, quelli fino a w^w (= omega^omega),
> allora sì, quelli sono senz'altro numerabili.
E ce ne sono di numerabili che vanno ben oltre, e oltre, e oltre,
ovviamente.
Giovanni
Matisse
> > Poi viene introdotto un nuovo numero w, che per definizione si
> > trova dopo tutti i numeri naturali.
>
> A me pare che da qualche parte si contraddice.
> Come lo costruisce w?
> Da' per scontato che esiste un numero oltre i naturali
> (o meglio, lo definisce lui). Mica e' tanto costruttivo.
Tu essere fesso, molto fesso.
Ciao!
Giovanni
LordBeotian
"gnappa" <lagiraffa77Q...@yahoo.it> ha scritto
> "I numeri ordinali transfiniti sono costruiti nel seguente modo: prima
> viene la successione dei numeri naturali: 1, 2, 3, ecc. Poi viene
> introdotto un nuovo numero w, che per definizione si trova dopo tutti i
> numeri naturali. w è seguito da w+1, quindi da w+2, w+3, ecc. Al di là di
> tutti i numeri della forma w+n segue w*2, poi w*2+1, w*2+2, ecc., dopo di
> questi w*3, quindi w*3+1, w*3+2, ecc. Al di là di tutti i numeri della
> forma w*n+n segue il numero w^2, quindi ancora w^2+1, w^2+2, ..., w^w+w,
> ecc, e finalmente w^3, e ancora avanti in questo modo per formare w^4, ...,
> w^5, ..., e finalmente w^w, e ancora altri numeri, se si desidera."
>
> Il mio problema è che non riesco a capire come l'uso di espressioni "si
> trova dopo tutti i numeri naturali", "Al di là di tutti i numeri della
> forma..." non corrisponda a concepire l'infinito in atto. Inoltre non ho
> capito se gli ordinali transfiniti sono numerabili.
Tutti gli ordinali che vengono descritti sopra sono "calcolabili": puoi
costruire un programma per calcolatore che riceve in input una qualsiasi
coppia di tali ordinali (ad esempio w^w+w e 4*w^2) e ti dice chi dei due sta
prima e chi sta dopo. Questo significa che la struttura di ciascuno di tali
ordinali è "costruibile" algoritmicamente. NB: questo non è vero per *tutti*
gli ordinali ma solo per il segmento che è rilevante nell'articolo.
Ciao!!
Marco
maitre Aliboron
sai che novita'...
Matisse
> Tutti gli ordinali che vengono descritti sopra sono "calcolabili":
> puoi costruire un programma per calcolatore che riceve in input una
> qualsiasi coppia di tali ordinali (ad esempio w^w+w e 4*w^2) e ti
> dice chi dei due sta prima e chi sta dopo. Questo significa che la
> struttura di ciascuno di tali ordinali è "costruibile"
> algoritmicamente.
In realtà il vero problema è giustificare l'induzione, fino a un dato
ordinale "costruibile".
Giovanni
LordBeotian
"Matisse" <nos...@invalid.it> ha scritto
Sicuramente è concettualmente più complicato rispetto all'induzione
ordinaria, ma dal punto di vista di un costruttivista non dovrebbe porre
problemi "filosofici" del tipo di cui parla l'articolo, non più almeno di
quanti già non ne ponga l'induzione ordinaria sui naturali.
gnappa
> gnappa wrote:
>> Inoltre non ho capito se gli ordinali transfiniti sono numerabili.
>
> Anche i cardinali, e in particolare anche quelli non numerabili, sono
> (pensabili come) ordinali. Quindi se intendevi *tutti* gli ordinali,
> allora no, non sono numerabili.
> Se però intendevi, ad esempio, quelli fino a w^w (= omega^omega), allora
> sì, quelli sono senz'altro numerabili.
>
LordBeotian ha scritto:
> Tutti gli ordinali che vengono descritti sopra sono "calcolabili":
> puoi costruire un programma per calcolatore che riceve in input una
> qualsiasi coppia di tali ordinali (ad esempio w^w+w e 4*w2) e ti dice
> chi dei due sta prima e chi sta dopo. Questo significa che la struttura
> di ciascuno di tali ordinali è "costruibile" algoritmicamente.
> NB: questo non è vero per *tutti* gli ordinali ma solo per
> il segmento che è rilevante nell'articolo.
Grazie a entrambi, questo aiuta a capire. E' proprio il fatto che siano
numerabili che rende l'induzione transfinita accettabile dagli
intuizionisti giusto?
LordBeotian
"gnappa" <lagiraffa77Q...@yahoo.it> ha scritto
> Grazie a entrambi, questo aiuta a capire. E' proprio il fatto che siano
> numerabili che rende l'induzione transfinita accettabile dagli
> intuizionisti giusto?
Non credo che la sola numerabilità sia sufficiente per rendere questi
ordinali oggetti accettabili in un ottica "costruttivista". La cosa
importante è che siano oggetti "costruibili". (Senza dimenticare che esistono
varie forme di costruttivismo e che il costruttivismo non ha una definizione
rigorosa).
Vedi qui per maggiori delucidazioni sul "costruttivismo":
http://en.wikipedia.org/wiki/Constructivism_(mathematics)
gnappa
>
> "gnappa" <lagiraffa77Q...@yahoo.it> ha scritto
>
>> Grazie a entrambi, questo aiuta a capire. E' proprio il fatto che
>> siano numerabili che rende l'induzione transfinita accettabile dagli
>> intuizionisti giusto?
>
> Non credo che la sola numerabilità sia sufficiente per rendere questi
> ordinali oggetti accettabili in un ottica "costruttivista". La cosa
> importante è che siano oggetti "costruibili".
Sì, intendevo che se non fossero numerabili sicuramente non sarebbero
costruibili, o sbaglio?
grazie e ciao
Matisse
> Sì, intendevo che se non fossero numerabili sicuramente non sarebbero
> costruibili, o sbaglio?
Non sbagli: gli ordinali non numerabili certamente non sono costruibili.
Giovanni
Matisse
Non sono del tutto d'accordo. Non puoi mettere sullo stesso piano
(filosofico) procedimenti - l'induzione ordinaria e l'induzione fino a
epsilon_0 - che hanno diversa forza dimostrativa.
In PA puoi benissimo definire tutti gli ordinali "calcolabili" di cui
sopra e decidere (con una formula phi(x,y) che è sempre decidibile in
PA), data una qualsiasi coppia di tali ordinali, quale dei due sta prima
e quale sta dopo. L'unica cosa che non puoi fare, come ben sai, è
dimostrare che ci si può fare induzione. Ma allora non si può dire che
tale induzione è non epistemologicamente più "impegnativa" di quella sui
naturali.
Giovanni
LordBeotian
"Matisse" <nos...@invalid.it> ha scritto
>> > In realtà il vero problema è giustificare l'induzione, fino a un
>> > dato ordinale "costruibile".
>>
>> Sicuramente è concettualmente più complicato rispetto all'induzione
>> ordinaria, ma dal punto di vista di un costruttivista non dovrebbe
>> porre problemi "filosofici" del tipo di cui parla l'articolo, non più
>> almeno di quanti già non ne ponga l'induzione ordinaria sui naturali.
>
>
> Non sono del tutto d'accordo. Non puoi mettere sullo stesso piano
> (filosofico) procedimenti - l'induzione ordinaria e l'induzione fino a
> epsilon_0 - che hanno diversa forza dimostrativa.
> In PA puoi benissimo definire tutti gli ordinali "calcolabili" di cui sopra
> e decidere (con una formula phi(x,y) che è sempre decidibile in PA), data
> una qualsiasi coppia di tali ordinali, quale dei due sta prima e quale sta
> dopo. L'unica cosa che non puoi fare, come ben sai, è dimostrare che ci si
> può fare induzione. Ma allora non si può dire che tale induzione è non
> epistemologicamente più "impegnativa" di quella sui naturali.
Ma infatti non nego quello che dici. Osservo solo che il problema di essere
"epistemologicamente più impegnativa" non è equivalente al problema di essere
"accettabile in un'ottica costruttivista". E' in quest'ultima ottica che le
due induzioni non mi sembrano porre problemi di entità differente (ma visto
che il costruttivismo non è una filosofia dai contorni ben delineati queste
impressioni lasciano comunque il tempo che trovano).
Matisse
> Ma infatti non nego quello che dici. Osservo solo che il problema di
> essere "epistemologicamente più impegnativa" non è equivalente al
> problema di essere "accettabile in un'ottica costruttivista". E' in
> quest'ultima ottica che le due induzioni non mi sembrano porre
> problemi di entità differente (ma visto che il costruttivismo non è
> una filosofia dai contorni ben delineati queste impressioni lasciano
> comunque il tempo che trovano).
Scusa, qual è il più piccolo tra gli ordinali x tali che l'induzione
fino ad x non è dimostrabile in PA? (E' una domanda.)
Giovanni
LordBeotian
Matisse
> > Scusa, qual è il più piccolo tra gli ordinali x tali che
> > l'induzione fino ad x non è dimostrabile in PA? (E' una domanda.)
>
> Non lo so :)
Fino ad omega^2 si può dimostrare?
Vediamo...
Ovviamente riesci a dimostrarla fino a omega, fino a omega*2, fino a
omega*3, eccetera.
Qui dovrebbe esserci il salto alla metateoria. Infatti, hai che per ogni
n,k , è un teorema il fatto che vale l'induzione fino a omega*n+k.
Quello che ti servirebbe per andare oltre, sarebbe un teorema del tipo
"per ogni n,k , ..." dentro la teoria, e non lo puoi dedurre dagli
infiniti teoremi ciascuno dei quali associato a una data coppia n,k.
Quindi no, già per omega^2 l'induzione in PA non si può dimostrare.
Ho ragionato correttamente?
Giovanni
Matisse
> Fino ad omega^2 si può dimostrare?
> Vediamo...
> Ovviamente riesci a dimostrarla fino a omega, fino a omega*2, fino a
> omega*3, eccetera.
> Qui dovrebbe esserci il salto alla metateoria. Infatti, hai che per
> ogni n,k , è un teorema il fatto che vale l'induzione fino a
> omega*n+k. Quello che ti servirebbe per andare oltre, sarebbe un
> teorema del tipo "per ogni n,k , ..." dentro la teoria, e non lo puoi
> dedurre dagli infiniti teoremi ciascuno dei quali associato a una
> data coppia n,k. Quindi no, già per omega^2 l'induzione in PA non si
> può dimostrare. Ho ragionato correttamente?
Se ho ragionato correttamente, questo risponde alla domanda
sull'accettabilità in un'ottica costruttivista: il principio utilizzato
è un salto metateoretico (se, per ogni n, P(n) è un teorema, allora è un
teorema "per ogni n, P(n)"), che normalmente è accettabile anche in
un'ottica costruttivista.
Giovanni
LordBeotian
Matisse
> Sembra che sia epsilon_0:
>
> <http://groups.google.it/group/sci.logic/browse_frm/thread/ed97629c2e65bcae/c0332f188f2d7930?hl=it&lnk=st&q=PA+transfinite+induction#c0332f188f2d7930>
>
Anch'io sospettavo fosse epsilon_0 , poi però ho cambiato idea.
Il link al file pdf presente nel thread su sci.logic non funziona.
Da solo non riesco a capire perché il ragionamento che ho fatto
nell'altro post è sbagliato. Tu dove vedi la falla?
Giovanni
LordBeotian
"Matisse" <nos...@invalid.it> ha scritto
> Anch'io sospettavo fosse epsilon_0 , poi però ho cambiato idea.
> Il link al file pdf presente nel thread su sci.logic non funziona.
> Da solo non riesco a capire perché il ragionamento che ho fatto nell'altro
> post è sbagliato. Tu dove vedi la falla?
Tu hai osservato che un certo tipo di passaggio logico (sufficiente per
dimostrare l'induzione fino a omega^2) non si poteva fare... non so se è vero
ma in ogni caso non sarebbe comunque è sufficiente a dire che non c'è NESSUN
modo di dimostrare l'induzione fino a omega^2 in PA. Se veramente fosse così
semplice individuare enunciati indecidibili in PA il teorema di Godel non
avrebbe destato tanta sorpresa.
LordBeotian
"LordBeotian" <poki...@yahoo.it> ha scritto
Vabbè qui mi devo correggere: il TdG ha una portata molto più generale.
Tuttavia per quanto ne so gli enunciati attualmente noti per essere
indecidibili in PA sono un paio.
Matisse
> Tuttavia per quanto ne so gli enunciati attualmente noti
> per essere indecidibili in PA sono un paio.
Ma come??
L'induzione fino a epsilon_0, l'induzione fino a epsilon_0+1,
l'induzione fino a epsilon_0+2, ...
:-)))))))))))))))
Giovanni
Matisse
> Tu hai osservato che un certo tipo di passaggio logico (sufficiente
> per dimostrare l'induzione fino a omega^2) non si poteva fare... non
> so se è vero ma in ogni caso non sarebbe comunque è sufficiente a
> dire che non c'è NESSUN modo di dimostrare l'induzione fino a omega^2
> in PA.
Nel thread su sci.logic si dice che si deve procedere per induzione. Tu
hai idea di come?
Giovanni
LordBeotian
"Matisse" <nos...@invalid.it> ha scritto
>> Tuttavia per quanto ne so gli enunciati attualmente noti
>> per essere indecidibili in PA sono un paio.
>
> Ma come??
> L'induzione fino a epsilon_0, l'induzione fino a epsilon_0+1, l'induzione
> fino a epsilon_0+2, ...
Sì certo, poi volendo tramite il teorema di Godel se ne costruiscono infiniti
di enunciati indecidibili. Sono un paio quelli matematicamente rilevanti. Ed
in nessun caso la dimostrazione dell'indecidibilità in PA è qualcosa di
semplice.
Matisse
> Sono un paio quelli matematicamente rilevanti.
Appunto, e non saprei se l'induzione fino a un dato ordinale transfinito
possa essere considerata matematicamente rilevante come tali altri
enunciati.
Giovanni
Matisse
> l'induzione fino a un dato ordinale transfinito possa
E soprattutto: potesse.
Giovanni
Matisse
> [...]
Ah, ho capito una cosa.
Tu per induzione dimostri che, se vale l'induzione fino a omega*n,
allora vale anche fino a omega*(n+1). Quindi dimostri che vale fino a
omega^2.
Bisogna capire però perché questo procedimento (sempre che sia corretto)
possa essere applicato fino a ordinali minori di epsilon_0 ma non a
epsilon_0. Hai qualche idea?
Giovanni
Matisse
> Tu per induzione dimostri che, se vale l'induzione fino a omega*n,
> allora vale anche fino a omega*(n+1). Quindi dimostri che vale fino a
> omega^2.
Vabbè, qui bisogna integrare con qualche dettaglio, ma non dovrebbero
esserci problemi.
> Bisogna capire però perché questo procedimento (sempre che sia
> corretto) possa essere applicato fino a ordinali minori di epsilon_0
> ma non a epsilon_0. Hai qualche idea?
Non riesco a capire perché così fino a epsilon_0 non ci si arriva. Forse
è scorretto come procedimento?
Giovanni