Sopra il Principio d'Induzione

da **Valerio Capraro** » 19/10/2005, 21:45

Visto che sti giorni va di moda il principio di induzione e visto che mi sono rotto di fare gli esercizi di teoria di Galois, scrivo un piccolo saggio sopra il principio d'induzione.

Il principio di induzione viene formalizzato da Peano nel suo terzo assioma dei numeri naturali. Per la cronaca i primi due sono; per la cronaca la definzione rigorosa è:

Si chiama terna di Peano ogni terna (N,0,f), dove N è un insieme contenente 0 e f una applicazione su N che verifica le tre seguenti proprietà (i tre assiomi di Peano)

1) 0 non appartiene a Imf
2) f è iniettiva
3) se M è un insieme contenente 0 per cui f(M) è contenuto in M, allora M=N.

ora, che una siffatta terna esista sembra non dimostrabile; quindi:

ASSIOMA DELL'INFINITO: Esiste una terna di Peano.

a questo punto è importantissimo il seguente

Teorema: (porta il nome di due matematici tedeschi che non mi ricordo (mi perdonino!!))

Se esiste una terna di Peano allora questa è unica

quindi ha senso la seguente

definizione: l'unica terna di Peano la chiamiamo "insieme dei numeri naturali"; e si pone f(0)=1, f(f(0))=2... e via dicendo. L'applicazione f viene detta "applicazione del successivo".

A questo punto si definisce la somma e il prodotto nel modo più ovvio e tutte quelle belle cose. Veniamo ora al terzo assioma di Peano:

con questa nuova interpretazione di f, possiamo formulare il terzo principio di Peano nel seguente modo:

Se M è un insieme contenente 0 che se contiene n contiene anche n+1, allora N=M. In tale nuova formulazione nessuno ha difficoltà nel riconoscere la base del principio di induzione nella sua forma cosiddetta debole.

la forma forte si ottiene invece riformulando ulteriormente il terzo assioma di Peano nel seguente modo:

Se M è un insieme contenente 0 che se contiene tutti i numeri fino a n-1 contiene anche n, allora M=N.

beh.. il fatto che queste tre formulazioni del terzo assioma di induzione siano equivalenti è una questione molto complicata e bella ed una dimostrazione si trova nel mio antichissimo post "tre assiomi e una dimostrazione".

Comunque sia siamo arrivati alle versioni note del principio di induzione:

forma debole: Sia Pn una proprietà vera per un naturale di partenza n0 e tale che la verità di Pn implica quella di Pn+1, allora tale proprietà è vera per ogni naturale maggiore o uguale di n0

forma forte: Sia Pn una proprietà vera per un naturale di partenza n0 e tale che la verità di Pn0 Pn0+1.... Pn0+k implica quella di Pn0+k+1 allora tale proprietà è vera per tutti gli i naturali maggiori od uguali di n0

Chiaramente tali formulazioni del principio di induzioni non sono "sintatticamente" equivalenti al terzo assioma di Peano e quindi necessiterebbero di una dimostrazione che, sebbene facile, non mi va di postare (ihih).

A questo punto voglio soffermarmi sulle molte varianti del principio di induzione:

1) Sia Pn una proprietà vera per un certo naturale n0. Se la falsità di Pn (n>n0) implica la falsità di Pn-1, allora tale proprietà è vera per ogni naturale maggiore od uuguale di n0.

2) Sia Pn una proprietà vera per n0 e per n0+1. Se Pn vera implica Pn+2 vera allora tale proprietà è vera per tutti gli n >= n0

3) Sia Pn una proprietà vera per un insieme superiormente illimitato di naturali. Se Pn falsa implica P+1 falsa allora tale proprietà è vera per tutti i naturali a partire dal minimo del precedente insieme su sui è vera

4) Sia N1, N2,... una successione di insiemi numerabili e P1,P2... una successione di proprietà da verificare rispettivamente su N1, N2... Supponiamo P1 vera sul primo (!?) elemento di N1 e supponiamo Pn vera sul k-esimo elemento di Nn, allora se tale verità implica P(n-1) vera sul (k+1)-esimo elemento di N(n-1) e P(n+1) vera sul (k-1)-esimo elemento di N(n+1) tutto questo per n,k diversi da 1. Se inoltre P1 vera sul k-esimo elemento di N1 implica la verità di P1 sul (k+1)-esimo elemento di N1 e se infine Pn vera sul primo elemento di Nn implica P(n+1) vera sul primo elemento di N(n+1). Allora tutti gli elementi di N1... verificano rispettivamente le proprietà N1...

(sembra un pò astrusa quest'ultima variante, ma si può comprendere facilmetne qualora si pensi alla dimostrazione della numerabilità dell'insieme dei numeri razionali.

beh... non gliela faccio più a scrivere e quindi vi saluto a tutti...

ciao, ubermensch

da **infinito** » 20/10/2005, 00:28

So bene che a scrivere tanto si incappa naturalmente in qualche errore (sei “normale” anche tu, vero?)

Salvo miei errori correggo uno dei tuoi:
<blockquote id="quote">quote:<hr height="1" noshade id="quote">Originally posted by ubermensch

A questo punto voglio soffermarmi sulle molte varianti del principio di induzione:
…
3) Sia Pn una proprietà vera per un insieme superiormente illimitato di naturali. Se Pn falsa implica P+1 falsa allora tale proprietà è vera per tutti i naturali a partire dal minimo del precedente insieme su sui è vera<hr height="1" noshade id="quote"></blockquote id="quote">
Secondo me la formulazione corretta è:
3) Sia Pn una proprietà vera per un insieme superiormente illimitato di naturali. Se Pn falsa implica P+1 falsa allora tale proprietà è vera tutti i naturali.

Poi dici
<blockquote id="quote">quote:<hr height="1" noshade id="quote">Originally posted by ubermensch

4) Sia N1, N2,... una successione di insiemi numerabili e P1,P2... una successione di proprietà da verificare rispettivamente su N1, N2... Supponiamo P1 vera sul primo (!?) elemento di N1 e supponiamo Pn vera sul k-esimo elemento di Nn, allora se tale verità implica P(n-1) vera sul (k+1)-esimo elemento di N(n-1) e P(n+1) vera sul (k-1)-esimo elemento di N(n+1) tutto questo per n,k diversi da 1. Se inoltre P1 vera sul k-esimo elemento di N1 implica la verità di P1 sul (k+1)-esimo elemento di N1 e se infine Pn vera sul primo elemento di Nn implica P(n+1) vera sul primo elemento di N(n+1). Allora tutti gli elementi di N1... verificano rispettivamente le proprietà N1...<hr height="1" noshade id="quote"></blockquote id="quote">
ma delle due proposizioni di
«se tale verità implica
P(n-1) vera sul (k+1)-esimo elemento di N(n-1)
e
P(n+1) vera sul (k-1)-esimo elemento di N(n+1)»
è sufficiente considerarne una sola

Infine mi parrebbe interessante completare con la generalizzazione di tale concetto ai numeri transfiniti (lo ho formalizzato io, quindi potrebbe non essere stato fatto in forma ottimale):

Sia T un insieme di numeri transfiniti ordinato canonicamente, e a il suo primo elemento.
Se una proprietà p è tale che in T:
1° p(a) è vera;
2° per ogni elemento b di T, (p(c) vera per ogni c<b) implica (p(b) vera)
allora p è vera in T.

Quello che hai scritto mi pare comunque molto interessante. Mi ha però lasciato dubbiosa la tua affermazione
<blockquote id="quote">quote:<hr height="1" noshade id="quote">Originally posted by ubermensch

ora, che una siffatta terna esista sembra non dimostrabile; quindi:

ASSIOMA DELL'INFINITO: Esiste una terna di Peano.<hr height="1" noshade id="quote"></blockquote id="quote">
A me sembrava che la costruzione dei tranfiniti (e quindi dei naturali) per mezzo degli insiemi di elementi ottenuti dall’insieme vuoto fosse un modello sufficiente a garantire l’esistenza di una terna di Peano
(spiego con esempi, definendo i numeri naturali come particolari insiemi: 0={}; 1={0}; 2={0; 1}; 3={0; 1; 2}; 4={0; 1; 2; 3}; 5={0; 1; 2; 3; 4}; 6={0; 1; 2; 3; 4; 5}; ….).
Perché questo non è sufficiente per garantire l’esistenza di una terna di Peano?

da **Valerio Capraro** » 20/10/2005, 16:36

vediamo un pò di rispondere a tutto:

1) hai ragione
2) hai torto: perchè a priori non posso sapere come arrivo al k-esimo elemento di Nn; ovvero se ci arrivo salendo o scendendo, quindi (a patto di non avere altre informazioni) devo dimostrarle tutte e due
3) non so che dirti; l'unica cosa che mi viene in mente è che la funzione f che utilizzi te è una funzione di insieme e non una funzione su elementi di N; nel senso che tu definisci f({})=1, f({0,1})=2 ... e quindi di fatto quella che costruisci te non è una terna di Peano.

ciao, ubermensch

da **infinito** » 21/10/2005, 01:14

Sul mio “1”:
siamo d’accordo.

Sul mio “2”:
mi pare abbastanza convincente che si possa addirittura eliminare anche un’altra richiesta (non me ne ero accorto), cioè che alla fine la tua “variante 4” possa essere “ridotta a:

4a)
Sia N1, N2,... una successione di insiemi numerabili ORDINATI e P1,P2... una successione di proprietà da verificare rispettivamente su N1, N2...
Supponiamo che
1- P1 vera sul primo (!?) elemento di N1,
2a - se P1 vera sul k-esimo elemento di N1 implica la verità di P1 sul (k+1)-esimo elemento di N1,
3a - per k>1, se Pn vera sul k-esimo elemento di Nn, allora P(n+1) vera sul (k-1)-esimo elemento di N(n+1).
Allora
tutti gli elementi di N1... verificano rispettivamente le proprietà N1...

Oppure

4b)
Sia N1, N2,... una successione di insiemi numerabili ORDINATI e P1,P2... una successione di proprietà da verificare rispettivamente su N1, N2...
Supponiamo che
1 - P1 vera sul primo (!?) elemento di N1,
2b – se Pn vera sul primo elemento di Nn implica P(n+1) vera sul primo elemento di N(n+1)
3b - per n>1, se Pn vera sul k-esimo elemento di Nn, allora P(n-1) vera sul (k+1)-esimo elemento di N(n-1)
Allora
tutti gli elementi di N1... verificano rispettivamente le proprietà N1...

Se non ti pare convincente fammelo sapere.

Sul mio “3”:
Hai ragione: mi sono espresso male.
Supposto di aver definito i numeri naturali (come gli «insiemi di elementi ottenuti dall’insieme vuoto» del mi opost precedente), un esempio di una terna di Peano è (N,0,f), dove “N” è l’insieme dei numeri naturali, lo “0” è lo 0 (cioè {}), e f è l’applicazione su N che ad ogni numero naturale n associa il successivo, che è il numero “insieme dei numeri naturali minori o uguali ad n”.

Sopra il Principio d'Induzione

Sopra il Principio d'Induzione

Chi c’è in linea