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]

Sì, probabilmente mi sbagliavo

[algibro]

Sto provando a seguirvi, con fatica.
Credo di aver capito che il nocciolo della questione sia stabilire una relazione di ordine totale tra coppie di naturali $(m,n),(m',n') \in \mathbb{N}^2$ che sia adatta per verificare la monotonia di $g$, ovvero una relazione d'ordine che non crei problemi laddove si voglia stabilire se:

$\forall (m,n),(m',n') \in \mathbb{N}^2, (m,n)<(m',n') \Rightarrow g(m,n)

Escluso l'ordine lessicografico, mi si suggerisce di osservare che:

"G.D.":
Ecco perché suggerivo di considerare che

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

E cosi ritorno alla precedente definizione di iniettività:

$\forall (m,n),(m',n') \in \mathbb{N}^2, g(m,n)=g(m',n') \Rightarrow (m,n)=(m',n')$

$m+\frac{(m+n)(m+n+1)}{2}=m'+\frac{(m'+n')(m'+n'+1)}{2}$
$1+2+3+...+(m+n)+m=1+2+3+...+(m'+n')+m'$
$(m+n)=(m'+n') \wedge m=m' \Rightarrow (m,n)=(m',n')$

Cita

Segnala

[G.D.5]

"algibro":Sto provando a seguirvi, con fatica.
Credo di aver capito che il nocciolo della questione sia stabilire una relazione di ordine totale tra coppie di naturali $(m,n),(m',n') \in \mathbb{N}^2$ che sia adatta per verificare la monotonia di $g$, ovvero una relazione d'ordine che non crei problemi laddove si voglia stabilire se:

$\forall (m,n),(m',n') \in \mathbb{N}^2, (m,n)<(m',n') \Rightarrow g(m,n)

Il nocciolo della questione è provare l'iniettività di \( g \). Per farlo o sfrutti i legame tra stretta monotonia ed iniettività o trovi un'altra strada. Nel momento in cui scegli di optare per il legame tra stretta monotonia ed iniettività, devi stabilire una relazione d'ordine totale sul dominio, una sul codominio ed assicurarti che l'applicazione data conservi gli ordinamenti. Ovviamente gli ordinamenti stabiliti non devono creare problemi, per così dire, operativi.

"algibro":

Escluso l'ordine lessicografico, mi si suggerisce di osservare che:
[quote="G.D."]
Ecco perché suggerivo di considerare che

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

E cosi ritorno alla precedente definizione di iniettività:

$\forall (m,n),(m',n') \in \mathbb{N}^2, g(m,n)=g(m',n') \Rightarrow (m,n)=(m',n')$

[algibro]

Non ho argomentato perché non ne ero convinto affatto

Intuitivamente ho pensato che le somme dei primi $a \in \mathbb{N}$ numeri naturali e dei primi $a' \in \mathbb{N}$ numeri naturali si eguagliano se e solamente se $a=a'$.
[nota]$h:\mathbb{N} \mapsto \mathbb{N}, h(a)=\frac{a(a+1)}{2}$
è una funzione monotona strettamente crescente e quindi iniettiva:
$\forall a,a' \in \mathbb{N}, a
Quindi considerando $a=m+n$ e $a'=m'+n'$ ho pensato che la funzione
$h: \mathbb{N}^2 \mapsto \mathbb{N}, h(m,n)= \frac{(m+n)(m+n+1)}{2}$
è una funzione monotona strettamente crescente e pertanto iniettiva:
$\forall (m,n),(m',n') \in \mathbb{N}^2, (m+n)<(m'+n') \Rightarrow (m+n+1)<(m'+n'+1) \Rightarrow (m+n)(m+n+1)<(m'+n')(m'+n'+1) \Rightarrow \frac{(m+n)(m+n+1)}{2} < \frac{(m'+n')(m'+n'+1)}{2}$
Ora ho pensato che definendo una funzione $o(a)$ che, per fissato un naturale $a$, associa un naturale $a+m$ con $m \leq a$, abbiamo che se $a+m=a+m' \Rightarrow m=m'$
Riepilogando $\frac{a(a+1)}{2} = \frac{a'(a'+1)}{2} \Rightarrow a=a'$ e
$\frac{a(a+1)}{2}+m = \frac{a(a+1)}{2}+m' \Rightarrow m=m'$

Ma solo io ho difficoltà con questa iniettività !?
Eppure tutti gli altri esercizi svolti finora li ho affrontati senza problemi.

Ad ogni modo sto anche pensando a come definire una relazione di ordine totale tra coppie di naturali da poter utilizzare per dimostrare la stetta monotonia e conseguentemente l'iniettività di questa benedetta $g$.

[algibro]

Attenzione, forse ci sono.
Ho notato che ci sono $(m+n)$ possibilità di scrivere una coppia $(m,n)$ di naturali la cui somma è, appunto, $(m+n)$.
Ad esempio, ci sono $4$ coppie differenti di naturali la cui somma è $4$:
$(1,3)(2,2)(3,1)(4,0)$
Dove, il primo elemento di ogni coppia si differenzia dall'altro primo elemento in quanto, tutti i primi elementi delle coppie sono in successione da $1$ a $(m+n)$.
Quindi, appurato ormai che $\forall (m,n), (m',n') \in \mathbb{N}^2, \frac{(m+n)(m+n+1)}{2} = \frac{(m'+n')(m'+n'+1)}{2} \Rightarrow (m,n)=(m',n')$
abbiamo che detta somma non può essere scritta da due distinte coppie aventi il solo primo elemento uguale, quindi:
$\frac{(m+n)(m+n+1)}{2}+m = \frac{(m'+n')(m'+n'+1)}{2}+m' \Rightarrow (m,n)=(m',n')$

Festeggio ?
Mi aiutate a formalizzare meglio ?

Grazie infinite.