Grazie mille Steph per le dimostrazioni, ma non le leggo (
), almeno fin quando non avrò provato a dimostrarlo.
Hyka, prometto che uno di questi giorni leggerò la tua (e proverò anche i problemini che hai proposto nell'altro topic), "purtroppo" il Prodi mi risucchia (è veramente bello bello: un libro scritto da chi sapeva la matematica e, soprattutto, sapeva insegnarla; tremo ogni volta al solo pensiero di cosa sarebbe potuta essere un'intera opera matematica scritta da Prodi
) e ogni volta mi rimane pochissimo tempo.
Vi lascio la dimostrazione del libro della numerabilità di
[tex]\mathbb{N} \times \mathbb{N}[/tex]: come scritto da Steph, per ogni coppia
[tex](m,n)[/tex] introduciamo un "peso"
[tex]m+n=r[/tex]; evidentemente esisterà un numero limitato di coppie ordinate il cui peso è
[tex]r[/tex] (in particolare, tali coppie sono
[tex]r+1[/tex]).
Consideriamo insiemi del tipo
[tex]P_r=\{(m,n):(m,n) \in (\mathbb{N} \times \mathbb{N}[/tex] e
[tex]m+n=r\}[/tex], ma ora evidentemente
[tex]\bigcup_{r=0}^{\infty}P_r[/tex] ricopre
[tex]\mathbb{N} \times \mathbb{N}[/tex] ed è numerabile, inoltre gli insiemi
[tex]P_r[/tex] sono finiti; per il lemma tale unione è numerabile.
Lascio anche la dimostrazione del fatto che ogni insieme infinito può essere posto in corrispondenza biunivoca con un suo sottoinsieme proprio.
La tesi è evidente per un insieme numerabile (basti pensare che è possibile per
[tex]\mathbb{N}[/tex]).
Per dimostrarlo per un insieme infinito generico mostriamo dapprima che ogni insieme infinito contiene un sottoinsieme numerabile.
Lemma: Ogni insieme infinito contiene un sottoinsieme proprio numerabile.
Dimostrazione: Sia
[tex]X[/tex] un insieme infinito e sia
[tex]\phi: \tau(X) \rightarrow X[/tex] una funzione di scelta (quella
generalizzata, tanto per mostrare che non è solo un esercizio di stile).
Definiamo ora una successione a valori in
[tex]X[/tex] nel seguente modo:
[tex]a_0=\phi(X)[/tex]
[tex]a_n=\phi(X-\{a_0,a_1,...,a_{n-1}\})[/tex]
Il sottoinsieme
[tex]A=\{a_i:a_i \in X[/tex] e
[tex]i \in \mathbb N\}[/tex] è quello che cerchiamo
[tex]\blacksquare[/tex]
Bene, consideriamo ora l'insieme
[tex]X[/tex] come unione del sottoinsieme numerabile e del suo complementare:
[tex]X=A \cup A'[/tex]; non ci resta che considerare una funzione definita a tratti che sia la funzione identica sul complementare e che associ all'insieme numerabile un suo sottoinsieme proprio numerabile (cosa che sappiamo essere possibile), questa funzione è evidentemente biiettiva e stabilisce, dunque, una corrispondenza biunivoca tra
[tex]X[/tex] e una sua parte propria
[tex]\blacksquare[/tex]