Questioni di cardinalità

[angus89]

Dinostrare che $N$ e $N x N$ sono in bigezione e creare l'applicazione che li mette in bigezione.

(in realtà il problema era più complesso, ma con vari ragionamenti l'ho ricondotto a questo)

Propongo la mia soluzione e spero che qualcuno corregga enetuali (probabili) errori, e sono ben accette tutte la altre dimostrazioni della suddetta proposizione.

Dim:
$f:N->NxN$
Analizziamo $N$, un suo generico elemento è $n$.
E dunque fattoriaziamolo in fattori primi.
$n=p^alpha * q^beta*...$
Di tutti presti primi noi prendiamo il più piccolo, ovvero $p$.
E dunque la nostra applicazione manderà
$n->(p^alpha,n/(p^alpha))$

Si trova che ogni $n$ determina un'unica coppia appartenente a $N*N$.
Mentre ogni $n$ può esser generato da una coppia $NxN$
Ad ogni coppia di $NxN$ è associato un $n$...
Semprerebbe esserci la biunivocità...

Semprerebbe che fili tutto...ma come faccio ad esserne sicuro?

[Gatto89]

Sei sicuro sia suriettiva? I vari $(0, x)$ e $(1, x)$ non sembrano essere presi...

[angus89]

effettivamente quello manca...
Bè non è definita quella roba..

Non sò a questo punto e a quest'ora non ho altre idee...
Se ne hai qualcuna posta pure...

[Fioravante Patrone]

Non capisco. Cantor non ti basta?

[angus89]

Non capisco. Cantor non ti basta?

Bè effettivamente utilizzando Cantor non hai bisogno di dir nulla...
Basta dire che entrambi sono numerabili...
Ma alla domanda: qual'è l'applicazione bigettiva non saprei proprio rispondere adesso...
Sento la necessità di esplicitarla...

[angus89]

ripetendo certo la forma esplicita (e non grafica) di una applicazione bigettiva
$F:N->N x N$
Tutti sanno che esiste, ma io non riesco a trovarla

[Fioravante Patrone]

Allora. Cantor un giorno si è svegliato e ha detto: $NN \times NN$ è numerabile. E tutti gli hanno creduto.

Sorry, il medioevo e il principio di autorità sono finiti da un pezzo.
Io mi riferivo al cosiddetto "primo procedimento diagonale" (di Cantor).

[angus89]

Bè...
Per quanto riguarda Cantor da perfetto ignorante conosco solo la proposizione "ogni insieme numerabile e infinito ha la stessa cardinalità di N" e conosco la dimostrazione sulla non numerabilità di R.
In quel contesto ho visto per la prima volta la diagonale di Cantor.
Quindi non conosco il "primo procedimento diagonale"...

[Fioravante Patrone]

Bè...
Per quanto riguarda Cantor da perfetto ignorante conosco solo la proposizione "ogni insieme numerabile e infinito ha la stessa cardinalità di N" e conosco la dimostrazione sulla non numerabilità di R.
In quel contesto ho visto per la prima volta la diagonale di Cantor.
Quindi non conosco il "primo procedimento diagonale"...

Mi cadono le braccia. Come parlare al vento.
A me personalmente non interessa se sei ignorante o meno. Tutti sappiamo solo una misera porzione di mate. In compenso mi preoccupa e molto che tu ribadisca l'idea che a Cantor gli abbiano creduto sulla parola. Di solito in mate una "proposizione" è tale se corredata da dimostrazione. E la consapevolezza di questo dovrebbe essere il "riflesso condizionato".

[angus89]

ma certo...
la penso proprio come te...
Quello che Cantor ha dimostrato è che ci sono insiemi infiniti che son più piccoli di altri insiemi infiniti.
Inoltre se un insieme è numerabile di conseguenza è in bigezione con N, basta pensare che posso mettere un indice ad ogni elemento.
In questo caso se pensiamo $NxN$, possiamo pensare ad una matrice...
Oppure elencarli e di consequenza inventarci un qualsiasi modo per numerarli
$(0,0) - (0,1) - (0,2) - (0,3) - (0,4) - (0,5) ...$
$(1,0) - (1,1) - (1,2) - (1,3) - (1,4) - (1,5) ...$
$(2,0) - (2,1) - (2,2) - (2,3) - (2,4) - (2,5) ...$
$(3,0) - (3,1) - (3,2) - (3,3) - (3,4) - (3,5) ...$
$...$
Ad esempio andare avanti per diagonali...

Per quanto riguarda Fioravante sottolineo che la penso esattamente come te...
Non è che tutti hanno creduto a Cantor...
Io sto semplicente dicendo che se un insieme è numerabile, banalmente è in bigezione con N e dal punto di vista grafico si trova facilmente un modo per numerare $NxN$...
Io cerco solo un modo analitico...
Tutto qui...