Principio induzione(altra forma)

[anto_zoolander]

We

Ho un problema con l'assimilare questa forma del principio di induzione, viene utilizzato per molte dimostrazioni nel mio libro, ad esempio: divisione euclidea, divisioni successive, MCD. Che mi servono per passare alle congruenze.

Ogni sottoinsieme $VsubseteqNN$ tale che

$(a).$ $0inV$

$(b).$ $ninV$ ogniqualvolta $kinV, forallk:0leqk
allora $V=NN$

Vedo di fare qualche passo.. considero $V={ninNN:p(n)$ è vera$}$

verifico se $0inV$ come passo base(?) e se risulta vera, suppongo che $p(n)$ sia vera per un generico $ninN$
ora al posto di provare che dall'essere vera $p(n)$ segue che è vera $p(n+1)$, che devo dimostrare?

devo trovare un $0leqk
ad esempio volendo dimostrare $p(n): 0+1+2+...+n=(n(n+1))/2$ con questa forma(?)

Faccio qualche altro passo così avete anche altro materiale per capire cosa non mi è chiaro:

$p(0): 0=0(1+0)/2$ il passo base è verificato per $n=0$

ora con la prima forma supporrei vera $p(n)$ per un generico $n$ e tento di dimostrare che dall'essere vera $p(n)=>p(n+1)$ vera.
Quì invece dovrei trovare un $0leqk Se così fosse, prenderei $(n-1)$ e cercherei di dimostrare che $p(n-1)$ è vera.

$p(n-1): 1+2+...+(n-1)=((n-1)n)/2$

$p(n-1): 1+2+...+(n-1)+n=((n-1)n)/2+n$ quì userei l'ipotesi...

$p(n-1): (n(n+1))/2=((n-1)n+2n)/2$

$p(n-1): (n(n+1))/2=(n(n-1+2))/2$ che è vera

attualmente quel "ogniqualvolta" lo interpreto come:

$kinNN:0leqkninV$ e si conclude che $V=NN$

aiuto

[FE7]

Mi sembra che il punto dove sbagli a capire sia che prendi un qualsiasi $k$ minore di $n$ , mentre invece l'ipotesi richiede "ogni $k$ minore di $n$ stia in $V$ ". Nota che comunque per avere $V=\mathbb{N}$ basterebbe chiedere che $n-1 in V$ implica $ n in V $ per ogni $n$, le due formulazioni sono equivalenti anche se una sembra "più forte".

[anto_zoolander]

Però se prendo il ragionamento 'dall'essere vera $p(n-1)$ si ha che:

$p(n-1)=>p(n)$

è equivalente alla prima forma. Solo che anziché dimostrare che sia vera per il successivo,dimostro che sia vera per un generico $n$. Solo che $n$ è il successivo di $n-1$ dunque sto dimostrando la stessa cosa.

Il discorso è che non so come tradurre il ragionamento $(b)$.

[G.D.5]

Questa forma del Principio di Induzione si chiama Principio di Induzione Forte e differisce dal Principio di Induzione solo per l'ipotesi del passo induttivo: mentre il Principio di Induzione fornisce come ipotesi induttiva l'appartenenza a \( S \subseteq \mathbb{N} \) solo del precedente di \( n + 1 \), il Principio di Induzione Forte fornisce come ipotesi induttiva l'appartenenza a \( S \subseteq \mathbb{N} \) non solo del precedente di \( n + 1 \) ma di tutti i numeri naturali minori di \( n + 1 \).

Il Principio di Induzione Forte fornisce cioè nel passo induttivo non una sola ipotesi induttiva (i.e. il valere di \( n \in S \)) ma più ipotesi induttive (i.e. il valere di \( 0 \in S \land 1 \in S \land 2 \in S \land \ldots \land n \in S \)), da cui la denominazione Forte.

[anto_zoolander]

Grazie appena ti è possibile, potresti farmi un esempio pratico?

Questa cosa di prendere come Ipotesi tutti i $kinNN:0leqk

Cita

Segnala

[G.D.5]

"anto_zoolander":Grazie appena ti è possibile, potresti farmi un esempio pratico?

Questa cosa di prendere come Ipotesi tutti i $kinNN:0leqk

Prima di scegliere l'esempio, in che senso "non ti cala"?

[anto_zoolander]

Traduco: 'non riesco a digerirlo'

Cioè attraverso il passo induttivo, suppongo che la proposizione sia vera per ogni $0leqk

Cita

Segnala

[G.D.5]

Precisamente. Ed è proprio il fatto che si assume che la proposizione sia vera non solo per il precedente di \( n \) ma in generale per tutti i naturali minori di \( n \) che porta ad appellarsi a tale forma di induzione come induzione forte. Anche se il termine più corretto sarebbe induzione sul decorso dei valori.

Ho però come l'impressione che non sia l'assunzione in sé a darti "fastidio".
Il problema è liceità dell'assunzione? Il senso dell'assunzione? Il fatto che non riesci a vedere come quest'assunzione possa innescare un "effetto domino" come quello innescato dall'induzione standard?

[anto_zoolander]

Si esattamente.
È proprio l'ultima che hai scritto.

[G.D.5]

Innanzitutto concedimi due premesse.


Date le proposizioni \( p \) e \( q \), l'implicazione \( p \implies q \) (per la quale \( p \) è l'antecedente e \( q \) il conseguente) è falsa solo quando \( p \) è vera e \( q \) è falsa: questo significa che se si sa che \( p \) è falsa, allora, indipendentemente dal valore di verità di \( q \), si può affermare che \( p \implies q \) è vera; viceversa se si sa che \( p \implies q \) è vera e \( p \) pure è vera, allora necessariamente deve essere vera anche \( q \). In particolare il fatto che dalla verità di \( p \implies q \) e di \( p \) si possa trarre la verità di \( q \) costituisce la più importante e la più utilizzata delle regole di deduzione della logica classica: il modus ponens.

Quando si quantifica sulla variabile di un predicato, volendo essere precisi, si dovrebbe per l'appunto quantificare sulla sola variabile e non su una relazione che coinvolge la variabile. In altri termini quando si scrive \( \forall x \in S, \mathscr{P}(x) \) oppure \( \exists x \in S: \mathscr{P}(x) \) si commettono degli abusi di notazione, che consistono in delle contrazioni, tollerati al punto da diventare convenzioni. In particolare \( \forall x \in S, \mathscr{P}(x) \) sta per \( \forall x \left ( x \in S \implies \mathscr{P}(x) \right ) \) e \( \exists x \in S: \mathscr{P}(x) \) sta per \( \exists x \left ( x \in S \land \mathscr{P}(x) \right ) \).


Ciò detto, il Principio di Induzione afferma che se \( S \subseteq \mathbb{N} \) è tale che:

(1) \( 0 \in \mathbb{N} \)
(2) \( \forall n \left ( n \in \mathbb{N} \implies n+1 \in \mathbb{N} \right ) \)

allora \( S = \mathbb{N} \).

In che modo si produce l'effetto domino?
Essendo vera la (1), allora \( 0 \in \mathbb{N} \), sicché la prima tessera del domino cade.
Poiché la (2) è vera ed è quantificata universalmente, allora per particolarizzazione essa è vera per \( n = 0 \), i.e. per \( n = 0 \) è vera l'implicazione \( 0 \in \mathbb{N} \implies 1 \in \mathbb{N} \) e, poiché sappiamo per la (1) che l'antecedente è vero, allora deve essere vero anche il conseguente, i.e. è vero che \( 1 \in \mathbb{N} \): cade così la seconda tessera.
La seconda tessera fa cadere la terza: ancora per particolarizzazione la (2) è vera anche per \( n = 1 \), i.e. è vera l'implicazione \( 1 \in \mathbb{N} \implies 2 \in \mathbb{N} \) e, poiché sappiamo che è vero che \( 1 \in \mathbb{N} \), allora deve essere vero che \( 2 \in \mathbb{N} \) e cade così anche la terza terza tessera.
Si ricomincia particolarizzando per \( n = 2 \) e si ottiene che \( n + 1 = 3 \in S \).
Iterando cadono tutte le tessere.

Con il Principio di Induzione Forte accade esattamente la stessa cosa: infatti le due forme sono equivalenti.

Il Principio di Induzione Forte afferma che se \( S \subseteq \mathbb{N} \) è tale che:

(a) \( 0 \in \mathbb{N} \)
(b) \( \forall n \left ( \forall k \left ( 0 \leq k \leq n \implies k \in S \right ) \implies n+1 \in S \right ) \)

allora \( S = \mathbb{N} \).

In che modo si produce l'effetto domino?
Essendo vera la (a), allora \( 0 \in \mathbb{N} \), sicché la prima tessera del domino cade.
Poiché la (b) è vera ed è quantificata universalmente, allora per particolarizzazione essa è vera per \( n = 0 \), i.e. per \( n = 0 \) è vera l'implicazione \( \forall k \left ( 0 \leq k \leq 0 \implies k \in S \right ) \implies 1 \in S \); consideriamo l'antecedente di questa implicazione, che a sua volta consta di un'implicazione, i.e. \( \forall k \left ( 0 \leq k \leq 0 \implies k \in S \right ) \): quando \( k = 0 \) l'implicazione diventa \( 0 \leq 0 \leq 0 \implies 0 \in S \) che è vera perché \( 0 \leq 0 \leq 0 \) è banalmente vera e \( 0 \in S \) è vera per mezzo di (a); quando \( k \neq 0 \) l'implicazione diventa \( 0 \leq h \leq 0 \implies h \in S \) (dove \( h \) è il particolare valore di \( k \) diverso da \( 0 \)) ed è ancora vera perché \( 0 \leq h \leq 0 \) (il suo antecedente) è falso (e quale sia il valore di verità di \( h \in S \) è irrilevante); allora \( \forall k \left ( 0 \leq k \leq 0 \implies k \in S \right ) \) è vero, sicché l'implicazione \( \forall k \left ( 0 \leq k \leq 0 \implies k \in S \right ) \implies 1 \in S \), che sappiamo essere vera, ha l'antecedente vero: possiamo allora dedurre che \( 1 \in S \) è vero e cade così la seconda tessera del domino.
La caduta della seconda tessera fa cadere la terza: ancora per particolarizzazione la (b) è vera anche per \( n = 1 \), i.e. è vera l'implicazione \( \forall k \left ( 0 \leq k \leq 1 \implies k \in S \right ) \implies 2 \in S \); consideriamo l'antecedente di questa implicazione, che a sua volta consta di un'implicazione, i.e. \( \forall k \left ( 0 \leq k \leq 1 \implies k \in S \right ) \): quando \( k = 0 \) l'implicazione diventa \( 0 \leq 0 \leq 1 \implies 0 \in S \) che è vera perché \( 0 \leq 0 \leq 1 \) è banalmente vera e sappiamo che \( 0 \in S \) è vero (per (a)); quando \( k = 1 \) l'implicazione diventa \( 0 \leq 1 \leq 1 \implies 1 \in S \) che è vera perché \( 0 \leq 1 \leq 1 \) è banalmente vera e sappiamo che \( 1 \in S \) è vero (la caduta della seconda tessera del domino); quando \( k > 1 \) l'implicazione diventa \( 0 \leq h \leq 1 \implies h \in S \) (dove \( h \) è il particolare valore di \( k \) maggiore di \( 1 \)) ed è ancora vera perché \( 0 \leq h \leq 1 \) (il suo antecedente) è falso (e quale sia il valore di verità di \( h \in S \) è irrilevante); allora \( \forall k \left ( 0 \leq k \leq 1 \implies k \in S \right ) \) è vero, sicché l'implicazione \( \forall k \left ( 0 \leq k \leq 1 \implies k \in S \right ) \implies 2 \in S \), che sappiamo essere vera, ha l'antecedente vero: possiamo allora dedurre che \( 2 \in S \) è vero e cade così la terza tessera del domino.
Si ricomincia particolarizzando per \( n = 2 \) e si ottiene che \( n + 1 = 3 \in S \).
Iterando cadono tutte le tessere.


La differenza tra le due forme di induzione è prettamente operativa: la prima forma dell'induzione è il prodursi di un effetto domino in cui si assiste prima alla caduta della tessera \( n \), e, sapendo che la distanza tra questa tessera e quella successiva, la tessera \( n + 1 \), è minore dell'altezza della tessera cadente, si attende e si osserva la caduta della tessera \( n + 1 \), dovendo osservare il processo a partire dalla caduta della tessera iniziale; nella forma forte dell'induzione invece si osserva la caduta della tessera \( n + 1 \) senza osservare direttamente la caduta delle tessere precedenti ma attendendo soltanto di vedere la tessera immediatamente precedente, la tessera \( n \), cadere per far cadere la tessera che stiamo osservando, potendo noi dunque affermare che sono cadute tutte le tessere fino alla \( n + 1 \)-esima perché sappiamo che le tessere fino alla \( n \)-esima sono già cadute. È come se la prima forma dell'induzione fosse un effetto domino osservato dal vivo in cui alla caduta della tessera \( n + 1 \) si può affermare che sono cadute tutte le tessere fino alla \( n + 1 \) perché sono state viste cadere una dopo l'altra; la forma forte dell'induzione è invece un'effetto domino registrato e poi guardato mandando direttamente il video al punto in cui cade la tessera \( n + 1 \): mandando il video direttamente in quel punto si vede che sono cadute tutte le tessere fino alla \( n \), si manda in play il video e si vede cadere la tessera \( n + 1 \) e allora si può affermare che sono cadute tutte le tessere fino alla tessera \( n + 1 \).


Un classico esempio in cui si vede l'utilità dell'induzione forte è il Teorema Fondamentale dell'Aritmetica: ogni numero maggiore di \( 1 \) si può scrivere come prodotto di numeri primi. La base dell'induzione è \( n = 2 \). Nel passo induttivo o \( n \) è primo oppure non lo è; se non lo è si può scrivere come prodotto tra due interi \( a \) e \( b \) entrambi minori di \( n \): siccome sono minori di \( n \) per essi vale la fattorizzazione in primi per ipotesi induttiva (l'ipotesi del passo induttivo) e quindi pure \( n \) è fattorizzabile in primi. Poiché \( a \) e \( b \) sono in due e sono minori di \( n \) ma non di un'unità, l'induzione normale non sarebbe servita.


Un'ultima nota di carattere squisitamente logico.
In verità il Principio di Induzione forte si può formulare anche con una sola clausola: i.e. per affermare \( S \subseteq \mathbb{N} \) coincide proprio con \( \mathbb{N} \), la sola condizione che \( S \) deve verificare è che \( \forall n \left ( \forall k \left ( 0 \leq k < n \implies k \in S \right ) \implies n \in S \right ) \): infatti se tale clausola è vera, allora, per particolarizzazione, è vera per \( n = 0 \), i.e. è vero che \( \forall k \left ( 0 \leq k < 0 \implies k \in S \right ) \implies 0 \in S \), dove l'antecedente di questa implicazione, i.e. \( \forall k \left ( 0 \leq k <0 \implies k \in S \right ) \), è banalmente vero, perché qualunque sia \( k \) la condizione \( 0 \leq k < 0 \) è sempre falsa e quindi \( 0 \leq k < 0 \implies k \in S \) è sempre vera, indipendentemente dal valore di verità di \( k \in S \), sicché possiamo dedurre che \( 0 \in S \) è vero. In altri termini, a rigor di logica, nell'induzione forte il passa base non serve se si riesce a produrre una prova della clausola \( \forall n \left ( \forall k \left ( 0 \leq k < n \implies k \in S \right ) \implies n \in S \right ) \) che sia veramente generale, che vada cioè bene per qualunque \( n \), compreso \( n = 0 \) o qualunque altro valore iniziale di \( n \) che dovrebbe fare da passo base. Questo cosa significa? Significa che quando la condizione (b) è data nella forma \( \forall n \left ( \forall k \left ( 0 \leq k < n \implies k \in S \right ) \implies n \in S \right ) \), in realtà il passo base non è un vero e proprio passo base ma un trattare a parte il caso \( n = 0 \) per assicurarsi di non fare pasticci; quando invece la (b) è data nella forma \( \forall n \left ( \forall k \left ( 0 \leq k \leq n \implies k \in S \right ) \implies n+1 \in S \right ) \), il passo base è un vero passo base, perché per \( n = 0 \) la verità di \( \forall k \left ( 0 \leq k \leq n \implies k \in S \right ) \) dipende dall'essere vero che \( 0 \in S \), come sopra mostrato.
A quale delle due forma dell'induzione forte attenersi allora, ti chiederai. È uguale: basta che quella che si usa si usa bene. In vero esistono anche altre varianti dell'induzione forte in cui si ricorre a più di un passo base: cioè prima di procedere al passo induttivo si prova più di un passo base e non solo \( n = 0 \).

[anto_zoolander]

Stupendo, grazie mille! Lo stampo e lo metto insieme alle dispense perchè è veramente ottimo. Grazie ancora!