Trovare biiezioni $NN->ZZ$ e $NN->QQ$

[Gi81]

1) Trovare una funzione biiettiva da $NN$ in $ZZ$
2) Trovare una funzione biiettiva da $NN$ in $QQ$

n.b.: la richiesta non è "dimostrare che esiste una funzione..."
in entrambi i casi bisogna scrivere esplicitamente la funzione.

Ovviamente si può svolgere anche solo il punto 1 ,o solo il punto 2.

[Pachisi]

Per la prima:

$$f(x) = \left\{\begin{array}{ll}
\frac{x}{2} & : x \text{pari}\\
-\frac{x-1}{2} & : x \text{dispari}
\end{array}
\right.$$

[robbstark1]

Non sono sicuro che la funzione che ho pensato per il secondo punto sia sufficientemente esplicita.

Costruisco prima una funzione iniettiva $QQ \to ZZ$, definita così:
$f(m/n) = 2^m 3^n sign(m/n)$, dove $m/n$ è una frazione ridotta ai minimi termini.
E' possibile disporre tutti i numeri della forma $ 2^m 3^n$ in ordine crescente, tenendo anche conto che $n>0$, quindi definire una funzione $g: Im(f) \to NN$ che associa ad ogni numero la sua posizione meno 1.
Per esempio:
$g(3) = 0$, $g(6) = 1$, $g(9) = 2$, $g(12) = 3$, $g(24) = 4$, $g(27) = 5$, ecc.
Analogamente per i numeri negativi definisco:
$g(-3) = -1$, $g(-6) = -2$, $g(-9) = -3$, $g(-12) = -4$, $g(-24) = -5$, $g(-27) = -6$, ecc.
E' piuttosto chiaro che la funzione $g \circ f$ è una funzione biiettiva tra $QQ$ e $ZZ$.
A questo punto resta da comporla con la famosa funzione suggerita da Pachisi per avere una funzione biiettiva tra $QQ$ e $NN$.

[j18eos]

@Pachisi Quasi: \(\displaystyle0\) e \(\displaystyle1\) vanno entrambi in \(\displaystyle0\)!

[dan952]

Basta cambiare

$f(x)={(x/2\ se\ pari.),(-(x+1)/2\ se\ dispari):}$

Penso...

[Pachisi]

@j18eos: Giusto, non me ne ero accorto!
Dovrebbe funzionare con la correzione di dan95

[dan952]

@Robbstark
Non capisco quella che hai definito è una funzione che va da $ZZ×ZZ \rightarrow ZZ$

[robbstark1]

Per quanto riguarda la funzione che ho chiamato $f$, va da $QQ$ in $ZZ$. Dato che gli elementi di $QQ$ sono frazioni di interi, è immediato quel che osservi, cioè che $QQ$ è equivalente ad un sottinsieme di $ZZ \times ZZ$.
La funzione $g$ va invece da $Im(f)$ in $ZZ$.
Questa è la parte chiave. A questo punto mi servo della funzione di Pachisi per portare da $ZZ$ in $NN$, avrei dovuto specificare la sua inversa, ma non ci ho fatto molta attenzione perché quella parte del problema mi era già nota.

[dan952]

Quello che intendevo riguardava solo un fatto di notazione, non si dovrebbe scrivere $f(m,n)=...$ invece che $f(m/n)$

[robbstark1]

Credo che la notazione $f(m/n)$ sia corretta. In fondo avrei potuto scrivere anche $f(x) = 2^{num(x)} 3^{den(x)}$, dove le funzioni $num$ e $den$ associano un numero razionale con il numeratore e il denominatore della frazione corrispondente, ridotta ai minimi termini, ma mi è sembrato più semplice scrivere in quel modo.

Scrivere $f(m,n)$ va bene pure, ma bisogna specificare che il dominio non è tutto $ZZ \times ZZ$, bensì quel sottinsieme che genera frazioni $m/n$ ridotte ai minimi termini. Comunque alla fine è più o meno equivalente.

[j18eos]

Indizio!

Dimostrare che \(\displaystyle\mathbb{Q}\) è in biezione con \(\displaystyle\mathbb{N}\times\mathbb{Z}\), per l'esercizio 1 quest'ultimo insieme è in biezione con \(\displaystyle\mathbb{N}\times\mathbb{N}\).

Per la prima parte dell'indizio, basta scrivere tutti i numeri razionali in una... tabella (infinita).

[robbstark1]

A j18eos:

La tabella può essere usata per costruire una funzione da $ZZ \times ZZ$ a $QQ$, ma non iniettiva. Questo però può essere usato per concludere che $QQ$ ha cardinalità non superiore a $ZZ$, ma la costruzione della biezione non è esplicita.

Piuttosto un'alternativa al mio metodo può essere quella di considerare solo un quadrante di questa tabella, fatto dalle frazioni positive, e mettere questo in corrispondenza biunivoca con $NN$ numerando lungo le diagonali, facendo attenzione a non contare più volte lo stesso numero razionale (generato da frazioni non ai minimi termini).
Si può poi ripetere la stessa cosa con un quadrante che genera frazioni negative e associare a $ZZ^-$.
Quindi nel complesso si trova una biezione direttamente tra $QQ$ e $ZZ$, quindi tra $QQ$ ed $NN$, grazie al punto 1.

[j18eos]

@robbstark

Perché non si avrebbe una funzione iniettiva?

Scrivo le prime due righe della tabella che ho in mente:
\[
\begin{bmatrix}
\dots & -2 & -1 & 0 & 1 & 2 & \dots\\
\dots & -\frac{3}{2} & -\frac{1}{2} & \frac{1}{2} & \frac{3}{2} & \frac{5}{2} & \dots\\
\ddots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots
\end{bmatrix}.
\]
Come vedi, i numeri razionali non si ripetono!

[robbstark1]

A j18eos:

Ok, con quella tabella si può mettere in corrispondenza biunivoca $QQ$ ed $NN \times ZZ$, non $ZZ \times ZZ$. In ogni caso il problema delle ripetizioni si può eliminare facendo attenzione quando si scrive la tabella, come hai mostrato (che non è il caso che solitamente ho incontrato sui libri). Da $NN \times ZZ$ si può facilmente passare ad $NN \times NN$, grazie al punto 1. Occorre ancora dimostrare che $NN \times NN$ ha la stessa cardinalità di $NN$, e mi viene in mente il famoso metodo di numerare per diagonali, anche se è possibile scegliere percorsi alternativi.

Il mio voleva essere un approccio alternativo, che fosse più facile da esprimere in termini di funzioni classiche, per cui mi sono buttato sull'algebra piuttosto che la geometria. Il risultato non è più semplice come speravo, ma mi sembra che comunque sia altrettanto valido.

[j18eos]

"robbstark":...Il mio voleva essere un approccio alternativo, che fosse più facile da esprimere in termini di funzioni classiche, per cui mi sono buttato sull'algebra piuttosto che la geometria. Il risultato non è più semplice come speravo, ma mi sembra che comunque sia altrettanto valido...

Se ci riuscirai, ti leggerò con curiosità!

[robbstark1]

Per quanto riguarda trovare una funzione biiettiva tra $NN$ e $QQ$ con un metodo alternativo a quello della tabella ci sono già riuscito nel mio primo post.
Quanto a trovare una funzione elementare che soddisfi questi requisiti, invece dubito sia fattibile, ma ovviamente se dovesse venirmi in mente qualcosa la scriverò.

[j18eos]

Forse dovresti aggiungere un valore assoluto...

[robbstark1]

Perchè dovrei mettere un valore assoluto?

[j18eos]

Se tu supponi (senza ledere la generalità) che per il generico numero razionale \(\displaystyle\frac{m}{n}\) sia \(\displaystyle n>0\) allora \(\displaystyle m\in\mathbb{Z}\) e quindi non è sempre \(\displaystyle 3^m\in\mathbb{Z}\) ma \(\displaystyle 3^{|m|}\in\mathbb{Z}\).

Suggerimento per una terza soluzione:

pensare alla spirale di Archimede!

[robbstark1]

Sí, è vero.
Bella anche l'ultima soluzione.

[Dezzo93_it]

Per trovare una biiezione tra $NN$ e $ZZ$ la più semplice che mi viene in mente è:

\[ \varphi(n)=(-1)^{n+1} \Bigg[\frac{n+1}{2}\Bigg] \]

dove al solito $[ # ]$ indica la parte intera di $#$.