Mappa da NxN a N
Salve a tutti,
sto cercando di dimostrare, senza utilizzare un ragionamento geometrico, che \(\displaystyle f(n,m)=\frac{(n+m)(n+m+1)}{2}+m \) è una mappa iniettiva.
Ho provato come si dovrebbe fare a verificare che \(\displaystyle f(n_1,m_1)=f(n_2,m_2) \Rightarrow (n_1,m_1)=(n_2,m_2) \). Per farlo ho scritto la funzione in una forma più comoda, ottenendo come condizione di uguaglianza di due generiche immagini la seguente:
(*) \(\displaystyle (S_1-S_2)(S_1+S_2+1)=2(m_2-m_1) \)
con \(\displaystyle S_1=n_1+m_1 \) e \(\displaystyle S_2=n_2+m_2 \).
Da questa si vede che se \(\displaystyle S_1=S_2 \) allora \(\displaystyle m_2=m_1 \) e di conseguenza anche \(\displaystyle n_2=n_1 \).
Allora mi basterebbe ora vedere cosa succede nei casi \(\displaystyle S_1>S_2 \) e \(\displaystyle S_1
Sospetto anche che esista una strada migliore di questa...
Un suggerimento?
Grazie in anticipo.
sto cercando di dimostrare, senza utilizzare un ragionamento geometrico, che \(\displaystyle f(n,m)=\frac{(n+m)(n+m+1)}{2}+m \) è una mappa iniettiva.
Ho provato come si dovrebbe fare a verificare che \(\displaystyle f(n_1,m_1)=f(n_2,m_2) \Rightarrow (n_1,m_1)=(n_2,m_2) \). Per farlo ho scritto la funzione in una forma più comoda, ottenendo come condizione di uguaglianza di due generiche immagini la seguente:
(*) \(\displaystyle (S_1-S_2)(S_1+S_2+1)=2(m_2-m_1) \)
con \(\displaystyle S_1=n_1+m_1 \) e \(\displaystyle S_2=n_2+m_2 \).
Da questa si vede che se \(\displaystyle S_1=S_2 \) allora \(\displaystyle m_2=m_1 \) e di conseguenza anche \(\displaystyle n_2=n_1 \).
Allora mi basterebbe ora vedere cosa succede nei casi \(\displaystyle S_1>S_2 \) e \(\displaystyle S_1
Sospetto anche che esista una strada migliore di questa...
Un suggerimento?
Grazie in anticipo.
Risposte
Si può procedere utilizzando la seguente uguaglianza:
Infatti:
$\sum_{k=1}^(n)k=(n(n+1))/2$
Infatti:
$((n_1+m_1)(n_1+m_1+1))/2+m_1=\sum_{k=1}^(n_1+m_1)k+m_1$
$((n_2+m_2)(n_2+m_2+1))/2+m_2=\sum_{k=1}^(n_2+m_2)k+m_2$
$((n_1+m_1)(n_1+m_1+1))/2+m_1=((n_2+m_2)(n_2+m_2+1))/2+m_2 rarr$
$rarr \sum_{k=1}^(n_1+m_1)k+m_1=\sum_{k=1}^(n_2+m_2)k+m_2 rarr$
$rarr \sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0$
Primo caso: $n_1+m_1=n_2+m_2=s$
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=1}^(s)k-\sum_{k=1}^(s)k+m_1-m_2=0] rarr [m_1=m_2] rarr [n_1=n_2]$
Secondo caso: $n_1+m_1 gt n_2+m_2$
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1]
^^ [m_1 lt m_2] ^^ [n_1 gt n_2] rarr$
^^ [m_1 lt m_2] ^^ [n_1 gt n_2] rarr$
$rarr \sum_{k=n_2+m_2+1}^(n_1+m_1)k$ non dipende da $n_1$ e da $n_2 rarr$ assurdo
Terzo caso: $n_1+m_1 lt n_2+m_2$
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=n_1+m_1+1}^(n_2+m_2)k=m_1-m_2]
^^ [m_1 gt m_2] ^^ [n_1 lt n_2] rarr$
^^ [m_1 gt m_2] ^^ [n_1 lt n_2] rarr$
$rarr \sum_{k=n_1+m_1+1}^(n_2+m_2)k$ non dipende da $n_1$ e da $n_2 rarr$ assurdo
Innanzitutto grazie mille per aver risposto.
Ci avevo provato anche io ad usare quell'uguaglianza ma non ero arrivato ugualmente a niente di buono.
Comunque non riesco a vedere bene dove sia l'assurdo nella tua dimostrazione, ad esempio prendiamo questo caso qui:
$ \sum_{k=n_2+m_2+1}^(n_1+m_1)k = m_2-m_1$ mica è assurda solo perchè $ \sum_{k=n_2+m_2+1}^(n_1+m_1)k $ non dipende dai due n
Infatti il percorso logico per arrivare lì è stato:
Impongo \(\displaystyle f(n_1,m_1)=f(n_2,m_2) \) per particolari coppie di naturali \(\displaystyle (n_1,m_1) \) e \(\displaystyle (n_2,m_2) \); come conseguenza, affinché succeda quello, deve succedere che:
$ \sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1 $
cioè devono esistere particolari \(\displaystyle n_1 \) e \(\displaystyle n_2 \) tali che quella somma sia pari a \(\displaystyle m_2-m_1 \).
Ad ogni modo l'assurdo è evidente riscrivendola un attimo per esteso:
\(\displaystyle (n_2+m_2+1)+(n_2+m_2+2)+(n_2+m_2+3)+...+(n_1+m_1)=m_2-m_1 \)
\(\displaystyle m_1+(n_2+1)+(n_2+m_2+2)+(n_2+m_2+3)+...+(n_1+m_1)=0 \)
che è assurdo perché sono tutti numeri naturali e quindi strettamente positivi.
Grazie ancora
Ci avevo provato anche io ad usare quell'uguaglianza ma non ero arrivato ugualmente a niente di buono.
Comunque non riesco a vedere bene dove sia l'assurdo nella tua dimostrazione, ad esempio prendiamo questo caso qui:
"anonymous_0b37e9":
Secondo caso: $ n_1+m_1 gt n_2+m_2 $
$ [\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1] ^^ [m_1 lt m_2] ^^ [n_1 gt n_2] rarr $
$ rarr \sum_{k=n_2+m_2+1}^(n_1+m_1)k $ non dipende da n1 e da n2→ assurdo
$ \sum_{k=n_2+m_2+1}^(n_1+m_1)k = m_2-m_1$ mica è assurda solo perchè $ \sum_{k=n_2+m_2+1}^(n_1+m_1)k $ non dipende dai due n
Infatti il percorso logico per arrivare lì è stato:
Impongo \(\displaystyle f(n_1,m_1)=f(n_2,m_2) \) per particolari coppie di naturali \(\displaystyle (n_1,m_1) \) e \(\displaystyle (n_2,m_2) \); come conseguenza, affinché succeda quello, deve succedere che:
$ \sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1 $
cioè devono esistere particolari \(\displaystyle n_1 \) e \(\displaystyle n_2 \) tali che quella somma sia pari a \(\displaystyle m_2-m_1 \).
Ad ogni modo l'assurdo è evidente riscrivendola un attimo per esteso:
\(\displaystyle (n_2+m_2+1)+(n_2+m_2+2)+(n_2+m_2+3)+...+(n_1+m_1)=m_2-m_1 \)
\(\displaystyle m_1+(n_2+1)+(n_2+m_2+2)+(n_2+m_2+3)+...+(n_1+m_1)=0 \)
che è assurdo perché sono tutti numeri naturali e quindi strettamente positivi.
Grazie ancora
A questo punto si può vedere anche che è biunivoca dimostrando la suriettività.
Credo di esserci riuscito, chiedo per favore un tuo parere.
Fissato un elemento \(\displaystyle f_0 \) nel codominio, devo far vedere che esso appartiene anche all'immagine, ovvero trovare una coppia \(\displaystyle (n_0,m_0) \) che raggiunge \(\displaystyle f_0 \).
Allora chiamo \(\displaystyle \mathcal{M} \) il seguente insieme:
\(\displaystyle \mathcal{M}=\left \{ m \in \mathbb{N}|m=f_0-\frac{S(S+1)}{2},S \in \mathbb{N} \right \} \)
Poiché è un sottoinsieme dei naturali esso ammette minimo, che chiamo \(\displaystyle m_0 \) a cui corrisponde un opportuno \(\displaystyle S_0 \).
Chiamo inoltre \(\displaystyle n_0=S_0-m_0 \).
Dunque: \(\displaystyle f(n_0,m_0)=\frac{(n_0+m_0)(n_0+m_0+1)}{2}+m_0=\frac{S_0(S_0+1)}{2}+f_0-\frac{S_0(S_0+1)}{2}=f_0 \).
Che ne dici?
Credo di esserci riuscito, chiedo per favore un tuo parere.
Fissato un elemento \(\displaystyle f_0 \) nel codominio, devo far vedere che esso appartiene anche all'immagine, ovvero trovare una coppia \(\displaystyle (n_0,m_0) \) che raggiunge \(\displaystyle f_0 \).
Allora chiamo \(\displaystyle \mathcal{M} \) il seguente insieme:
\(\displaystyle \mathcal{M}=\left \{ m \in \mathbb{N}|m=f_0-\frac{S(S+1)}{2},S \in \mathbb{N} \right \} \)
Poiché è un sottoinsieme dei naturali esso ammette minimo, che chiamo \(\displaystyle m_0 \) a cui corrisponde un opportuno \(\displaystyle S_0 \).
Chiamo inoltre \(\displaystyle n_0=S_0-m_0 \).
Dunque: \(\displaystyle f(n_0,m_0)=\frac{(n_0+m_0)(n_0+m_0+1)}{2}+m_0=\frac{S_0(S_0+1)}{2}+f_0-\frac{S_0(S_0+1)}{2}=f_0 \).
Che ne dici?
"Ianero":
... non riesco a vedere bene dove sia l'assurdo nella tua dimostrazione ...
Ciao. Dobbiamo dimostrare che:
$[((n_1+m_1)(n_1+m_1+1))/2+m_1=((n_2+m_2)(n_2+m_2+1))/2+m_2] rarr [n_1=n_2] ^^ [m_1=m_2]$
del tutto equivalente a:
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [n_1=n_2] ^^ [m_1=m_2]$
Ora, riprendendo il caso che tu stesso hai riportato:
Secondo caso: $n_1+m_1 gt n_2+m_2$
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1]$
essendo la sommatoria a primo membro sicuramente positiva, deve essere positivo anche il secondo:
$m_1 lt m_2$
Inoltre:
$[n_1+m_1 gt n_2+m_2] ^^ [m_1 lt m_2] rarr [n_1 gt n_2]$
In definitiva:
$[\sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1] ^^ [n_1+m_1 gt n_2+m_2] ^^ [m_1 lt m_2] ^^ [n_1 gt n_2]$
Fin qui non fa una piega. Per concludere è sufficiente osservare che la seguente uguaglianza:
$\sum_{k=n_2+m_2+1}^(n_1+m_1)k=m_2-m_1$
in cui, mentre il primo membro dipende da $n_1$ e da $n_2$, il secondo non ne dipende, deve essere falsa. Infatti, solo per fare un esempio:
$[m_1=3] ^^ [m_2=4] ^^ [n_1=7] ^^ [n_2=2] rarr [\sum_{k=7}^(10)k=1]$
manifestamente falsa. Insomma, essendo pervenuti ad un assurdo, l'ipotesi iniziale:
$n_1+m_1 gt n_2+m_2$
non deve essere presa nemmeno in considerazione. Poiché si possono fare le stesse considerazioni anche nel terzo caso, a verificarsi può essere solo il primo caso:
Primo caso: $n_1+m_1=n_2+m_2=s$
$[\sum_{k=1}^(n_1+m_1)k-\sum_{k=1}^(n_2+m_2)k+m_1-m_2=0] rarr [\sum_{k=1}^(s)k-\sum_{k=1}^(s)k+m_1-m_2=0] rarr [m_1=m_2] rarr [n_1=n_2]$
Francamente, non vedo problemi di natura logica in questo ragionamento.
"Ianero":
A questo punto si può vedere anche che è biunivoca dimostrando la suriettività ... Che ne dici?
Non mi convince. Piuttosto, procederei per induzione illustrando solo il secondo passo (il primo è banale):
Ipotesi
$EE (m,n) in NN^2 : k=((n+m)(n+m+1))/2+m$
Tesi
$EE (barm,barn) in NN^2 : k+1=((barn+barm)(barn+barm+1))/2+barm$
Dimostrazione
$[barm=m+1] ^^ [barn=n-1] rarr$
$rarr ((barn+barm)(barn+barm+1))/2+barm=((n-1+m+1)(n-1+m+1+1))/2+m+1=$
$=((n+m)(n+m+1))/2+m+1=k+1$
"anonymous_0b37e9":
Non mi convince. Piuttosto, procederei per induzione...
La tua è certamente più elegante.
Siccome sto cercando di imparare come vanno fatte per bene le dimostrazioni in matematica facendo questo tipo di esercizi, ti chiedo se nella mia ci fosse qualche errore che non riesco a vedere, per favore.
Grazie
"Ianero":
... chiamo \(\displaystyle \mathcal{M} \) il seguente insieme:
\(\displaystyle \mathcal{M}=\left \{ m \in \mathbb{N}|m=f_0-\frac{S(S+1)}{2},S \in \mathbb{N} \right \} \)
Poiché è un sottoinsieme dei naturali esso ammette minimo ...
Se $S in NN$, non si comprende il motivo per cui \(\displaystyle \mathcal{M} \) dovrebbe ammettere minimo.
Occorreva far vedere che quell'insieme \( \displaystyle \mathcal{M} \) contenesse almeno un elemento, per ogni \(\displaystyle f_0 \in \mathbb{N} \) scelto, giusto?
Hai già scritto che cosa occorre dimostrare:
Nella migliore delle ipotesi, come tu voglia procedere mi sembra piuttosto involuto.
"Ianero":
Fissato un elemento \(\displaystyle f_0 \) nel codominio, devo far vedere che esso appartiene anche all'immagine, ovvero trovare una coppia \(\displaystyle (n_0,m_0) \) che raggiunge \(\displaystyle f_0 \).
Nella migliore delle ipotesi, come tu voglia procedere mi sembra piuttosto involuto.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo