L'insieme delle parti di [tex]\mathbb{N}[/tex] è equipotente all'intervallo [0,1]

Domande di teoria, mini-dispense degli utenti, richieste di riferimenti ad articoli, ...

Moderatore: Moderatori

L'insieme delle parti di [tex]\mathbb{N}[/tex] è equipotente all'intervallo [0,1]

Messaggioda Gradevole il ven 29 ago 2008, 12:25

Se \mathbb{N} è l' insieme di tutti i numeri interi positivi, dimostrare che B è equivalente al continuo reale [0, 1], dove B è definito come l'insieme i cui elementi sono tutti i possibili sottoinsiemi di \mathbb{N}.

(L' esercizio lascia anche un suggerimento (che è meglio ignorare, perché incomprensibile. --- S): rappresentare un sottoinsieme A di \mathbb{N} con una successione a_1, a_2, \ldots, nel primo caso finita e nel secondo infinita, dei simboli 0 e 1, dove a_n= 1 oppure 0, secondo che l'n-esimo elemento di A appartenga o non appartenga al sottoinsieme dato.)

Come si può fare ? :D
Gradevole
 
Messaggi: 4
Iscritto il: gio 28 ago 2008, 17:51

Messaggioda Albe il ven 29 ago 2008, 16:16

Si consideri la funzione di \mathcal{P}(\mathbb{N}) (l'insieme delle parti di \mathbb{N}) in [0,1] che ad ogni sottoinsieme A di \mathbb{N} associa il numero x_A \in [0,1] il cui sviluppo decimale sia 0,c_1c_2\dots c_n\dots, dove l' n-esima cifra è 1, se n\in A, e 0 altrimenti. Si può facilmente dimostrare che la mappa è iniettiva; segue quindi che |\mathcal{P}(\mathbb{N})| \leq \big|[0,1]\big|. La stessa funzione di prima, ma con sviluppo in base 2, è suriettiva; ne segue che \big|[0,1]\big|\leq |\mathcal{P}(\mathbb{N})|. Quindi si desume che \big|[0,1]\big|= |\mathcal{P}(\mathbb{N})| (editato un typo).

Spero di essere stato chiaro, cosa che non mi riesce troppo bene... :)
Avatar utente
Albe
 
Messaggi: 24
Iscritto il: lun 16 giu 2008, 18:46
Località: Verona-Padova

Messaggioda Gradevole il sab 30 ago 2008, 13:09

Con "sviluppo in base 2 " cosa intendi esattamente?

Riflettendo sul senso del problema.. significa che quindi anche l'insieme delle parti di \mathbb{N} non è numerabile ?

Ti ringrazio !
Gradevole
 
Messaggi: 4
Iscritto il: gio 28 ago 2008, 17:51

Messaggioda pic il sab 30 ago 2008, 13:18

Le parti \mathcal{P}(A) di un insieme A non sono mai equipotenti ad A: presa una funzione f: A \to \mathcal{P}(A), esiste sempre x \in \mathcal{P}(A), fatto da tutti e soli gli elementi che non appartengono alla propria immagine, e questo insieme non è antimmagine immagine di nulla.
Avatar utente
pic
 
Messaggi: 693
Iscritto il: gio 12 giu 2008, 14:32
Località: London, UK

Messaggioda Albe il sab 30 ago 2008, 15:37

Semplicemente ho adottato come base di numerazione in [0,1] quella binaria, invece dell'usuale base decimale, in modo che ogni numero in [0,1] abbia un antimmagine rispetto la funzione da me considerata.
Avatar utente
Albe
 
Messaggi: 24
Iscritto il: lun 16 giu 2008, 18:46
Località: Verona-Padova

Revisionismo storico

Messaggioda salvo.tringali il mar 20 ott 2009, 15:33

Gradevole ha scritto:[...] L' esercizio lascia anche un suggerimento : rappresentare un sottoinsieme A di \mathbb{N} con una successione a_1, a_2, \ldots, nel primo caso finita e nel secondo infinita, dei simboli 0 e 1, dove a_n= 1 oppure 0, secondo che l'n-esimo elemento di A appartenga o non appartenga al sottoinsieme dato. [...]

...a distanza di tempo, trovo l'occasione per leggere anche questo thread. Sbaglio, o il suggerimento non è molto sensato?! :unsure: Se |A| = \infty, non vedo come la costruzione indicata possa fornire una sequenza finita di simboli 0 e 1. E poi quali sarebbero il primo e il secondo caso cui si fa riferimento nel testo? ...

Albe ha scritto:Si consideri la funzione di \mathcal{P}(\mathbb{N}) (l'insieme delle parti di \mathbb{N}) in [0,1] che ad ogni sottoinsieme A di \mathbb{N} associa il numero x_A \in [0,1] il cui sviluppo decimale sia 0,c_1c_2\dots c_n\dots, dove l' n-esima cifra è 1, se n\in A, e 0 altrimenti. Si può facilmente dimostrare che la mappa è iniettiva; segue quindi che |\mathcal{P}(\mathbb{N})| \leq \big|[0,1]\big|. La stessa funzione di prima, ma con sviluppo in base 2, è suriettiva; ne segue che \big|[0,1]\big|\leq |\mathcal{P}(\mathbb{N})|. Quindi si desume che \big|[0,1]\big|\leq |\mathcal{P}(\mathbb{N})|.

Visto la soluzione di Albe (dopo averla texata a puntino). Anche se non mi spiego la ragione, per cui abbia scelto di lavorare in un verso con le rappresentazioni decimali e nell'altro con le rappresentazioni binarie, quando avrebbe potuto utilizzare unicamente queste ultime, e risparmiarsi così uno sforzo definitivamente inutile. ;)

pic ha scritto:Le parti \mathcal{P}(A) di un insieme A non sono mai equipotenti ad A: presa una funzione f: A \to \mathcal{P}(A), esiste sempre X \in \mathcal{P}(A), fatto da tutti e soli gli elementi che non appartengono alla propria immagine, e questo insieme non è antimmagine di nulla.

@pic: per caso intendevi "immagine", anziché "antimmagine"? Nel senso che non esiste alcun x \in A tale che f(x) = X? Sicché f(\cdot) non può essere suriettiva , e perciò neppure bigettiva? Btw, davvero brillante il modo in cui costruisci l'insieme X, definendo X:=\{x \in A: x \notin f(x)\}.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5357
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)

Messaggioda killing_buddha il mar 20 ott 2009, 16:23

Btw, davvero brillante il modo in cui costruisci l'insieme X

Brillante, e piuttosto classico ;)
- Se incontri il Buddha uccidilo. Devi vivere libero da ogni dogma: se non riesci a uccidere Buddha, come ucciderai il tuo pregiudizio?
- "Peu d'abstraction on éloigne de la géometrie; beaucoup on y ramène"
Avatar utente
killing_buddha
 
Messaggi: 2744
Iscritto il: gio 17 lug 2008, 19:51

Messaggioda pic il dom 1 nov 2009, 14:02

Si', salvo, intendevo immagine. Correggo :redface:
Avatar utente
pic
 
Messaggi: 693
Iscritto il: gio 12 giu 2008, 14:32
Località: London, UK

Messaggioda lazyhaze il ven 25 giu 2010, 23:28

salvo.tringali ha scritto:Visto la soluzione di Albe (dopo averla texata a puntino). Anche se non mi spiego la ragione, per cui abbia scelto di lavorare in un verso con le rappresentazioni decimali e nell'altro con le rappresentazioni binarie, quando avrebbe potuto utilizzare unicamente queste ultime, e risparmiarsi così uno sforzo definitivamente inutile. ;)

Se intendi che con le rappresentazioni binarie avremmo avuto anche l'iniezione ti sbagli, infatti i due sottoinsiemi dei numeri naturali \{1\} e \{2, 3, \ldots\} hanno immagine 0,1 = 0,0\overline{1}. La cosa può essere aggiustata come segue, ma con uno sforzo definitivamente inutile, vista la possibilità di considerare la rappresentazione decimale:

Siano \mathfrak{A} l'insieme dei sottoinsiemi di \mathbb{N} il cui complementare in \mathbb{N} è finito, e \mathfrak{B} l'insieme dei sottoinsiemi di \mathbb{N} il cui complementare è infinito. \mathfrak{A} ha la cardinalità del numerabile, infatti per ogni n \in \mathbb{N} \cup \{0\} esistono un numero finito di A \in \mathfrak{A} la cui somma degli elementi del complementare è uguale ad n, e l'unione di un numero al più numerabile di insiemi al più numerabili (in questo caso addirittura finiti) è numerabile. Ma allora \mathcal{P}(\mathbb{N}) = \mathfrak{A}\cup\mathfrak{B} ha la stessa cardinalità di \mathfrak{B}, dato che la cardinalità di quest'ultima è ovviamente almeno numerabile. A questo punto la suriezione di Albe (da \mathfrak{B} in [0,1)) è anche un'iniezione perché abbiamo escluso tutti i sottoinsiemi la cui rappresentazione binaria sia definitivamente uguale a 1. Abbiamo la tesi: \big|[0,1]\big|= \big|[0,1)\big|=|\mathcal{P}(\mathbb{N})|.

(Tengo a precisare che il ragionamento non è mio ma di Kolmogorov e Fomin, in Elementi di teoria delle funzioni e di analisi funzionale.)

Sorge spontanea la domanda (a cui non so rispondere): si può esplicitare una biezione tra \mathcal{P}(\mathbb{N}) e [0,1]?

Edit: chiarisco una frase e correggo un typo su segnalazione privata di salvo.tringali, che ringrazio. Edit 2: altre piccole correzioni dovute al fatto che consideravo 0 \in \mathbb{N}.
Ultima modifica di lazyhaze il dom 18 lug 2010, 22:30, modificato 1 volta in totale.
lazyhaze
 
Messaggi: 1
Iscritto il: ven 25 giu 2010, 18:38

4 occhi vedono meglio di 2

Messaggioda salvo.tringali il sab 26 giu 2010, 10:26

lazyhaze ha scritto:Se intendi che con le rappresentazioni binarie avremmo avuto anche l'iniezione ti sbagli, infatti i due sottoinsiemi dei numeri naturali \{1\} e \{2, 3, \ldots\} hanno immagine 0,1 = 0,0\overline{1}. La cosa può essere aggiustata come segue, ma con uno sforzo definitivamente inutile, vista la possibilità di considerare la rappresentazione decimale [...]

Hai perfettamente ragione, sì. Adesso mi spiego le ragioni di Albe.

Albe ha scritto:[...] Quindi si desume che \big|[0,1]\big|= |\mathcal{P}(\mathbb{N})| [...]

lazyhaze ha scritto:Segnalo una imprecisione nel post di Albe: “quindi si desume che \big|[0,1]\big|= |\mathcal{P}(\mathbb{N})|” e non \leq. Mi è sembrato di capire che segnalare anche le “inezie” come queste sia cosa gradita: se non è così ditemelo e le tengo per me. :)

Ho provveduto a editare il refuso. E credo di affermare una posizione condivisa, se dico che, da queste parti, anche la segnalazione delle "inezie" è assai apprezzata. Benché, quando si tratti palesemente di typo, la prassi è di utilizzare i pm, per darne notizia all'autore o a un mod, così che si possa fissarlo.
"Che bella storia", disse l'Alchimista. | Whatever can be encoded by syntax shouldn't be left to semantics. | Homomorphisms are to algebraic structures as seminorms are to ordered structures.
Avatar utente
salvo.tringali
 
Messaggi: 5357
Iscritto il: mar 17 giu 2008, 19:46
Località: Karl-Franzens-Universität, Graz (AT)


Torna a Teoria

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite