Numerabilità

[Ramo82]

sia N l'insieme dei naturali. Dimostrare che N^2 è numerabile.
lo è anche N^3?

[Principe2]

scriviamo tutte le coppie ordiante di NxN così:

(0,0) (1,0) (2,0)....
(0,1) (1,1) (2,1)....
(0,2) (1,3) (2,2)....
....................
...................

sia d(0)={(0,0)}, d(1)={(0,1),(1,0)}...d(k)={(k,0),(k-1,1)..(1,k-1),(0,k)}

consideriamo la successione {d(k)}: è sicuramente numerabile, perchè è una successione; d'altra parte, comunque presa una coppia del prodotto cartesiano NxN, sta lì dentro; in concluzione NxN è numerabile.

in generale è numerabile N^k. infatti c'è un teorema che dice che se A è isomosrfo a B e C è isomorfo a D, allora AxC è isomorfo a BxD.
poniamo A,C,D=N e B=NxN otteniamo che N^3 è isomorfo a N^2 che a sua volta, abbiamo mostrato, è isomorfo a N, da cui, per transitività la tesi. ragionando analogamente si dimostra che, comunque preso k naturale, N^k è numerabile.

ciao, ubermensch

[Ramo82]

io conoscevo un altro criterio x ordinare N^2. Ordini prima le coppie a seconda della somma dei loro 2 elementi in ordine crescente e ordini le coppie caratterizzate dalla stessa somma mediante l'ordine lessicografico.
Anche per la numerabilità d R^3 ho un'altra dimostrazione: se t interessa te la dico... anche da questa x induzione si arriva a N^k numerabile per ogni k naturale..

[Principe2]

si dimmela! thanx..

[Ramo82]

eccola:

poichè NxN è numerabile significa che esiste una bigezione da NxN a N. Chiamiamola f. Ora si consideri f3 da N^3 a N così definita:
f3(n1,n2,n3)=f(n1,f(n2,n3))
poichè f3 è biunivoca (non lo dimostro ma vedrai da te che è molto facile concluderlo vista la bigettività d f) si ha la tesi.

Per N^k si opera per induzione:
* N^2 è numerabile per cui esiste f bigettiva da N^2 a N

* N^k numerabile -->N^(k+1)numerabile:
N^k numerabile implica che esiste una fk bigettiva da N^k a N. Allora si prende
f[k+1] definita come
f[k+1](n1,n2,...,n[k+1])=f(n1,fk(n2,n3,...,n[k+1])
che è bigettiva (la dimostrazione è simile a quella x f)

[Principe2]

ok grazie!