Numerabilità
Numerabilità
Un classicone: dimostrare che [tex]\mathbb{N} \times \mathbb{N}[/tex] è numerabile!
Re: Numerabilità
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à
Si, ha perfettamente ragione Afullo.
Mi sono dimenticato di inserire un lemmino che aiuta nella dimostrazione (lo metto come hint):
Mi sono dimenticato di inserire un lemmino che aiuta nella dimostrazione (lo metto come hint):
Testo nascosto:
Re: Numerabilità
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à
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à
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)
Un altro fatto dei suddetti quattro è che una partizione di un insieme numerabile è finita o numerabile (ma allora [tex]\mathbb{Q}[/tex]...): Prodi(gi)
Ultima modifica di Gizeta il 14/10/2014, 6:41, modificato 1 volta in totale.
Re: Numerabilità
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
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
Re: Numerabilità
Si, ho fatto qualcosa di molto simile (talmente tanto che è proprio quel che ho fatto ).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... ?
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).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].
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 ).
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à
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:
Re: Numerabilità
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.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 ).
Oppure c'è la via magica 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 (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.