Numerabilità

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.
Avatar utente
Drago
Messaggi: 1059
Iscritto il: 14/03/2013, 15:51

Re: Numerabilità

Messaggio da Drago »

W Cantor! xD
@hyka: non ho ben capito cosa intendi... la mia è l'idea classica che si usa anche su R, ovvero creare un nuovo numero alternando le cifre prendendole dai due (o anche n) numeri :)
mr96
Messaggi: 1489
Iscritto il: 11/02/2014, 20:37

Re: Numerabilità

Messaggio da mr96 »

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)
Avendo già visto come si dimostra che l'insieme dei razionali è numerabile non dovrebbe essere complicato (più o meno è lo stesso), ma forse sbaglio, non sono per nulla afferrato in ste cose...
hyka
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Numerabilità

Messaggio da hyka »

Ok, quella a cui mi riferivo io è diversa ma essenzialmente simile.

I naturali sono un UFD, in particolare ogni naturale può essere fattorizzato come \(n = 2^{\alpha_0} 3^{\alpha_1} 5^{\alpha_2} \ldots\).
Ora da questa fattorizzazione puoi passare alla tupla infinita \(\overline{n} = (\alpha_0, \alpha_1, \alpha_2, \ldots) = (v_{p_0}(n), v_{p_1}(n), \ldots)\) tramite una funzione \(f : \mathbb{N} \to \mathbb{N}^\mathbb{N}\) che possiamo "definire per componenti" come \(f(n)(m) = v_{p_m}(n)\).
Si tratta banalmente di una funzione iniettiva(ce lo dice UFD) non suriettiva, infatti dato \(\overline{n} = (1, 2, 3, \ldots)\) il numero \(n\) che dovrebbe essere mappato in \(\overline{n}\) dovrebbe essere infinito, ma questo elemento non appartiene a \(\mathbb{N}\).
Continuando, data una tupla infinita \(\mathbb{N}^\mathbb{N}\), che corrisponde ad una funzione \(\alpha : \mathbb{N} \to \mathbb{N}\), puoi passare ad una coppia \((n, m)\) tramite la funzione parziale \(g : \mathbb{N}^\mathbb{N} \to \mathbb{N}^2\) definita come \(\displaystyle g(h) = \left(2^{\alpha(0)} 3^{\alpha(2)} 5^{\alpha(4)} \ldots, 2^{(\alpha(1)} 3^{\alpha(3)} 5^{\alpha(5)} \ldots \right) = \left(\prod_{i \in \mathbb{N}} p_i^{\alpha(2i)}, \prod_{i \in \mathbb{N}} p_i^{\alpha(2i + 1)}\right)\).
Questa seconda relazione è funzionale ma non totale, suriettiva ma non iniettiva. Ad ogni modo puoi costruire una funzione iniettiva da \(\mathbb{N}^2 \to \mathbb{N}^\mathbb{N}\) e una funzione parziale suriettiva da \(\mathbb{N}^\mathbb{N} \to \mathbb{N}\) in modo abbastanza intuitivo(non mi va di scriverle esplicitamente) la cui composizione (che è una funzione) sarà inversa della composizione delle prime due funzioni (che anch'essa è una funzione), perciò abbiamo costruito un isomorfismo tra \(\mathbb{N}^2\) e \(\mathbb{N}\).

Da qui è facile dimostrare che \(\mathbb{N}\) è isomorfo a \(\mathbb{Q}\), semplicemente aggiungendo in coda alla sequenza \(\mathbb{N} \to \mathbb{N}^\mathbb{N} \to \mathbb{N}^2\) la funzione parziale (suriettiva ma non iniettiva) \(h: \mathbb{N}^2 \to \mathbb{Q}\) definita come \((x, y) \mapsto \dfrac{x}{y}\). Per tornare indietro basta considerare l'ovvia funzione iniettiva non suriettiva \(\mathbb{Q} \to \mathbb{N}^2\) definita come (ovvio) e si ha lo stesso argomento di prima.
Avatar utente
enigma
Messaggi: 124
Iscritto il: 19/03/2013, 20:11

Re: Numerabilità

Messaggio da enigma »

hyka ha scritto:abbiamo costruito un isomorfismo tra \(\mathbb{N}^2\) e \(\mathbb{N}\).
Lo scrivo per precisarlo nel caso a qualcun altro, come a me, non fosse subito chiaro: quello che ha costruito non è un isomorfismo, ma una biiezione-ovvero $\mathbb N^2$ e $\mathbb N$ sono equipotenti, ma non isomorfi come (ad esempio) monoidi commutativi. L'unico senso che si può dare a tale terminologia è nella categoria $\mathbf{Set}$, ma è un po' una forzatura lessicale.
hyka
Messaggi: 43
Iscritto il: 11/08/2014, 19:03

Re: Numerabilità

Messaggio da hyka »

@enigma: immagino si possa interpretare anche come isomorfismo tra due strutture algebriche senza operazioni, ma concordo sul fatto che potrebbe far (ingiustamente) pensare che le usuali operazioni sui numeri naturali siano in qualche modo preservate.

Volendo essere un pizzico più pignoli, si può osservare che c'è un bel problema con la valutazione p-adica dello \(0\), due possibili soluzioni sono sostituire \(\mathbb{N}^\mathbb{N}\) con \((\mathbb{N} \cup \{\infty\})^\mathbb{N}\) usando questa definizione (e bisognerebbe modificare un po' le funzioni) oppure aggiungere altre due funzioni:
\(\mathbb{N} \to \mathbb{N} \setminus \{0\} \to \mathbb{N}^\mathbb{N} \to (\mathbb{N} \setminus \{0\})^2 \to \mathbb{N}^2\)
dove la prima è \(n \mapsto n + 1\) e l'ultima \((n, m) \mapsto (n-1, m-1)\)
aggiungendo un po' di lavoro da fare per dimostrare che si tratta di una biiezione (sempre se è vero).
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio da Gizeta »

Grazie mille Steph per le dimostrazioni, ma non le leggo ( :mrgreen: ), almeno fin quando non avrò provato a dimostrarlo.

Hyka, prometto che uno di questi giorni leggerò la tua (e proverò anche i problemini che hai proposto nell'altro topic), "purtroppo" il Prodi mi risucchia (è veramente bello bello: un libro scritto da chi sapeva la matematica e, soprattutto, sapeva insegnarla; tremo ogni volta al solo pensiero di cosa sarebbe potuta essere un'intera opera matematica scritta da Prodi :cry: ) e ogni volta mi rimane pochissimo tempo.

Vi lascio la dimostrazione del libro della numerabilità di [tex]\mathbb{N} \times \mathbb{N}[/tex]: come scritto da Steph, per ogni coppia [tex](m,n)[/tex] introduciamo un "peso" [tex]m+n=r[/tex]; evidentemente esisterà un numero limitato di coppie ordinate il cui peso è [tex]r[/tex] (in particolare, tali coppie sono [tex]r+1[/tex]).
Consideriamo insiemi del tipo [tex]P_r=\{(m,n):(m,n) \in (\mathbb{N} \times \mathbb{N}[/tex] e [tex]m+n=r\}[/tex], ma ora evidentemente [tex]\bigcup_{r=0}^{\infty}P_r[/tex] ricopre [tex]\mathbb{N} \times \mathbb{N}[/tex] ed è numerabile, inoltre gli insiemi [tex]P_r[/tex] sono finiti; per il lemma tale unione è numerabile.

Lascio anche la dimostrazione del fatto che ogni insieme infinito può essere posto in corrispondenza biunivoca con un suo sottoinsieme proprio.
La tesi è evidente per un insieme numerabile (basti pensare che è possibile per [tex]\mathbb{N}[/tex]).
Per dimostrarlo per un insieme infinito generico mostriamo dapprima che ogni insieme infinito contiene un sottoinsieme numerabile.

Lemma: Ogni insieme infinito contiene un sottoinsieme proprio numerabile.

Dimostrazione: Sia [tex]X[/tex] un insieme infinito e sia [tex]\phi: \tau(X) \rightarrow X[/tex] una funzione di scelta (quella generalizzata, tanto per mostrare che non è solo un esercizio di stile).
Definiamo ora una successione a valori in [tex]X[/tex] nel seguente modo:

[tex]a_0=\phi(X)[/tex]

[tex]a_n=\phi(X-\{a_0,a_1,...,a_{n-1}\})[/tex]

Il sottoinsieme [tex]A=\{a_i:a_i \in X[/tex] e [tex]i \in \mathbb N\}[/tex] è quello che cerchiamo [tex]\blacksquare[/tex]

Bene, consideriamo ora l'insieme [tex]X[/tex] come unione del sottoinsieme numerabile e del suo complementare: [tex]X=A \cup A'[/tex]; non ci resta che considerare una funzione definita a tratti che sia la funzione identica sul complementare e che associ all'insieme numerabile un suo sottoinsieme proprio numerabile (cosa che sappiamo essere possibile), questa funzione è evidentemente biiettiva e stabilisce, dunque, una corrispondenza biunivoca tra [tex]X[/tex] e una sua parte propria [tex]\blacksquare[/tex]
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio da Gizeta »

Teorema: Un sottoinsieme di un insieme numerabile è finito o numerabile.

Dimostrazione: Sia l'insieme numerabile [tex]A[/tex], allora possiamo dire [tex]A=\{a_i:i \in \mathbb{N}\}[/tex] dal momento che è numerabile.
Preso [tex]A' \subset A[/tex] lo individuo con il numero reale ottenuto giustapponendo gli elementi ordinati per indice crescente; chiaramente ho finito, infatti posso esprimere il numero in notazione decimale e associare ad ogni cifra l'esponente della potenza di [tex]10[/tex] che gli spetta dalla notazione posizionale.

Esempio:

[tex]A'=\{a_7,a_3,a_5,a_{25},a_{12},...\}[/tex]

[tex]a_3a_5a_7a_{12}a_{25}...=10^0a_3+10^1a_5+10^2a_7+10^3a_{12}+10^4a_{25}+...[/tex]

[tex]a_3 \mapsto 0[/tex]
[tex]a_5 \mapsto 1[/tex]
[tex]a_7 \mapsto 2[/tex]
[tex]a_{12} \mapsto 3[/tex]
[tex]a_{25} \mapsto 4[/tex]
...

Chiaramente se il sottoinsieme è finito non è numerabile e viceversa.
Il fatto che siano numerati è stato sfruttato per costruire il numero in maniera univoca.
Gizeta
Messaggi: 826
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggio da Gizeta »

Propongo le dimostrazioni delle altre tre proposizioni connesse a quella presentata nel post precedente.

1) L'unione di una famiglia finita non vuota di insiemi numerabili è un insieme numerabile.

Dim. Sia [tex]\textit{F}[/tex] una famiglia finita non vuota di insiemi numerabili; dato che è finita si ha [tex]card(\textit{F})=n[/tex] per qualche [tex]n \in (\mathbb{N}\setminus\{0\})[/tex].
Procediamo per induzione sul numero cardinale: per n=1 la proposizione è vera in quanto l'unione della famiglia [tex]\textit{F}[/tex] coincide con l'insieme numerabile elemento di [tex]\textit{F}[/tex], quindi è numerabile per ipotesi; supponiamo la proposizione sia vera per [tex]n[/tex], allora abbiamo

[tex]\displaystyle \bigcup_{i=1}^{n+1}{A_i}=\bigcup_{i=1}^n{A_1} \cup A_{n+1}[/tex]

Consideriamo ora i due insiemi [tex]\displaystyle B_1= \left (\bigcup_{i=1}^n{A_i} \right ) \times \{0\}[/tex] e [tex]B_2= A_{n+1} \times \{1\}[/tex], che sono disgiunti, e le ovvie bigezioni verso gli insiemi [tex]\displaystyle \bigcup_{i=1}^n{A_i}[/tex] e [tex]\displaystyle A_{n+1}[/tex]; segue che per ipotesi induttiva [tex]B_1[/tex] è in corrispondenza biunivoca con [tex]\mathbb{N}[/tex] e per ipotesi [tex]B_2[/tex] è in corrispondenza biunivoca con [tex]\mathbb{N}[/tex], ma del resto [tex]\mathbb{N} \cong P[/tex] e [tex]\mathbb{N} \cong D[/tex] (dove indichiamo, rispettivamente, l'insieme dei pari e dei dispari con [tex]P[/tex] e [tex]D[/tex]) e [tex]P \cup D = \mathbb{N}[/tex] e [tex]P \cap D = \emptyset[/tex], quindi è così definita una corrispondenza biunivoca [tex]\displaystyle \bigcup_{i=1}^{n+1}{A_i} \cong \mathbb{N}[/tex].

___________________________________________


Attenzione: la dimostrazione presentata contiene un errore , infatti proprio perché [tex]\displaystyle \bigcup_{i=1}^n{A_i}[/tex] e [tex]A_{n+1}[/tex] non sono disgiunti, non possiamo in generale essere sicuri che esista una bigezione dalla loro unione verso la loro "unione disgiunta".
Apportiamo la seguente correzione: [tex]\displaystyle \left ( A_{n+1} \setminus (\bigcup_{i=1}^n{A_i} \cap A_{n+1}) \right ) \subset A_{n+1}[/tex], quindi per il teorema 2) dimostrato sotto è finito o numerabile per ipotesi induttiva, e [tex]\displaystyle \bigcup_{i=1}^n{A_i} \cup \left (A_{n+1} \setminus \left( \bigcup_{i=1}^n{A_i} \cap A_{n+1} \right ) \right) = \bigcup_{i=1}^n{A_i} \cup A_{n+1}[/tex].

Nel caso in cui quella differenza sia numerabile costruiamo una bigezione come sopra (dal momento che ora disponiamo effettivamente di due insieme disgiunti), invece se dovesse essere finita è un attimo dimostrare che l'unione di un numerabile e un insieme finito è numerabile.

___________________________________________


2) Un sottoinsieme di un insieme numerabile è finito o numerabile.

Dim. Sia senza perdita di generalità [tex]X \subset \mathbb{N}[/tex] (infatti se [tex]X[/tex] non fosse sottoinsieme dei naturali si potrebbe operare sulla sua immagine tramite la corrispondenza biunivoca con i naturali e poi comporre l'applicazione individuata con l'inversa della corrispondenza biunivoca) tale sottoinsieme e supponiamo non sia finito, allora possiamo definire un'applicazione [tex]f: \mathbb{N} \rightarrow X[/tex] ricorsivamente come :

[tex]f(0)=min(X)[/tex]
[tex]f(n+1)=min(X \setminus\{f(0), f(1), f(2),..., f(n)\})[/tex]

Cominciamo col notare che l'applicazione è ben definita in quanto [tex]X[/tex] non è finito quindi togliendo da esso insiemi di cardinalità finita otteniamo insiemi non vuoti, dunque per il principio del minimo intero essi ammettono minimo.

[tex]f[/tex] è iniettiva dato che [tex]X[/tex] è una catena (cioè un sottoinsieme totalmente ordinato) di [tex]\mathbb{N}[/tex];
[tex]f[/tex] è suriettiva dato che scelto ad arbitrio [tex]x \in X[/tex] esiste in [tex]X[/tex] solo un numero finito [tex]m[/tex] di elementi più piccoli di [tex]x[/tex], quindi [tex]f(m+1)=x[/tex] per definizione dell'applicazione [tex]f[/tex].

Per definizione, dunque, si ha [tex]f:\mathbb{N} \cong X[/tex]

3) Una partizione di un insieme numerabile è finita o numerabile.

Con il termine partizione indichiamo una famiglia di sottoinsiemi di un determinato insieme non vuoti, a due a due disgiunti e la cui unione ricopre l'insieme.

Come sopra possiamo considerare senza perdita di generalità una partizione [tex]\textit{F}[/tex] di [tex]\mathbb{N}[/tex] e supporre che essa non sia finita.
Ad ogni insieme di [tex]\textit{F}[/tex] associamo l'elemento minimo dell'insieme (che esiste per il principio del minimo intero), poi costruiamo una bigezione [tex]\textit{F} \cong \mathbb{N}[/tex] associando ad ogni [tex]n \in \mathbb{N}[/tex] i minimi nell'ovvio ordine indotto dall'ordinamento totale dei numeri naturali.
Tale applicazione è iniettiva perché gli elementi della famiglia sono a due a due disgiunti e suriettiva perché, similmente alla dimostrazione precedente, per ogni minimo esiste solo un numero finito di minimi che lo precede.
Rispondi