Numerabilità

Oltre la matematica elementare: teoria, esercizi, e riflessioni sulle varie branche della matematica che si fanno all'università.

Re: Numerabilità

Messaggioda Drago » 14/10/2014, 20:12

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

Re: Numerabilità

Messaggioda mr96 » 14/10/2014, 20:34

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...
mr96
 
Messaggi: 1455
Iscritto il: 11/02/2014, 20:37

Re: Numerabilità

Messaggioda hyka » 14/10/2014, 20:50

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

Re: Numerabilità

Messaggioda enigma » 17/10/2014, 9:47

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.
Avatar utente
enigma
 
Messaggi: 124
Iscritto il: 19/03/2013, 20:11

Re: Numerabilità

Messaggioda hyka » 17/10/2014, 11:22

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

Re: Numerabilità

Messaggioda Gizeta » 18/10/2014, 7:46

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: 814
Iscritto il: 27/11/2013, 17:16

Re: Numerabilità

Messaggioda Gizeta » 14/11/2014, 18:35

Scusate il doppio post, ma ho un dubbio amletico su una (mia) dimostrazione.

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.

A me pare funzionare, anche perché l'idea è abbastanza banalotta e semplice.
Posso mettere il fatidico quadratino nero, secondo voi? :roll:
Gizeta
 
Messaggi: 814
Iscritto il: 27/11/2013, 17:16

Precedente

Torna a Matematica Universitaria

Chi c’è in linea

Visitano il forum: Nessuno e 0 ospiti