Dimostrare biiezione di una $f: \mathbb{N^2} \to \mathbb{N}$

[algibro]

Scusate in anticipo la banalità del problema.
Voglio dimostrare che la seguente funzione è una corrispondenza biunivoca.

$f: \mathbb{N^2} \mapsto \mathbb{N}, f(m,n)=2^m(2n+1)-1$
So che $f$ è iniettiva quando per ogni $x \in \mathbb{N}$ esiste al massimo una sola coppia $(m,n) \in \mathbb{N^2}$ tale che $2^m(2n+1)-1=x$, ossia è iniettiva quando se $f(m,n)=f(m',n') \Rightarrow (m,n)=(m',n')$.
Pertanto imposto la seguente uguaglianza.
$2^m(2n+1)-1=2^{m'}(2n'+1)-1$
$2^m(2n+1)=2^{m'}(2n'+1)$
Come procedo per dedurne che $m=m'$ e $n=n'$ ?

Inoltre, per verificare che $f$ è suriettiva.
Devo dimostrare che $\forall x \in \mathbb{N} \exists (m,n) \in \mathbb{N^2} : x=2^m(2n+1)-1$
Come posso procedere ?

[killing_buddha]

Dato $x$, dividi $x+1$ per la massima potenza di $2$ possibile. Questo è $m$. Il restante numero è per forza dispari, e quindi della forma $2n+1$ per un unico $n$.

[algibro]

"killing_buddha":Dato $x$, dividi $x+1$ per la massima potenza di $2$ possibile. Questo è $m$. Il restante numero è per forza dispari, e quindi della forma $2n+1$ per un unico $n$.

Certo.
Perché se $x$ è pari allora $x+1$ è dispari e quindi l'unico suo divisone nella forma $2^m$ è con $m=0$, dunque $(x+1)/1$ è dispari nella forma $2n+1$.
Se invece $x$ è dispari e quindi $x+1$ è pari, quest'ultimo è di certo esprimibile come $2^m$ per un certo $m \in \mathbb{N}$ e quindi $2n+1=1$ con $n=0$.

Per l'iniettività ? Ci provo.

Grazie infinite.

[algibro]

Per l'iniettività.

$2^m(2n+1)=2^{m'}(2n'+1)$
$2^{m-m'}={(2n'+1)}/{(2n+1)}$
Ma ${(2n'+1)}/{(2n+1)}$ è un rapporto tra due dispari mentre $2^{m-m'}$ è un pari, segue necessariamente che ${(2n'+1)}/{(2n+1)}=1 \Rightarrow n=n'$ e che $m-m'=0 \Rightarrow m=m'$

[algibro]

Ho quest'altra funzione per cui non riesco a dimostrarne l'iniettività.

$g:\mathbb{N^2} \mapsto \mathbb{N}, g(x)=m+{(m+n)(m+n+1)}/{2}$
Devo dimostrare che
$\forall (m,n),(x,y) \in \mathbb{N^2}, m+{(m+n)(m+n+1)}/{2}=x+{(x+y)(x+y+1)}/{2} \Rightarrow (m,n)=(x,y)$
La prima osservazione che mi viene in mente è che il prodotto $(m+n)(m+n+1)$ come anche $(x+y)(x+y+1)$ è sempre un pari e quindi divisibile per 2.
Una prima strada che ho provato è stata quella di chiedermi quando $(m+n)(m+n+1)=(x+y)(x+y+1)$.
Due prodotti sono uguali nelle seguenti ipotesi:
1) $(m+n)=(x+y) \wedge (m+n+1)=(x+y+1)$;
La seconda è vera se $(m+n)=(x+y)$ ma da qui non saprei come procedere.
2) $(m+n)=(x+y+1) \wedge (m+n+1)=(x+y)$.
E anche da qui non so come potrei procedere.
Ho anche osservato che $(m+n)(m+n+1)=(m+n)^2+(m+n)$ Pertanto avrei che:
$(m+n)^2+(m+n)=(x+y)^2+(x+y)$.
Ma anche con questa strada mi fermo qui.

[algibro]

"algibro":Ho quest'altra funzione per cui non riesco a dimostrarne l'iniettività.

$g:\mathbb{N^2} \mapsto \mathbb{N}, g(x)=m+{(m+n)(m+n+1)}/{2}$
Devo dimostrare che
$\forall (m,n),(x,y) \in \mathbb{N^2}, m+{(m+n)(m+n+1)}/{2}=x+{(x+y)(x+y+1)}/{2} \Rightarrow (m,n)=(x,y)$
La prima osservazione che mi viene in mente è che il prodotto $(m+n)(m+n+1)$ come anche $(x+y)(x+y+1)$ è sempre un pari e quindi divisibile per 2.
Una prima strada che ho provato è stata quella di chiedermi quando $(m+n)(m+n+1)=(x+y)(x+y+1)$.
Due prodotti sono uguali nelle seguenti ipotesi:
1) $(m+n)=(x+y) \wedge (m+n+1)=(x+y+1)$;
La seconda è vera se $(m+n)=(x+y)$ ma da qui non saprei come procedere.
2) $(m+n)=(x+y+1) \wedge (m+n+1)=(x+y)$.
E anche da qui non so come potrei procedere.
Ho anche osservato che $(m+n)(m+n+1)=(m+n)^2+(m+n)$ Pertanto avrei che:
$(m+n)^2+(m+n)=(x+y)^2+(x+y)$.
Ma anche con questa strada mi fermo qui.

Chi riesce a sbloccarmi questo problemino ? grazie in anticipo...

Aggiornamento: forse ci sono arrivato da solo...

[killing_buddha]

$g$ è monotona, quindi deve essere iniettiva.

[G.D.5]

"algibro":Per l'iniettività.

$2^m(2n+1)=2^{m'}(2n'+1)$
$2^{m-m'}={(2n'+1)}/{(2n+1)}$
Ma ${(2n'+1)}/{(2n+1)}$ è un rapporto tra due dispari mentre $2^{m-m'}$ è un pari, segue necessariamente che ${(2n'+1)}/{(2n+1)}=1 \Rightarrow n=n'$ e che $m-m'=0 \Rightarrow m=m'$

Credo che qui ci sia un errore. \( 2^{m - m'} \) non può essere pari: se lo fosse, dovrebbe esserlo anche \( \displaystyle \frac{2n'+1}{2n+1} \), da cui dovrebbe essere pari anche \( 2n'+1 \), il che non è possibile.

Da \( 2^{m} ( 2n+1) = 2^{m'} (2n'+1) \) segue che \( m = m' \): in caso contrario il numero a sinistra e quello a destra non avrebbero lo stesso numero di \( 2 \). Allora \( \displaystyle \frac{2n'+1}{2n+1} = 1 \), da cui \( 2n'+1 = 2n+1 \) ed infine \( n'=n \).

[algibro]

"G.D.":[quote="algibro"]Per l'iniettività.

$2^m(2n+1)=2^{m'}(2n'+1)$
$2^{m-m'}={(2n'+1)}/{(2n+1)}$
Ma ${(2n'+1)}/{(2n+1)}$ è un rapporto tra due dispari mentre $2^{m-m'}$ è un pari, segue necessariamente che ${(2n'+1)}/{(2n+1)}=1 \Rightarrow n=n'$ e che $m-m'=0 \Rightarrow m=m'$

Credo che qui ci sia un errore. \( 2^{m - m'} \) non può essere pari: se lo fosse, dovrebbe esserlo anche \( \displaystyle \frac{2n'+1}{2n+1} \), da cui dovrebbe essere pari anche \( 2n'+1 \), il che non è possibile.

Da \( 2^{m} ( 2n+1) = 2^{m'} (2n'+1) \) segue che \( m = m' \): in caso contrario il numero a sinistra e quello a destra non avrebbero lo stesso numero di \( 2 \). Allora \( \displaystyle \frac{2n'+1}{2n+1} = 1 \), da cui \( 2n'+1 = 2n+1 \) ed infine \( n'=n \).[/quote]

Scusami ma come può essere dispari $2^{m-m'}$ ?
Il ragionamento che avevo impostato era questo.
Partendo dal fatto che $2^{m-m'}={(2n'+1)}/{(2n+1)}$ ed essendo il membro a sinistra sempre pari e quello a destra sempre dispari l'unica possibilità affinché l'uguaglianza valga è che $m-m'=0$ così che $2^0=1$ e che ${(2n'+1)}/{(2n+1)}=1$.
Grazie per l'aiuto G.D.

[G.D.5]

Prima dici

"algibro":
essendo il membro a sinistra sempre pari...

e poi dici

"algibro":
così che \( 2^{0} = 1 \)

[algibro]

"G.D.":Prima dici

[quote="algibro"]
essendo il membro a sinistra sempre pari...

e poi dici

"algibro":
così che \( 2^{0} = 1 \)

[/quote]

Hai ragione, in effetti ho scritto da cani. Il concetto era "è sempre pari eccezione fatta per l'unico caso in cui l'esponente è zero, il che implica che m ed m' siano uguali. Grazie

[G.D.5]

"algibro":
Hai ragione, in effetti ho scritto da cani. Il concetto era "è sempre pari eccezione fatta per l'unico caso in cui l'esponente è zero, il che implica che m ed m' siano uguali. Grazie

Scritta così però è scritta anche peggio: il fatto che una potenza di \( 2 \) ad esponente naturale è un numero pari tranne nel caso in cui l'esponente è \( 0 \), non implica proprio niente. Per lo meno non autonomamente.

[algibro]

"G.D.":[quote="algibro"]
Hai ragione, in effetti ho scritto da cani. Il concetto era "è sempre pari eccezione fatta per l'unico caso in cui l'esponente è zero, il che implica che m ed m' siano uguali. Grazie

Scritta così però è scritta anche peggio: il fatto che una potenza di \( 2 \) ad esponente naturale è un numero pari tranne nel caso in cui l'esponente è \( 0 \), non implica proprio niente. Per lo meno non autonomamente.[/quote]

compreso perfettamente, grazie !

"killing_buddha":$g$ è monotona, quindi deve essere iniettiva.

Bene, che fosse monotona l'avevo intuito, ma non riesco a convincermene attraverso dimostrazione.

Ad esempio, è ovvio che $\forall (m,n),(x,y) \in \mathbb{N}^2$ con $m \frac{(m+n)(m+n+1)}{2}<\frac{(x+y)(x+y+1)}{2} \Rightarrow m+\frac{(m+n)(m+n+1)}{2}
Altrettanto ovvio che $\forall (m,n),(x,y) \in \mathbb{N}^2$ con $m=y
Ancona, $\forall (m,n),(x,y) \in \mathbb{N}^2$ con $my$ allora se $m+n=x+y \Rightarrow m+\frac{(m+n)(m+n+1)}{2} < x+\frac{(x+y)(x+y+1)}{2}$

Il problema è quando voglio verificare che
$\forall (m,n),(x,y) \in \mathbb{N}^2$ con $my$ e $m+n > x+y \Rightarrow m+\frac{(m+n)(m+n+1)}{2} \ne x+\frac{(x+y)(x+y+1)}{2}$

[killing_buddha]

Che definizione di monotonìa stai applicando? Verificare le ultime tre condizioni non significa assolutamente nulla.

[G.D.5]

Non è più semplice osservare che

\[
\frac{(m+n)(m+n+1)}{2} = 1 + 2 + 3 + \cdots + (m+n)
\]

?

[algibro]

Intanto ringrazio entrambi per la pazienza, da non studente ma semplice appassionato ci metto un pochino per comprendere.
Ad ogni modo,
stavo cercando di verificare che
$\forall (m,n),(x,y) \in \mathbb{N}^2, (m+n)<(x+y) \Rightarrow g(m,n) A questo punto ho pensato che se la funzione fosse stata
$g(m,n)=\frac{(m+n)(m+n+1)}{2}$
sarebbe stato abbastanza facile verificare la monotonia.
Quello che mi ha indotto ad affrontare più ipotesi è stata la somma del primo elemento $m$, della coppia ordinata $(m,n)$, a
$\frac{(m+n)(m+n+1)}{2}$,
per cui mi sono chiesto: nel caso in cui prendo due coppie di naturali $(m,n),(x,y)$ con $m>x, n $\frac{(m+n)(m+n+1)}{2}<\frac{(x+y)(x+y+1)}{2}$
chi mi assicura che sommando $m$ al primo membro e $x$ al secondo membro, essendo $m>x$, la disuguaglianza rimane vera ?
Allora mi sono detto che rimane vera se
$\frac{(x+y)(x+y+1)}{2}-\frac{(m+n)(m+n+1)}{2}>(m-x)$

Ma il più piccolo naturale che può scaturire dalla differenza $\frac{(x+y)(x+y+1)}{2}-\frac{(m+n)(m+n+1)}{2}$ lo otteniamo quando $(x+y)=(m+n+1)$ ed in questo caso abbiamo che
$\frac{(m+n+1)(m+n+2)}{2}-\frac{(m+n)(m+n+1)}{2}=(m+n+1)>(m-x)$
che è la conclusione a cui volevo arrivare (forse inutilmente !?)

[G.D.5]

"algibro":
Ad ogni modo,
stavo cercando di verificare che
$\forall (m,n),(x,y) \in \mathbb{N}^2, (m+n)<(x+y) \Rightarrow g(m,n)

Non è questo ciò che devi verificare. Verificare che la funzione \( g \) è (strettamente) monotona significa verificare che:

\[
\forall (m,n), (x,y) \in \mathbb{N}^{2}, (m,n)<(x,y) \implies g(m,n) \]

Al che si pone il problema di come definire la relazione d'ordine \( < \) tra coppie: il modo più semplice (secondo me) di definire l'ordinamento tra coppie è ricorrere all'ordinamento lessicografico.

Questo tipo di ordinamento porta però a situazioni "strane", e.g. questa: se prendo le coppie \( (1,5) \) e \( (2,3) \), ho che \( 1 < 2 \), quindi \( (1,5) < (2,3) \), epperò

\[
1 + \frac{(1+5)(1+5+1)}{2} = 22 > 17 = 2 + \frac{(2+3)(2+3+1)}{2}
\]

Ecco perché suggerivo di considerare che

\[
\frac{(m+n)(m+n+1)}{2} = 1 + 2 + 3 + \cdots + (m+n)
\]

[killing_buddha]

"G.D.":
Al che si pone il problema di come definire la relazione d'ordine \( < \) tra coppie: il modo più semplice (secondo me) di definire l'ordinamento tra coppie è ricorrere all'ordinamento lessicografico.

Sbagliato: l'ordine lessicografico non ha la proprietà universale del prodotto, perché le proiezioni sui fattori non sono funzioni monotone: in \(\{a,\dots,z\}^{21}\) "asbesto" è minore di "baracca", ma \(s\not\le a\). La scelta giusta, quella cioè equipaggia \((P\times Q, \le)\) con la giusta proprietà universale, è il prodotto sulle componenti, ovvero quello per cui $(p,q)\le (p',q')$ se e solo se $p\le p'$ e $q\le q'$. Qui c'è un survey sulle proprietà categoriali di \(\bf Pos\).

[G.D.5]

Premesso che ho dato un'occhiata alle proprietà categoriali di \( \bf{Pos} \) senza capirci alcunché, dato che le mie conoscenze di Teoria delle Categorie sono praticamente nulle, mi pare però che anche questo ordinamento tra coppie non risolva il problema in oggetto: correggimi se sbaglio ma data un'applicazione strettamente monotona tra due insiemi ordinati, per affermare che questa applicazione è iniettiva occorre anche l'ipotesi che gli ordinamenti siano totali e l'ordinamento che proponi, per quanto migliore di quello lessicografico, non è totale. O mi sfugge qualcosa?

[killing_buddha]

Mi sembra sia sufficiente che l'ordinamento sul codominio sia totale

[G.D.5]

Non credo. Se per esempio prendo:
• \( S = \{ (1,2), (3,4), (5,6), (0,7) \} \) con l'ordinamento tra coppie come da tue indicazioni;
• \( T = \{ 1, 2, 3, 4 \} \) con l'usuale ordinamento tra naturali;
• \( f \colon S \to T \) t.c. \( f(1,2)=1, f(3,4)=2, f(5,6)=3, f(0,7)=1 \);
ho un'applicazione monotona tra i due insiemi ordinati \( S \) (parzialmente) e \( T \) (totalmente) ma non iniettiva. Giusto?