Pagina 1 di 2

Numerabilità

MessaggioInviato: 13/10/2014, 16:28
da Gizeta
Un classicone: dimostrare che [tex]\mathbb{N} \times \mathbb{N}[/tex] è numerabile! :D

Re: Numerabilità

MessaggioInviato: 13/10/2014, 17:03
da afullo
Non spaventi il fatto che sia nella sezione di matematica universitaria: anche se si tratta di programma del primo anno di aritmetica/algebra/matematica discreta, la sua dimostrazione è alla portata dell'olimpionico medio. :)

Re: Numerabilità

MessaggioInviato: 13/10/2014, 21:26
da Gizeta
Si, ha perfettamente ragione Afullo.
Mi sono dimenticato di inserire un lemmino che aiuta nella dimostrazione (lo metto come hint):

Testo nascosto:
Sia [tex]\mathscr{F}[/tex] una famiglia numerabile di insiemi finiti (non vuoti), allora [tex]\bigcup_{X \in \mathscr{F}}{X}[/tex] è numerabile.

Re: Numerabilità

MessaggioInviato: 13/10/2014, 21:33
da Drago
Non so dove porti la tua strada, ma uno può anche trovare una bella bigezione... (ok, farlo senza averlo mai visto forse è impossibile)

Re: Numerabilità

MessaggioInviato: 13/10/2014, 21:44
da xXStephXx
Potendo usare quel fatto la si può rigirare in molti modi. Tipo chessò $E_n = \{\ (a,b) \ | \ a+b=n\}$ ma non ricordo se la dimostrazione di quel fatto era davvero così diretta o bisognava ricorrere a qualche strano magheggio assiomatico. In ogni caso c'è sempre quella che si fa per i razionali xD

Re: Numerabilità

MessaggioInviato: 13/10/2014, 22:06
da Gizeta
Prodi sostiene che sia immediata e facile (e, supponendo che la mia dimostrazione sia corretta, lo è), infatti la pone insieme ad altri quattro fatti simili (magari chi vuole provare e non è molto esperto può aprire lo spoiler, dimostrare quel fatto e poi usare l'hint di Steph per concludere).

Un altro fatto dei suddetti quattro è che una partizione di un insieme numerabile è finita o numerabile (ma allora [tex]\mathbb{Q}[/tex]...): Prodi(gi) :lol:

Re: Numerabilità

MessaggioInviato: 13/10/2014, 22:25
da xXStephXx
Ah ok, allora sostanzialmente basterà numerare il primo insieme partendo da $1$, prendere l'insieme successivo, togliere eventuali ripetizioni e continuare numerando pure gli elementi del secondo.. e così via... ?

Comunque secondo me in tutto il discorso sulle cardinalità, l'idea davvero geniale è quella che serve per dimostrare che l'insieme delle parti di $A$ ha cardinalità strettamente maggiore di quella di $A$. Il nostro prof ci ha mostrato un modo bello :D

Re: Numerabilità

MessaggioInviato: 14/10/2014, 7:38
da Gizeta
xXStephXx ha scritto:Ah ok, allora sostanzialmente basterà numerare il primo insieme partendo da 1, prendere l'insieme successivo, togliere eventuali ripetizioni e continuare numerando pure gli elementi del secondo.. e così via... ?


Si, ho fatto qualcosa di molto simile (talmente tanto che è proprio quel che ho fatto :lol: ).

xXStephXx ha scritto:Comunque secondo me in tutto il discorso sulle cardinalità, l'idea davvero geniale è quella che serve per dimostrare che l'insieme delle parti di A ha cardinalità strettamente maggiore di quella di [tex]A[/tex].


Non l'ho ancora vista (o meglio, ho saltato le ultime due/tre pagine del capitolo 0 e sono proprio quelle in cui è presente la dimostrazione di questo fatto).

Mi pare carino anche il fatto che la cardinalità dell'insieme delle parti di [tex]\mathbb{N}[/tex] è la stessa di [tex]\mathbb{N}^{\mathbb{N}}[/tex] [l'insieme delle successioni a valori in [tex]\mathbb{N}[/tex]] (ma non è nemmeno così facile, credo, sul Prodi è contrassegnato con un asterisco: chi prova lo fa a suo rischio e pericolo :lol: ).

Un altro bel fatto è che ogni insieme infinito può essere posto in corrispondenza biunivoca con una sua parte propria (e, anzi, questa è una proprietà caratteristica degli insiemi infiniti), ma la dimostrazione è abbastanza cavillosa e fa un uso fondamentale dell'assioma della scelta.

Re: Numerabilità

MessaggioInviato: 14/10/2014, 19:34
da hyka
Drago ha scritto:Non so dove porti la tua strada, ma uno può anche trovare una bella bigezione... (ok, farlo senza averlo mai visto forse è impossibile)


Testo nascosto:
Intendi la funzione \(\mathbb{N} \to \mathbb{N}^\mathbb{N} \to \mathbb{N}^2\) che usa le valutazioni p-adiche?

Re: Numerabilità

MessaggioInviato: 14/10/2014, 19:59
da xXStephXx
Gizeta ha scritto:Mi pare carino anche il fatto che la cardinalità dell'insieme delle parti di [tex]\mathbb{N}[/tex] è la stessa di [tex]\mathbb{N}^{\mathbb{N}}[/tex] [l'insieme delle successioni a valori in [tex]\mathbb{N}[/tex]] (ma non è nemmeno così facile, credo, sul Prodi è contrassegnato con un asterisco: chi prova lo fa a suo rischio e pericolo :lol: ).


Forse dipende anche da cosa si può usare. Ad esempio usando il fatto che l'unione numerabile di insiemi numerabili è numerabile abbiamo che l'insieme delle parti di $\mathbb{N}$ è dato dall'insieme delle successioni a valori in $\mathbb{N}$ unito all'insieme dei polinomi a coefficienti in $\mathbb{N}$. Ora i secondi sono numerabili e quindi dovrebbe seguirne la tesi.


Oppure c'è la via magica :D Supponiamo per assurdo che possiamo numerare tutte le successioni a valori in $\mathbb{N}$. Allora le elenco tutte una sotto l'altra in una specie di griglia rettangolare infinita. Ma le posso davvero elencare tutte? Guardo la diagonale principale della griglia. E considero la successione che come $i-esimo$ elemento ha $1$ se l'$i-esimo$ elemento della $i-esima$ riga è maggiore di $10$. Altrimenti vale $11$. Quindi ho costruito una successione fatta da $1$ e $11$. Ora avendo elencato tutte le successioni, ho elencato anche questa. Supponiamo che nell'elenco occupa la posizione $k-esima$. Ma allora il suo $k-esimo$ elemento per costruzione vale $1$ se è maggiore di $10$ o $11$ se è minore o uguale di $10$, che è chiaramente assurdo.. Quindi non posso enumerare le successioni :mrgreen: (ovviamente idea riciclatissima eh)
Il fatto che la cardinalità è la stessa delle parti di $\mathbb{N}$ è ovvio perchè ha cardinalità maggiore di $\mathbb{N}$ ma non maggiore delle parti di $\mathbb{N}$ e quidni non essendoci cardinalità intermedie coincidono per forza.