induzione....

[iteuler]

Il principio di induzione ti viene in aiuto quando devi dimostrare qualche proposizione che coinvolge i numeri naturali, dimostrazioni di questo tipo sono insindacabili (a patto, ovviamente, di non commettere errori nel procedimento induttivo) ... tuttavia, riflettendoci meglio e pensando ai professori che circolano di questi tempi ...

[infinito]

Vorrei riassumere, correggere e integrare, perché mi pare che ci siano anche idee non del tutto corrette.

1° L’induzione potrebbe anche essere quella magnetica, ma in questo caso si parlava di quella “matematica”, per cui l’esempio delle pecorelle può esser carino, ma solo a patto che fosse poco più di un giochetto, perché una dimostrazione per induzione (se attuata correttamente) è sicuramente valida.

2° Il principio di induzione (PdI) non si può dimostrare, come ha provato Goedel, ma nel senso che non si può dimostrare la coerenza di nessun sistema di assiomi abbastanza complesso da “contenere l’aritmetica”.
In realtà, date le definizioni necessarie (per esempio di cosa sono i numeri naturali) è anche possibile dimostrane la validità. Come ha detto jack nell’insieme dei naturali, definito da Peano, si può dimostrare banalmente che vale, utilizzando il suo 5° postulato:
«se un sottoinsieme S dell’insieme dei naturali N è tale che vi appartiene il primo numero (lo “0” o lo “1”, a seconda delle definizioni), ed è tale che “se vi appartiene un numero vi appartiene anche il suo successivo”, allora S coincide con N».
(In questo caso non considero che il 5° postulato sia il principio, ma lo uso per dimostrarlo.)

3° Il PdI ha una sua forma più debole, che è la seguente:
«Se nell’insieme dei naturali N una proprietà P è vera per un particolare n0, e se si dimostra che “se si suppone vera per un certo n allora è necessariamente vera anche per il suo successivo (cioè n+1)”, allora è vera per tutti i numeri maggiori o uguali a n0».
Ovviamente se n0 = 0 si ha che la proprietà è vera per tutti i numeri, cioè che è vera in N.

4° Il PdI ha una sua forma più forte (si chiame “Principio di induzione transfinito”, vedi il successivo 5° punto), ma che posso “indebolire” in:
«Se in un insieme ben ordinato (cioè tale che ogni suo sottoinsieme abbia un elemento minimo) A una proprietà P è vera per un particolare n0, e se si dimostra che “se si suppone vera per tutti gli elementi minori di un certo elemento n allora è necessariamente vera anche per n”, allora è vera per tutti gli elementi maggiori o uguali a n0».

5° Il “Principio di induzione transfinito” recita:
«Se in un insieme ben ordinato A, una proprietà P è vera per il primo elemento e se è vero che “se si suppone vera per tutti gli elementi minori di un certo elemento n allora è necessariamente vera anche per n”, allora è vera in A».

6° Dice Enrico: «il prof la può accettare o non sarebbe potrebbe obbiettare su qualcosa? »
Secondo me il prof può sempre chiedere chiarimenti, delucidazioni e dimostrazioni, anche per dimostrazioni “ufficiali”, anzi: sarebbe bene che non ci fossero dimostrazioni che hanno il “nulla osta” e che possono essere ripetute a pappagallo senza aver capito niente (secondo voi potrebbero servire a qualcosa che non sia un “promemoria” o un “suggerimento” a chi capisce qualcosa e può ricostruire la dimostrazione?). Viceversa sta a te saper motivare perché e come usi il PdI nelle tue dimostrazioni (parlo nel caso che a scuola non lo abbiate mai incontrato).

Attendo critiche (corbellerie ne dico tante …).

[david_e]

Una domanda per il principio di induzione transfinito (ammetto da subito di essere ignorante in materia): al momento e' una cosa accettata da tutti la validita' di questo metodo o e' una cosa da prendere con le molle? Io sapevo che non sono ammesse operazioni logiche che implichino un numero infinito di passaggi...
Poi se fosse valida l'induzione transfinita si potrebbe fare induzione su tutti gli elementi di IR (dato che in ZFC anche IR e' ben ordinabile)?

[infinito]

Sì: è accettato "ufficialmente".

Non si parla di un numero infinito di passaggi, come non se ne parla in quello "ordinario" (che comunque dimostra per l'insieme numerabile N.

Per "IR" (che cos'è: l'insieme dei reali?) si potrebbe in teoria utilizzare, ma se lo dimostri con un "buon ordinamento", che è tutt'altra cosa dall'ordinamento canonico in R.
Comunque ogni insieme è bene ordinabile.

Di fatto però credo che si utilizzi quasi esclusivamente lavorando con gli ordinali (e, ovviamente, i cardinali, visto che vi sono inclusi).