Doppia induzione
Avrei bisogno di qualche chiarimento su questa tecnica di dimostrazione-definizione.
Che io sappia, il principio di induzione è un assioma di Peano per $NN$ e dice:
se $S\subNN$, $0\inS$, ${[n\inS]\Rightarrow[(n+1)\inS]}$ allora $S=NN$.
La doppia induzione dovrebbe essere qualcosa di simile, ma per sottoinsiemi di $NNtimesNN$. Come funziona?
Che io sappia, il principio di induzione è un assioma di Peano per $NN$ e dice:
se $S\subNN$, $0\inS$, ${[n\inS]\Rightarrow[(n+1)\inS]}$ allora $S=NN$.
La doppia induzione dovrebbe essere qualcosa di simile, ma per sottoinsiemi di $NNtimesNN$. Come funziona?
Risposte
A occhio direi che se per ogni a gli insiemi {(x,a)} e {(a,x)} godono delle 2 proprietà allora $S= NN\times NN$
Vediamo di fare un esempio. Supponiamo di voler dimostrare che, se $K$ è un campo, nello spazio vettoriale $K[x,y]$ l'insieme $X={x^ny^m\ |\ n, m\inNN}$ è linearmente indipendente.
E' chiaro che $X$ non è vuoto. Definiamo un sottoinsieme $Y\subX$ come ${x^ny^m\ |\ {x^iy^j}_{0<=i<=n, 0<=j<=m}\ "sono lin. indip."}$. A parole un monomio è in $Y$ se l'insieme formato da tutti i monomi di grado minore o uguale è linearmente indipendente.
Chiamiamo l'insieme $S={(n,m)\inNNtimesNN\ |\ x^ny^m\inY}$. Dimostrare che $S=NNtimesNN$ è come dimostrare che $Y=X$. Per come è definito, $Y$ è linearmente indipendente, quindi $Y=X$ implica la tesi.
Passo base) $(0,0)$ è in $S$ per costruzione.
Passo induttivo) supponiamo che, $forall n\inNN$, $forall 0<=h,k<=n$ risulti $(h,k)\inS$.
Resta da dimostrare che allora $(n+1,n+1)\inS$.
Questo segue dalle formule dei gradi: $x^(n+1)y^(n+1)$ ha un grado più alto di qualsiasi combinazione lineare di monomi $x^hy^k$, con $0<=h,k<=n$. Perciò $x^(n+1)y^(n+1)$ non dipende linearmente da monomi di grado più basso, quindi $x^(n+1)y^(n+1)\inY$ ovvero $(n+1,n+1)\inS$.
Qualcuno avrebbe la pazienza di correggere quello che ho scritto? Naturalmente più che la parte di algebra lineare mi interessa l'impostazione del passo base e del passo induttivo. Grazie!
E' chiaro che $X$ non è vuoto. Definiamo un sottoinsieme $Y\subX$ come ${x^ny^m\ |\ {x^iy^j}_{0<=i<=n, 0<=j<=m}\ "sono lin. indip."}$. A parole un monomio è in $Y$ se l'insieme formato da tutti i monomi di grado minore o uguale è linearmente indipendente.
Chiamiamo l'insieme $S={(n,m)\inNNtimesNN\ |\ x^ny^m\inY}$. Dimostrare che $S=NNtimesNN$ è come dimostrare che $Y=X$. Per come è definito, $Y$ è linearmente indipendente, quindi $Y=X$ implica la tesi.
Passo base) $(0,0)$ è in $S$ per costruzione.
Passo induttivo) supponiamo che, $forall n\inNN$, $forall 0<=h,k<=n$ risulti $(h,k)\inS$.
Resta da dimostrare che allora $(n+1,n+1)\inS$.
Questo segue dalle formule dei gradi: $x^(n+1)y^(n+1)$ ha un grado più alto di qualsiasi combinazione lineare di monomi $x^hy^k$, con $0<=h,k<=n$. Perciò $x^(n+1)y^(n+1)$ non dipende linearmente da monomi di grado più basso, quindi $x^(n+1)y^(n+1)\inY$ ovvero $(n+1,n+1)\inS$.
Qualcuno avrebbe la pazienza di correggere quello che ho scritto? Naturalmente più che la parte di algebra lineare mi interessa l'impostazione del passo base e del passo induttivo. Grazie!
non so se sbaglio, ma se hai parlato di due "indici indipendenti", dovresti secondo me "scioglierli", nel senso che non puoi trattare n ed m come se fossero $"uguali"$. secondo me, basta metterli entrambi autonomamente nel "passo induttivo":
$AAn,m in NN," "AA h,k in NN " t. c. " 0 <= h <= n," " 0 <= k <= m$ risulti $(h,k) in S$
resta da dimostrare che $(n+1,m+1) in S$
che ne pensi? ciao.
$AAn,m in NN," "AA h,k in NN " t. c. " 0 <= h <= n," " 0 <= k <= m$ risulti $(h,k) in S$
resta da dimostrare che $(n+1,m+1) in S$
che ne pensi? ciao.
Penso che è proprio questo il punto che mi dà dei dubbi. Quindi, secondo il tuo intervento, la teoria sarebbe questa:
Supponiamo $S\subNNtimesNN$. Se $(0,0)\inS$, e per ogni $(n,m)\inNNtimesNN$ abbiamo che {$\forall 0<=h<=n, 0<=k<=m\ : (h,k)\inS$}(*), e anche $(n+1,m+1)\inS$ allora $S=NNtimesNN$.
Questo mi sembra sicuramente più convincente rispetto al mio $(n+1,n+1)$ (che mi suonava strano).
L'unica cosa che ancora non mi quadra è l'ipotesi marcata con (*) (tra graffe). Nell'induzione "normale" (quella su $NN$) questa ipotesi non c'è. Che dici, se la togliamo potrebbe funzionare lo stesso?
Supponiamo $S\subNNtimesNN$. Se $(0,0)\inS$, e per ogni $(n,m)\inNNtimesNN$ abbiamo che {$\forall 0<=h<=n, 0<=k<=m\ : (h,k)\inS$}(*), e anche $(n+1,m+1)\inS$ allora $S=NNtimesNN$.
Questo mi sembra sicuramente più convincente rispetto al mio $(n+1,n+1)$ (che mi suonava strano).
L'unica cosa che ancora non mi quadra è l'ipotesi marcata con (*) (tra graffe). Nell'induzione "normale" (quella su $NN$) questa ipotesi non c'è. Che dici, se la togliamo potrebbe funzionare lo stesso?
Formalizzo meglio la mia domanda.
Potrebbe essere vero che, se $S\subNNtimesNN$ tale che:
1) $(0,0)\inNNtimesNN$;
2) $(n,m)\inS\ \Rightarrow (n+1,m+1)\inS$;
allora $S=NNtimesNN$?
Potrebbe essere vero che, se $S\subNNtimesNN$ tale che:
1) $(0,0)\inNNtimesNN$;
2) $(n,m)\inS\ \Rightarrow (n+1,m+1)\inS$;
allora $S=NNtimesNN$?
nell'induzione normale ci sono due casi autonomi entrambi validi:
si parte sempre dal dimostrare una prima cosa.
poi si può dedurre la valididità del termine (n+1)-esimo o dalla validità dell'n-esimo o dalla validità dei primi n.
che io sappia è indifferente.
in ogni caso dalla verifica di una cosa e di una deduzione segue la validità per infiniti termini (che possono anche non essere tutti, dipende da come imposti lo schema).
nel caso di doppia implicazione a me spaventa di più l'aumento contemporaneo dei due indici piuttosto che l'esistenza di due variabili indici distinte.
io proverei piuttosto a separare $(n+1,m), (n,m+1), (n+1,m+1)$.
è meglio fermarci qui per ora. ciao.
si parte sempre dal dimostrare una prima cosa.
poi si può dedurre la valididità del termine (n+1)-esimo o dalla validità dell'n-esimo o dalla validità dei primi n.
che io sappia è indifferente.
in ogni caso dalla verifica di una cosa e di una deduzione segue la validità per infiniti termini (che possono anche non essere tutti, dipende da come imposti lo schema).
nel caso di doppia implicazione a me spaventa di più l'aumento contemporaneo dei due indici piuttosto che l'esistenza di due variabili indici distinte.
io proverei piuttosto a separare $(n+1,m), (n,m+1), (n+1,m+1)$.
è meglio fermarci qui per ora. ciao.
"dissonance":
Formalizzo meglio la mia domanda.
Potrebbe essere vero che, se $S\subNNtimesNN$ tale che:
1) $(0,0)\inNNtimesNN$;
2) $(n,m)\inS\ \Rightarrow (n+1,m+1)\inS$;
allora $S=NNtimesNN$?
se prendi la diagonale $D={(n,n)inNNtimesNN|n in NN}$ verifica le condizioni 1 e 2 ma $D!=NN$
credo, come è gia stato suggerito, che serva:
2) $(n,m)in S \Rightarrow (n+1,m) in S$
3) $(n,m)in S \Rightarrow (n,m+1) in S$
oltre alla tua una e 2,3 implicano la tua 2
Quindi, in termini terra-terra, con il mio post precedente arrivo a dire:
$(0,0)\inS$ per la 1). Per la 2) anche $(0+1,0+1)=(1,1)\inS$. Quindi anche $(1+1,1+1)=(2,2)\in S$ e così via. E perciò non posso dire che $S=NNtimesNN$, ma semmai che $S={(n,n)\ |\ n\inNN}$, cioè che $S$ è uguale alla cosiddetta diagonale di $NNtimesNN$. Hai ragione.
Per risolvere il problema, o aggiungo l'ipotesi
3) se $(n,m)\inS$ allora $(h,k)\inS$ per $0<=h<=n, 0<=k<=m$; (come dicevi prima, in $NN$ non è necessaria)
oppure devo modificare l'ipotesi 2) sostituendola con la
2*) $(n,m)\inS\ \Rightarrow\ (n+1,m), (n,m+1)\in S$; ($(n+1,m+1)\inS$ mi sembra superfluo);
Che dici? Va meglio?
(edit) scrivevo contemporaneamente a rubik. mi riferisco al precedente messaggio di adaBTTLS. Sembra comunque che la cosa sia in dirittura di arrivo, visto che anche rubik conferma quello che ho scritto. Resta da vedere la mia ipotesi 3) ... ma forse non è la strada giusta.
$(0,0)\inS$ per la 1). Per la 2) anche $(0+1,0+1)=(1,1)\inS$. Quindi anche $(1+1,1+1)=(2,2)\in S$ e così via. E perciò non posso dire che $S=NNtimesNN$, ma semmai che $S={(n,n)\ |\ n\inNN}$, cioè che $S$ è uguale alla cosiddetta diagonale di $NNtimesNN$. Hai ragione.
Per risolvere il problema, o aggiungo l'ipotesi
3) se $(n,m)\inS$ allora $(h,k)\inS$ per $0<=h<=n, 0<=k<=m$; (come dicevi prima, in $NN$ non è necessaria)
oppure devo modificare l'ipotesi 2) sostituendola con la
2*) $(n,m)\inS\ \Rightarrow\ (n+1,m), (n,m+1)\in S$; ($(n+1,m+1)\inS$ mi sembra superfluo);
Che dici? Va meglio?
(edit) scrivevo contemporaneamente a rubik. mi riferisco al precedente messaggio di adaBTTLS. Sembra comunque che la cosa sia in dirittura di arrivo, visto che anche rubik conferma quello che ho scritto. Resta da vedere la mia ipotesi 3) ... ma forse non è la strada giusta.
da (0,0) passi a (0,1) e a (1,0), dovresti riuscire a passare anche a (1,1)
secondo me la condizione che avevi indicato (*) tra parentesi graffe va utilizzata in più modi:
da h fino a n e da k=m puoi dedurre (h,m+1) con h fino a n
da h=n e k fino a m puoi dedurre (n+1,k) con k fino a m
da quelle precedenti puoi dedurre (n+1,m+1)
intendiamoci "puoi dedurre" va verificato (sono secondo me tre ipotesi induttive)
se vale $(0,0) in S$ e se valgono le tre ipotesi induttive (forse due come dite voi, ma va dimostrato che $(n+1,m+1) in S$ si possa dedurre dalle altre)
allora $S=NNtimesNN$.
ciao. a dopo.
secondo me la condizione che avevi indicato (*) tra parentesi graffe va utilizzata in più modi:
da h fino a n e da k=m puoi dedurre (h,m+1) con h fino a n
da h=n e k fino a m puoi dedurre (n+1,k) con k fino a m
da quelle precedenti puoi dedurre (n+1,m+1)
intendiamoci "puoi dedurre" va verificato (sono secondo me tre ipotesi induttive)
se vale $(0,0) in S$ e se valgono le tre ipotesi induttive (forse due come dite voi, ma va dimostrato che $(n+1,m+1) in S$ si possa dedurre dalle altre)
allora $S=NNtimesNN$.
ciao. a dopo.
Dovrei rifletterci un po'.
Io credo che con le ipotesi 1), 2), 3) di rubik arriviamo a dire che $S=NNtimesNN$.
Più che in termini logici come te, io sto cercando di ragionare in termini geometrici:
ipotesi 1)- S contiene l'origine;
ipotesi 2)- Per ogni ascissa fissata $n$, $S$ contiene tutti i punti a coordinate intere della semiretta ${(n,y)|y>=0}$;
ipotesi 3)- Per ogni ordinata fissata $m$, $S$ contiene tutti i punti a coordinate intere della semiretta ${(x,m)|x>=0}$;
e queste ultime due proposizioni seguono dal principio di induzione in $NN$ applicato alle singole coordinate. Siccome ogni punto a coordinate intere positive deve giacere su una semiretta di questo genere, $S=NNtimesNN$.
Penso anche che in queste condizioni, l'ipotesi che avevo marcato con {}(*) sia un'altra maniera di vedere le cose, che francamente non mi pare il caso di prendere in considerazione, visto che queste 1), 2), 3) sono più comode.
Non so se questo sia il modo migliore di procedere. Immagino di no, però purtroppo essendo io quasi del tutto sprovvisto di nozioni di logica, non riesco a fare di meglio. Se qualcuno nota qualche errore mi farebbe un favore nel farmelo notare. In caso contrario ringrazio di cuore adaBTTLS per il tempo che ha dedicato a questo topic!
Io credo che con le ipotesi 1), 2), 3) di rubik arriviamo a dire che $S=NNtimesNN$.
Più che in termini logici come te, io sto cercando di ragionare in termini geometrici:
ipotesi 1)- S contiene l'origine;
ipotesi 2)- Per ogni ascissa fissata $n$, $S$ contiene tutti i punti a coordinate intere della semiretta ${(n,y)|y>=0}$;
ipotesi 3)- Per ogni ordinata fissata $m$, $S$ contiene tutti i punti a coordinate intere della semiretta ${(x,m)|x>=0}$;
e queste ultime due proposizioni seguono dal principio di induzione in $NN$ applicato alle singole coordinate. Siccome ogni punto a coordinate intere positive deve giacere su una semiretta di questo genere, $S=NNtimesNN$.
Penso anche che in queste condizioni, l'ipotesi che avevo marcato con {}(*) sia un'altra maniera di vedere le cose, che francamente non mi pare il caso di prendere in considerazione, visto che queste 1), 2), 3) sono più comode.
Non so se questo sia il modo migliore di procedere. Immagino di no, però purtroppo essendo io quasi del tutto sprovvisto di nozioni di logica, non riesco a fare di meglio. Se qualcuno nota qualche errore mi farebbe un favore nel farmelo notare. In caso contrario ringrazio di cuore adaBTTLS per il tempo che ha dedicato a questo topic!
prego.
anch'io ho pensato ad una "copertura geometrica" di $NNtimesNN$ e sono convinta anch'io della superfluità della terza implicazione.
se posso permettermi, mi sembra che la forma di rubik renda meglio l'idea dell'indipendenza e della pari importanza delle singole ipotesi.
ciao.
anch'io ho pensato ad una "copertura geometrica" di $NNtimesNN$ e sono convinta anch'io della superfluità della terza implicazione.
se posso permettermi, mi sembra che la forma di rubik renda meglio l'idea dell'indipendenza e della pari importanza delle singole ipotesi.
ciao.
"adaBTTLS":
mi sembra che la forma di rubik renda meglio l'idea dell'indipendenza e della pari importanza delle singole ipotesi.
sistemato.
"adaBTTLS":
se posso permettermi...
ma certo! non crederai che possa offendermi! 
"dissonance":
Formalizzo meglio la mia domanda.
Potrebbe essere vero che, se $S\subNNtimesNN$ tale che:
1) $(0,0)\inNNtimesNN$;
2) $(n,m)\inS\ \Rightarrow (n+1,m+1)\inS$;
allora $S=NNtimesNN$?
Certamente! (ammesso che nella 1) tu intendessi $(0,0)\in S$).
Per vederlo dimostriamo per prima cosa che
se $S_0:={n : (0,n)\in S}$ allora $S_0=NN$.
Vediamolo per induzione:
1) $0\in S_0$ dato che $(0,0)\in S$ per l'ipotesi 1).
2) Se $n\in S_0$ allora $(0,n)\in S$, ma allora, per l'ipotesi 2), $(0,n+1)\in S$ cioè $n+1\in S_0$.
Dimostriamo ora che dato un qualsiasi $n$ e posto $S^n:={m: (m,n)\in S}$, allora si ha $S^n=NN$.
Di nuovo ragioniamo per induzione.
1) $0\in S^n$ perchè, per quanto visto al primo punto $(0,n)\in S$ (qualunque sia $n$);
2) se $m\in S^n$ allora $(m,n)\in S$, ma allora per l'ipotesi 2) $(m+1,n)\in S$ e cioè $m+1\in S^n$.
Dunque $S^n=NN$; dato che questo è vero per ogni $n$ abbiamo dimostrato che $S=NN\times NN$.
edit
Scusate mi sono accorto dopo che ci eravate arrivati da soli
edit
Riscusate, sono proprio cotto. Mi sono alzato apposta dal letto rendendomi conto della questione della diagonale e della necessità di trattare indipendentemente i due indici
e mi sono accorto solo ora che il problema era stato completamente sviscerato nei post precedenti. Meglio che vada a dormire.
@ dissonance
... per carità ...
solo che dai ringraziamenti precedenti mi era parso di ricevere pensione e buonuscita!
ciao.
... per carità ...
solo che dai ringraziamenti precedenti mi era parso di ricevere pensione e buonuscita!
ciao.
vabbé allora ti dico la verità: questo topic mi aveva proprio scocciato! quando siamo arrivati a una conclusione non mi è sembrato vero!!!
però mi sembrava una cosa un po' cafona dirlo proprio così, in fondo se mi sono scocciato io probabilmente è successo lo stesso anche a te ... da qui la sviolinata di prima!
Comunque penso che adesso sia tutto finito. Quando è intervenuto V.G.E. mi si è gelato il sangue
ma per fortuna ha confermato la conclusione precedente. Alla prossima!!!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo