Numerabilità

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Numerabilità

Messaggio da Gizeta »

Un classicone: dimostrare che [tex]\mathbb{N} \times \mathbb{N}[/tex] è numerabile! :D
afullo
Messaggi: 2033
Iscritto il: 13/03/2013, 22:06
Contatta:

Re: Numerabilità

Messaggio 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. :)
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio 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.
Avatar utente
Drago
Messaggi: 1059
Iscritto il: 14/03/2013, 15:51

Re: Numerabilità

Messaggio 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)
xXStephXx
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Numerabilità

Messaggio 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
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio 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:
Ultima modifica di Gizeta il 14/10/2014, 6:41, modificato 1 volta in totale.
xXStephXx
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Numerabilità

Messaggio 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
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio 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.
hyka
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Numerabilità

Messaggio 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?
xXStephXx
Messaggi: 628
Iscritto il: 23/03/2013, 18:12

Re: Numerabilità

Messaggio 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.
Rispondi