Biiezione da $NN$ a $NN\times\NN$

[Giso1]

Salve a tutti, questo esercizio ci è stato dato dal prof. conseguentemente alla spiegazione del teorema di Schoeder-Cantor-Bernstein sulle funzioni iniettive.
Date le due funzioni iniettive: $f(x)\ NN\to\NN\times\NN$ definita come $f(a)\=\(a;0)$, e $g(x)\ NN\times\NN\to\NN$ definita come $g(a;b)\=\2^a\*\3^b$ trovare la funzione biettiva $h(x)$.
Sinceramente non so dove sbatter la testa, immagino che tale funzione dovrebbe avere una sorta di nesso con le due di partenze ma non so come procedere.
Ciao e grazie!

[perplesso1]

Scusa ma il teorema come l'avete dinostrato? perchè la dimostrazione che conosco io "costruisce" la biezione a partire dalle due funzioni iniettive, quindi secondo me dovresti solo applicare al caso particolare la costruzione generale, no?

[gundamrx91-votailprof]

Scusate, ma al di là del teorema, non è sufficiente comporre le due funzioni?

[Gi81]

@Gundam: occhio, se componi le due funzioni l'insieme di partenza e quello di arrivo coincidono

[perplesso1]

Ecco qua la costruzione che dicevo io, presa da "Set theory" di Jech ed opportunamente adattata, spero di non aver incasinato qualcosa, nel caso fatemelo notare.

Tu hai due funzioni iniettive

$f:NN -> NN^2$
$g: NN^2 -> NN$

quindi componedo ottieni una funzione iniettiva $(g \circ f): NN -> NN$. Ora definisci $A_0 = NN$ e $B_0 = g(NN^2)$ e poi per induzione

$A_{n+1} = g(f(A_n))$

$B_{n+1} = g(f(B_n))$

Nota che $A_{n+1} \subset B_n \subset A_n$ e quindi definisci $C_n = A_n-B_n$ e ancora poni $C= \bigcup_{n=0}^{\infty} C_n$. Siccome $g(f(C_n))= C_{n+1}$ hai che $g(f(C)) = \bigcup_{n=1}^{\infty} C_n \subset C$. Perciò possiamo definire una funzione $k: NN -> g(NN^2)$ tale che

$k(x) = g(f(x))$ se $x \in C$
$k(x) = x$ se $x \notin C$

che è iniettiva e surriettiva, cioè una biezione. A questo punto basta comporre $(k^{-1} \circ g) : NN^2 -> g(NN^2) -> NN$ per ottenere una biezione fra i due insiemi desiderati.

[gundamrx91-votailprof]

"Gi8":@Gundam: occhio, se componi le due funzioni l'insieme di partenza e quello di arrivo coincidono

Si, in effetti avrei dovuto connettere il cervello (ovvero vedere il teorema in questione) prima di rispondere.

[gugo82]

Tanto per dirne un'altra, per costruire una biiezione di \(\mathbb{N}^2\) in \(\mathbb{N}\) basta tener presente che ogni numero naturale \(n\) si scrive in unico modo come prodotto di una potenza di due ed un numero dispari (ciò si prova facilmente): pertanto la funzione \(\mathbb{N}^2\ni (h,k)\mapsto 2^{h-1} (2k-1)\in \mathbb{N}\) è una biiezione... Insomma, non è che serva fare necessariamente tutto quel casino.

[perplesso1]

"gugo82":Insomma, non è che serva fare necessariamente tutto quel casino.

Si, ma il fatto è che gli hanno dato esplicitamente due funzioni che in qualche modo dovrà usare, no? Altrimenti la traccia poteva anche dire "Sapendo che esistono due funzioni iniettive f e g trovare una biezione ....". Almeno io ho capito così, perchè se si trattava di trovare una biezione a caso gli avrei detto: parti da $(0,0)$ e segui le freccette... xD



Saluti.

[gugo82]

@ perplesso: Eh, ma seguendo le frecce si arriva solo a \((0,5)\)... Dunque? Quella con le freccette non mi pare affatto una biiezione di \(\mathbb{N}\) in \(\mathbb{N}^2\).
(E questa, seppur scherzosa, non è un'obiezione da poco... Quindi prendila a ridere. E poi leggiti Wittgenstein, Lezioni sui Fondamenti della Matematica, se non l'hai già fatto. )

Inoltre, lo so anch'io che il tuo ragionamento è corretto.
Quello che volevo far intendere è che una costruzione "pesante" come quella proposta è del tutto sprecata in questo ambito, poiché non se ne apprezza l'utilità.