Principio di induzione
Il mio libro riporta il principio di induzione nel seguente modo:
$[p(0)^^AAn[p(n)->p(n+1)]}->AAnp(n)$ $ninN$
1)Adesso mi chiedo perchè nelle dimostrazioni, quando si sceglie l'elemento generico con cui dimostrare il passo induttivo, esso viene scelto uguale a n? In base alla logica matematica non dovrebbe essere diverso.
Io so che per il quantificatore universale vale la seguente regola di inferenza:
$(P(a))/(AAxP(x))$ purchè P(a) sia ricavata da precedenti premesse universali.
Come potete osservare il termine "particolare" a è diverso da quello generale x.
2)Facendo una ricerca su wikipedia(quello inglese),(https://en.wikipedia.org/wiki/Mathematical_induction) nel paragrafo "Axiom of induction" potete osservare che nel passo induttivo sceglie come termine generale k($AAk$)(utilizzandolo anche come elemento particolare nelle dimostrazioni) anzichè n($AAn$). Come si giustifica formalmente ciò?
$[p(0)^^AAn[p(n)->p(n+1)]}->AAnp(n)$ $ninN$
1)Adesso mi chiedo perchè nelle dimostrazioni, quando si sceglie l'elemento generico con cui dimostrare il passo induttivo, esso viene scelto uguale a n? In base alla logica matematica non dovrebbe essere diverso.
Io so che per il quantificatore universale vale la seguente regola di inferenza:
$(P(a))/(AAxP(x))$ purchè P(a) sia ricavata da precedenti premesse universali.
Come potete osservare il termine "particolare" a è diverso da quello generale x.
2)Facendo una ricerca su wikipedia(quello inglese),(https://en.wikipedia.org/wiki/Mathematical_induction) nel paragrafo "Axiom of induction" potete osservare che nel passo induttivo sceglie come termine generale k($AAk$)(utilizzandolo anche come elemento particolare nelle dimostrazioni) anzichè n($AAn$). Come si giustifica formalmente ciò?
Risposte
"marco955":
Il mio libro riporta il principio di induzione nel seguente modo:
$[p(0)^^AAn[p(n)->p(n+1)]}->AAnp(n)$ $ninN$
1)Adesso mi chiedo perchè nelle dimostrazioni, quando si sceglie l'elemento generico con cui dimostrare il passo induttivo, esso viene scelto uguale a n? In base alla logica matematica non dovrebbe essere diverso.
Io so che per il quantificatore universale vale la seguente regola di inferenza:
$(P(a))/(AAxP(x))$ purchè P(a) sia ricavata da precedenti premesse universali.
Come potete osservare il termine "particolare" a è diverso da quello generale x.
2)Facendo una ricerca su wikipedia(quello inglese),(https://en.wikipedia.org/wiki/Mathematical_induction) nel paragrafo "Axiom of induction" potete osservare che nel passo induttivo sceglie come termine generale k($AAk$)(utilizzandolo anche come elemento particolare nelle dimostrazioni) anzichè n($AAn$). Come si giustifica formalmente ciò?
Ciao Marco!
1) Beh, è molto semplice, viene scelto uguale ad $ n $ perchè ricordati che il P.D.I. vale solo sull'insieme $ mathbb(N) $, quindi per comodità. Poi ricordati anche che quando fai il Passo Base te valuti $ P(n) $ per un valore preciso $ bar(n) $ che per te sarebbe $ P(a) $, quindi non fai altro che fare l'uguaglianza $ a = bar(n) $. Quindi $ (P(a))/(AAxP(x)) -= (P(bara))/(AAaP(a)) -= (P(barn))/(AAnP(n)) $
2) Per quanto riguarda l'assioma in questione, puoi vedere benissimo che scrive proprio $ k in mathbb(N) -= n in mathbb(N) -= marco in mathbb(N) $. Te una incognita puoi chiamarla come vuoi, l'importante è che qualunque sia il suo nome, valga che $ in mathbb(N) $.
P.s. Il passo base, ossia la verifica che la Proposizione $ P(n) $ sia verificata non la fai per un valore qualsiasi, bensì valutandola nel valore $ n = min{n in mathbb(N) | P(n) } $, cioè il PRIMO $n$ per cui quella proprietà è vera (infatti con il metodo dell'induzione andrai a dimostrare che da quello in poi, per tutti i successivi vale $ P(n) $.
Spero di esserti stato utile.
Ciao
Anche io su libri americani ho studiato la formula con $k$. Ne fai una questione di puntiglio, perché la variabile $n$ di cui parli è saturata dal quantificatore $AA$ nelle due volte in cui compare nella definizione, quindi puoi chiamarla come vuoi. (è una "variabile muta").
Quello che mi urta della formula che hai riportato dal libro è che non specifica dove sta questo $k$ o $n$ che dir si voglia.
E' ovvio che, avendo preso lo zero come base per la tua induzione, questo $n$ stia in $NN$, ma bisognerebbe riscriverla in modo più preciso così:
$(p(0)^^ (AAn in NN, p(n)=>p(n+1)))=>AAn in NN,p(n).$
Oppure ancor più in generale (ma meno comprensibile) l'induzione si può formulare così:
$((EEk:p(k))^^ (AAn: n in NN ^^n>=k, p(n)=>p(n+1)))=>AAn: n in NN^^n>=k,p(n).$
E qui sì che devi aggiungere una nuova lettera $k$, perché è la base dell'induzione ed è un valore fissato, può variare a seconda dell'enunciato, ma all'interno di una dimostrazione e all'interno del passo induttivo viene fissato, è quello da cui "parte" l'induzione.
In modo molto esotico, avresti potuto pure scrivere:
$(p(0)^^ (AAT in NN, p(T)=>p(T+1)))=>AAdelta in NN,p(delta)$
è chiaro che però aumentando le lettere strane la formula risulta meno comprensibile e dato che stiamo parlando di numeri naturali, la $n$ è sempre quella che assicura una comprensione più facile di quello che stiamo dicendo...
Quindi quello che sta scritto nel tuo libro va più che bene.
Quello che mi urta della formula che hai riportato dal libro è che non specifica dove sta questo $k$ o $n$ che dir si voglia.
E' ovvio che, avendo preso lo zero come base per la tua induzione, questo $n$ stia in $NN$, ma bisognerebbe riscriverla in modo più preciso così:
$(p(0)^^ (AAn in NN, p(n)=>p(n+1)))=>AAn in NN,p(n).$
Oppure ancor più in generale (ma meno comprensibile) l'induzione si può formulare così:
$((EEk:p(k))^^ (AAn: n in NN ^^n>=k, p(n)=>p(n+1)))=>AAn: n in NN^^n>=k,p(n).$
E qui sì che devi aggiungere una nuova lettera $k$, perché è la base dell'induzione ed è un valore fissato, può variare a seconda dell'enunciato, ma all'interno di una dimostrazione e all'interno del passo induttivo viene fissato, è quello da cui "parte" l'induzione.
In modo molto esotico, avresti potuto pure scrivere:
$(p(0)^^ (AAT in NN, p(T)=>p(T+1)))=>AAdelta in NN,p(delta)$
è chiaro che però aumentando le lettere strane la formula risulta meno comprensibile e dato che stiamo parlando di numeri naturali, la $n$ è sempre quella che assicura una comprensione più facile di quello che stiamo dicendo...
Quindi quello che sta scritto nel tuo libro va più che bene.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo