Serve la doppia induzione? Direi di no...

[G.D.]

Salve a tutti. Stavo leggendo di una nota proprietà dei numeri di Fibonacci (i.e. $F_{m+n}=F_{m-1}F_{n}+F{m}F_{n+1}$) e della sua dimostrazione per Induzione: io sarei partito sparato con una doppia induzione (prima su $n$ e poi su $m$, o viceversa), quando leggo nella dimostrazione della predetta proprietà che ciò non occorre, basta infatti fissare $m$ e indurre su $n$, senza poi indurre successivamente su $m$ fissando $n$, dacché formalmente si prova che $S=\{n \in \mathbb{N}: \forall m \in \mathbb{N}, F_{m+n}=F_{m-1}F_{n}+F_{m}F_{n+1}\}$.
Quando leggevo questo fatto, stavo anche pensando a una dimostrazione per induzione del fatto che $((m),(k))\in \mathbb{N}$ (quesito posto da silente in Superiori), dove pure ci sono due parametri naturali, ma una evetuale induzione va fatta solo su $n$ data la caratterizzazione di $k$ (i.e. $0\leq k \leq n$), ma la mia mente è andata a questo quesito che posi tempo fa, il quale si concluse con la conclamata necessità di operare una doppia induzione. Ma alla luce di quanto detto all'esordio di questo topic, anche per risolvere la questione posta nel mio topic sulle proprietà delle potenze cui ho fatto riferimento non è necesssario indurre due volte (una su $n$ e l'altra su $m$): a conforto di ciò trovo che nelle dispense di Analisi del prof.re assegnatoci per un mese a inizio A.A. le proprietà delle potenze vendono provate con l'induzione solo un prametro: e.g.
$x^{n}x^{m}={(x^{n}x=x^{n+1}, \text{se} m=1),(x^{n}x^{m-1}x=x^{n+m-1}x=x^{n+m}, \text{se} m>1):}$.
Detto questo, tornando al titolo, e riferendoci alla dimostrazione della proprietà dei Fibonacci e/o alle proprietà delle potenze nel topic linkato, la doppia induzione occorre?
A voi la parola

[G.D.]

Piccolo uppino.
Aggiungo anche questo link, nel quale si espongono due strategie per la doppia induzione. A che, la domanda è: perché nei due esempi del precedente post (i.e. le proprietà delle potenze e i numeri di Fibonacci) la doppia induzione non occorre pur essendovi due indici naturali?

P.S.
Dato che questo forum deve essere rimosso e il topic era stato aperto prima di questo annuncio, magari qualche mods lo può spostare dove più ritiene opportuno.

P.P.S.
Ringrazio il moderatore che ha gentilmente accolto la richiesta del P.S.

[fields]

Per applicare l'induzione standard, uno dovrebbe innanzituttto aver chiara qual e' esattamente la formula che desidera provare per induzione e specificare rispetto a quale variabile effettua l'induzione. Il fatto che ci siano altre mille variabili non ha nessuna importanza. L'induzione, data una formula $A(x)$, e data una dimostrazione di $A(0)$ e di $\forall x A(x)\rightarrow A(x+1)$, ti permette di concludere $\forall x A(x)$, che ci siano o meno altre mille variabili oltre a $x$ in $A(x)$.

Inoltre, c'e' una regola logica che ti permette di concludere $\forall y B(y)$, ogniquavolta dimostri che $B(y)$ e' vera senza fare ipotesi su che numero e' $y$ (i.e., $y$ e' arbitrario).

Vediamo come applicare il macchinario logico. Nel caso della proprieta' delle potenze, ad esempio, la dimostrazione e' per induzione standard e relativa alla formula:

$A(m) \equiv x^nx^m=x^{m+n}$

che dipende solo da $m$ per tua scelta.

Formalmente, dopo l'induzione, uno ha dimostrato solo $\forall m A(m)$. Siccome pero' $n$ e' arbitrario, uno puo' concludere

$\forall n \forall m A(m)\equiv\forall n \forall m x^nx^m=x^{n+m}$.



D'altra parte nessuno ti impedisce di considerare la formula

$B(n,m)\equiv x^nx^m=x^{n+m}$

in cui consideri $n,m$ come due variabili distinte oggetto di induzione simultanea. Per tua scelta, applicherai l'induzione doppia.

[G.D.]

tre cose:

1) Quindi usare la singola o la doppia dipende da quanto ci si vuole divertire con l'induzione, a patto che nella singola sia possibile dire "Questa variabile la posso lasciare totalmente arbitraria e casuale"?

2)

Inoltre, c'e' una regola logica che ti permette di concludere $\forall y B(y)$, ogniquavolta dimostri che $B(y)$ e' vera senza fare ipotesi su che numero e' $y$ (i.e., $y$ e' arbitrario).

Posso chiederti, per pura curiosità, anche se molto probabilmente non ho gli strumenti per comprenderla, qual è questa regola? Diciamo l'enunciato di questa regola...

3) Wikipedia inglese propone questo breve accenno alla doppia induzione:

Induction on more than one counter
It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process. That is, one performs a basis step and an inductive step for n, and in each of those performs a basis step and an inductive step for m. See, for example, the proof of commutativity accompanying addition of natural numbers. More complicated arguments involving three or more counters are also possible.

Quanto esposto in Wiki è la strategy 1 del topic su MathLinks contenuto nel link del mio secondo post?


Grazie mille.

[fields]

1) Quindi usare la singola o la doppia dipende da quanto ci si vuole divertire con l'induzione, a patto che nella singola sia possibile dire "Questa variabile la posso lasciare totalmente arbitraria e casuale"?

Non esattamente, quello che dici vale solo per i tuoi esempi. In generale, l'induzione doppia, quando correttamente intesa, e' induzione transfinita fino all'ordinale $\omega^2$ (o induzione lessicografica su coppie ordinate). E' un esercizio non banale e delicato mostrare che essa si puo' derivare dagli assiomi di Peano e dall'induzione "singola".

Ho parlato di induzione doppia intesa correttamente, perche' nel link del tuo secondo post, ad esempio, sia la prima che la seconda strategia in realta' sono riconducibili ad una piu' banale induzione sulla singola quantita' m+n. Con quelle ipotesi, si poteva dimostrare direttamente per induzione singola su z la formula

$\forall z \forall m \forall n z=m+n-> P(m,n)$

che chiaramente implica $\forall m \forall n P(m,n)$

Inoltre, c'e' una regola logica che ti permette di concludere $\forall y B(y)$, ogniquavolta dimostri che $B(y)$ e' vera senza fare ipotesi su che numero e' $y$ (i.e., $y$ e' arbitrario).

Posso chiederti, per pura curiosità, anche se molto probabilmente non ho gli strumenti per comprenderla, qual è questa regola? Diciamo l'enunciato di questa regola...

La regola e' pari pari quella che ho enunciato. E' un assioma della logica.

3) Wikipedia inglese propone questo breve accenno alla doppia induzione:

Induction on more than one counter
It is sometimes desirable to prove a statement involving two natural numbers, n and m, by iterating the induction process. That is, one performs a basis step and an inductive step for n, and in each of those performs a basis step and an inductive step for m. See, for example, the proof of commutativity accompanying addition of natural numbers. More complicated arguments involving three or more counters are also possible.

Quanto esposto in Wiki è la strategy 1 del topic su MathLinks contenuto nel link del mio secondo post?

Wikipedia e' troppo vaga perche' la possa capire...

[G.D.]

Non esattamente, quello che dici vale solo per i tuoi esempi. In generale, l'induzione doppia, quando correttamente intesa, e' induzione transfinita fino all'ordinale $\omega^2$ (o induzione lessicografica su coppie ordinate). E' un esercizio non banale e delicato mostrare che essa si puo' derivare dagli assiomi di Peano e dall'induzione "singola".

Ho parlato di induzione doppia intesa correttamente, perche' nel link del tuo secondo post, ad esempio, sia la prima che la seconda strategia in realta' sono riconducibili ad una piu' banale induzione sulla singola quantita' m+n. Con quelle ipotesi, si poteva dimostrare direttamente per induzione singola su z la formula

$\forall z \forall m \forall n z=m+n-> P(m,n)$

che chiaramente implica $\forall m \forall n P(m,n)$

Innanzitutto ti ringrazio per le tue risposte. La storia della doppia induzione comincia a incuriosirmi: è una cosa che avrò piacere di vedere in un normale corso di logica all'università (magari nell'ambito di fondamenti della matematica) o per ammirarla bisogna scegliere un percorso di specializzazione dedicato alla logic?!

Ancora grazie e buon proseguimento di... nottata!

[fields]

La storia della doppia induzione comincia a incuriosirmi: è una cosa che avrò piacere di vedere in un normale corso di logica all'università (magari nell'ambito di fondamenti della matematica) o per ammirarla bisogna scegliere un percorso di specializzazione dedicato alla logic?!

L'induzione doppia, essendo un caso particolare di induzione transfinita, si studia ad esempio in teoria degli insiemi, e in particolare in teoria dei numeri ordinali di Cantor. Tuttavia si puo' anche trattare in modo elementare, come ho detto nell'Aritmetica di Peano. Anzi, mi soprendo se nei tuoi corsi non e' ancora stata studiata.

In logica si studiano anche teoremi piu' sottili e piu' difficili, come ad esempio il fatto che nell'Aritmetica di Peano - quindi con la sola induzione singola - si puo' dimostrare l'induzione transfinita fino ad ordinali soprendentemente grandi ($\omega$, $\omega^{\omega}$, $\omega^{\omega^\omega}$....), ma non fino a $\epsilon_0$, che il piu' piccolo ordinale maggiore di quelli sopraccitati.

Per curiosita', l'induzione fino a $\epsilon_0$ corrisponde ad un induzione sugli alberi infiniti numerabili senza rami infiniti. Intuitivamente, essendo in questi alberi i nodi infiniti e l'altezza non necessariamente limitata superiormente, l'induzione coinvolge principi infinitari non rappresentabili nell'aritmetica di Peano.

[G.D.]

Di tutte queste cose non ne ho avuto neppure un accenno

Se permetti, avrei ancora una curiosità.
Per dimostrare la proprietà commutativa dell'addizione in $NN$ dopo avere introdotto detto insieme con la terna di Peano, si ricorre ad una doppia induzione con le due induzioni ad incastro (la mia fonte è l'Acerbi-Buttazzo):

Poniamo $S={m \in NN : \forall n \in NN, m+n=n+m}$: per il passo 3 (*) sappiamo che $0 \in S$. Proviamo ora che se $m \in S$ anche $m^+ \in S$: poniamo $S_m ={n in NN: m^+ + n =n + m^+}$. Sempre per il passo 3 si ha $0 in S_m$; inoltre se $n in S_m$ abbiamo:

$m^+ +n^+ = (m^+ + n)^+ \ \ \ \ \ \ \ \ \ \text{definizione di} +$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=(n+m^+)^+ \ \ \ \ \ \ \ \ \ n in S_m$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=((n+m)^+)^+\ \ \ \ \ \ \ \ \ \text{definizione di} +$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=((m+n)^+)^+\ \ \ \ \ \ \ \ \ m \in S$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=(m+n^+)^+\ \ \ \ \ \ \ \ \ \text{definizione di} +$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=(n^+ + m)^+\ \ \ \ \ \ \ \ \ m \in S$
$\ \ \ \ \ \ \ \ \ \ \ \ \ \=n^+ + m^+\ \ \ \ \ \ \ \ \ \ \text{definizione di} +$

ovvero $n^+ in S$. Allora $S_m=NN$, cioè $m^+ in S$, e questo prova che $S=NN$.

Due domande:
1) Sbaglio o questa dimostrazione è l'applicazione della strategy 1 nel link a MathLinks del secondo mio post?
2) Sarebbe possibile procedere con una singola induzione? Cioè sarebbe possibile dire $m$ (oppure $n$) è arbitrario e vado con l'induzione solo su $n$ (risp. $m$)?



Ancora grazie.

__________________
Il passo 3 è un lemmino: il testo enuncia senza provare che $0$ è neutro per $+$.

[fields]

1) Sbaglio o questa dimostrazione è l'applicazione della strategy 1 nel link a MathLinks del secondo mio post?

No. Se noti, nel dimostrare $n^+\in S_m$, utilizzi due ipotesi induttive distinte, cioe' che $n\in S_m$ e $m\in S$. Nel post di mathlinks, invece, si usano due induzioni singole che dipendono ognuna da una sola ipotesi induttiva. Ecco perche' qui si tratta di un'induzione doppia "vera", annidata, mentre in mathlinks no, come ho gia' avuto modo di notare.

2) Sarebbe possibile procedere con una singola induzione? Cioè sarebbe possibile dire $m$ (oppure $n$) è arbitrario e vado con l'induzione solo su $n$ (risp. $m$)?

Ho un po' smanettato, e in effetti dico di si'. Puoi dimostrare la commutativita' dell'addizione usando solo induzioni semplici, non annidate. Se vuoi provarci, ecco qua la mia strada:

Lemma 1. $m^++n=m+n^+$

Lemma 2. $0+n=n+0$.

Teorema. $n+m=m+n$.

Ognuno dei risultati lo provi per induzione semplice; su quali variabili scoprilo tu...

[G.D.]

Lemma 1. Su $n$.
Lemma 2. Su $n$.
Lemma 3. Su $m$.
?