numerabilità

Messaggioda Ramo82 » 29/03/2004, 14:27

sia N l'insieme dei naturali. Dimostrare che N^2 è numerabile.
lo è anche N^3?
Ramo82
New Member
New Member
 
Messaggio: 7 di 64
Iscritto il: 27/03/2004, 13:22

Messaggioda Valerio Capraro » 29/03/2004, 17:00

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
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 523 di 2911
Iscritto il: 03/02/2004, 23:58
Località: Southampton (UK)

Messaggioda Ramo82 » 29/03/2004, 19:37

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..
Ramo82
New Member
New Member
 
Messaggio: 11 di 64
Iscritto il: 27/03/2004, 13:22

Messaggioda Valerio Capraro » 29/03/2004, 21:20

si dimmela! thanx..
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 530 di 2911
Iscritto il: 03/02/2004, 23:58
Località: Southampton (UK)

Messaggioda Ramo82 » 30/03/2004, 14:33

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)
Ramo82
New Member
New Member
 
Messaggio: 17 di 64
Iscritto il: 27/03/2004, 13:22

Messaggioda Valerio Capraro » 30/03/2004, 16:36

ok grazie!
Valerio Capraro
Advanced Member
Advanced Member
 
Messaggio: 535 di 2911
Iscritto il: 03/02/2004, 23:58
Località: Southampton (UK)


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite