Dimostrazione equipotenza di N e suo insieme delle parti
Sono a conoscenza del fatto che l'insieme delle parti di un insieme ha sempre cardinalità maggiore dell'insieme stesso.
Riflettendo su questo argomento ho formulato questa "dimostrazione" che sembra affermare che l'insieme dei naturali e il suo insieme delle parti sono equipotenti..
Qualcuno mi può aiutare a capire dov'è la falla?
Posso definire l'insieme delle parti come l'unione degli insiemi di sottoinsiemi di $NN$ che hanno la stessa cardinalità:
$P(NN)=\bigcup_{n=0}^{\infty} A_n$ con $A_n={ x sube NN | |x|=n}$
allora le funzioni $G_n : A_n -> NN^n$ definite da:
$AA x={x_1, x_2, ...} in A_n$
$G_n(x)=(x_i, , x_i,, , ...)$ con $x_i, < x_i,, < x_i,,, < ...$ (posso farlo perchè $NN$ è ben ordinato)
sono tutte iniettive perchè se ho due immagini uguali (dato che ho n-uple ordinate) ho proprio la definizione di identità di due insiemi.
Così se questa cosa funziona $AA n in NN$ posso dire che $EE$ una funzione iniettiva da $P(N)$ in $\bigcup_{n=0}^{\infty} NN^n$ .. giusto?
ma $AA n NN^n$ è numerabile, $\bigcup_{n=0}^{\infty} NN^n$ è unione di insiemi numerabili e quindi esso stesso numerabile.
il che implicherebbe $P(NN)$ numerabile!
Mi scuso per la presentazione ma anche copiando i codici da "Formula" non ottengo nulla.
Edit: Grazie Samy21
Riflettendo su questo argomento ho formulato questa "dimostrazione" che sembra affermare che l'insieme dei naturali e il suo insieme delle parti sono equipotenti..
Qualcuno mi può aiutare a capire dov'è la falla?
Posso definire l'insieme delle parti come l'unione degli insiemi di sottoinsiemi di $NN$ che hanno la stessa cardinalità:
$P(NN)=\bigcup_{n=0}^{\infty} A_n$ con $A_n={ x sube NN | |x|=n}$
allora le funzioni $G_n : A_n -> NN^n$ definite da:
$AA x={x_1, x_2, ...} in A_n$
$G_n(x)=(x_i, , x_i,, , ...)$ con $x_i, < x_i,, < x_i,,, < ...$ (posso farlo perchè $NN$ è ben ordinato)
sono tutte iniettive perchè se ho due immagini uguali (dato che ho n-uple ordinate) ho proprio la definizione di identità di due insiemi.
Così se questa cosa funziona $AA n in NN$ posso dire che $EE$ una funzione iniettiva da $P(N)$ in $\bigcup_{n=0}^{\infty} NN^n$ .. giusto?
ma $AA n NN^n$ è numerabile, $\bigcup_{n=0}^{\infty} NN^n$ è unione di insiemi numerabili e quindi esso stesso numerabile.
il che implicherebbe $P(NN)$ numerabile!
Mi scuso per la presentazione ma anche copiando i codici da "Formula" non ottengo nulla.
Edit: Grazie Samy21
Risposte
Ho l'impressione che la cardinalità dell'insieme delle parti sia maggiore di quella dell'insieme dato, solo se questo contiene un numero finito di elementi. Un po' come dire che un sottoinsieme proprio di un dato insieme ha cardinalità minore di tale insieme solo per quantità finite: mi pare che c'è una definizione di insieme infinito che dice che "un insieme si definisce infinito se e solo se lo si può mettere in corrispondenza biunicoca con qualche suo sottoinsieme proprio". E' un ricordo "a memoria" quindi mi scuso della poca rigorosità... in pratica l'insieme N è infinito perchè può essere messo in corrispondenza biunivoca, ad esempio, con quello di tutti i numeri pari: naturali e pari hanno la stessa cardinalità, pur essendo i pari in un sottoinsieme proprio di N! Ma sarebbe lo stesso per N e l'insieme di tutti i naturali stessi moltiplicati per un n qualunque (appartenente ad N)
"Mikk_90":
Mi scuso per la presentazione ma anche copiando i codici da "Formula" non ottengo nulla.
Dovresti metterle tra i simboli di dollaro $\$$
"cisufo":
Ho l'impressione che la cardinalità dell'insieme delle parti sia maggiore di quella dell'insieme dato, solo se questo contiene un numero finito di elementi. Un po' come dire che un sottoinsieme proprio di un dato insieme ha cardinalità minore di tale insieme solo per quantità finite: mi pare che c'è una definizione di insieme infinito che dice che "un insieme si definisce infinito se e solo se lo si può mettere in corrispondenza biunicoca con qualche suo sottoinsieme proprio". E' un ricordo "a memoria" quindi mi scuso della poca rigorosità... in pratica l'insieme N è infinito perchè può essere messo in corrispondenza biunivoca, ad esempio, con quello di tutti i numeri pari: naturali e pari hanno la stessa cardinalità, pur essendo i pari in un sottoinsieme proprio di N! Ma sarebbe lo stesso per N e l'insieme di tutti i naturali stessi moltiplicati per un n qualunque (appartenente ad N)
Mi dispiace cisufo ma qui ti sbagli. Ti faccio un esempio semplice N e R. Sono uno sottoinsieme dell'altro ma hanno cardinalità diverse,
in particolare P(N) ha proprio la cardinalità di R.
La definizione che dai di insieme infinito è corretta ma questa non implica che ci sia un solo tipo d'infinito.
non so se ho capito quello che intendi fare con la tua dimostrazione, ma mi pare che tu metta in relazione l'insieme $NN$ non con $P(NN)$, ma con $P(NN)\//\sim$, cioè con l'insieme delle parti di $NN$ quozientato con la relazione di equivalenza "avere la stessa cardinalità", cioè non distinguendo tra sottoinsiemi diversi aventi lo stesso numero di elementi.
Provo ad essere più chiaro.
$AA n in NN$ la funzione $G_n$ è iniettiva e ha come dominio $A_n={x sube NN | |x|=n}$ e come codominio $N^n$
sostanzialmente ${A_n}_n$ è una partizione di $P(NN)$.
Quindi questa "dimostrazione" dice che i vari elementi della partizione di $P(NN)$ sono numerabili, che implica $P(NN)$ numerabile.
$AA n in NN$ la funzione $G_n$ è iniettiva e ha come dominio $A_n={x sube NN | |x|=n}$ e come codominio $N^n$
sostanzialmente ${A_n}_n$ è una partizione di $P(NN)$.
Quindi questa "dimostrazione" dice che i vari elementi della partizione di $P(NN)$ sono numerabili, che implica $P(NN)$ numerabile.
sarà che sono arrugginita, ma io non vedo l'iniettività, perché non vedo come sono definite queste funzioni.
ad esempio, prendiamo $G_5$. quali sarebbero le immagini di ${1,2,3,4,5}, {1,10,15,40,80}, ....$ ?
ad esempio, prendiamo $G_5$. quali sarebbero le immagini di ${1,2,3,4,5}, {1,10,15,40,80}, ....$ ?
L'esempio di N ed R è corretto, ma parlando di N e P(N) non riesco a vedere l'equipotenza fra P(N) ed R, poichè non vedo "continuità" fra i sottoinsiemi di N. Ma forse sono arrugginito un po' anch'io...
@adaBTTLS sono funzioni che che prendono in entrata sottoinsiemi di $NN$ di una certa cardinalità n e
restituiscono un n-upla ordinata in ordine crescente degli elementi del sottoinsieme.
@cisufo penso si possa costruire una biiezione tra $P(NN)$ e [0,1] così:
$AA x in P(NN)$ associ l'n-upla ordinata in modo crescente formata dagli elementi dell'insieme. E decidiamo di associare all'insieme che contiene l'insieme vuoto 1.
${O/} -> 1$
e quindi $AA x=(a_1, a_2, ...) -> 0,a_1a_2a_3...$
In questo modo sei sicuro di prendere qualsiasi numero dell'intervallo [0,1] perchè la sua espansione decimale la puoi vedere come sottoinsieme di $NN$
restituiscono un n-upla ordinata in ordine crescente degli elementi del sottoinsieme.
@cisufo penso si possa costruire una biiezione tra $P(NN)$ e [0,1] così:
$AA x in P(NN)$ associ l'n-upla ordinata in modo crescente formata dagli elementi dell'insieme. E decidiamo di associare all'insieme che contiene l'insieme vuoto 1.
${O/} -> 1$
e quindi $AA x=(a_1, a_2, ...) -> 0,a_1a_2a_3...$
In questo modo sei sicuro di prendere qualsiasi numero dell'intervallo [0,1] perchè la sua espansione decimale la puoi vedere come sottoinsieme di $NN$
Perfetto, grazie: va da sè, che [0,1] in R ed R stesso sono equipotenti... esatto?
"cisufo":
Perfetto, grazie: va da sè, che [0,1] in R ed R stesso sono equipotenti... esatto?
Si esatto, ogni intervallo di R ha la potenza del continuo.
"Mikk_90":
@adaBTTLS sono funzioni che che prendono in entrata sottoinsiemi di $NN$ di una certa cardinalità n e
restituiscono un n-upla ordinata in ordine crescente degli elementi del sottoinsieme.
questo presuppone il saper ordinare sia i sottoinsiemi di $NN$ sia le $n$-uple. visto che se fosse vero sarebbe un risultato clamoroso, perché non spendere qualche parola in più sul "come" vengono ordinati gli elementi di entrambi gli insiemi?
giacché ci siamo, qui si tratta di confrontare la cardinalità di $P(NN)$ non con $NN^n$ ma con $uuu_(n in NN) NN^n$ ...
Si certo l'avevo scritto nel mio post iniziale:
Per ordinare i sottoinsiemi di $NN$ non ci dovrebbero essere problemi perchè per l'appunto $NN$ è ben ordinato e questo vuol dire che ogni suo
sottoinsieme non vuoto ha un elemento minimo; quindi il primo elemento della n-upla è il minimo dell'insieme di partenza,
per il secondo si considera l'insieme di partenza meno il minimo e così via..
"Mikk_90":
Così se questa cosa funziona $AA n in NN$ posso dire che $EE$ una funzione iniettiva da $P(N)$ in $\bigcup_{n=0}^{\infty} NN^n$ .. giusto?
Per ordinare i sottoinsiemi di $NN$ non ci dovrebbero essere problemi perchè per l'appunto $NN$ è ben ordinato e questo vuol dire che ogni suo
sottoinsieme non vuoto ha un elemento minimo; quindi il primo elemento della n-upla è il minimo dell'insieme di partenza,
per il secondo si considera l'insieme di partenza meno il minimo e così via..
sì, così va bene. anche se non hai scritto come è fatta questa funzione, è abbastanza chiaro come si possa costruire.
a questo punto, spero che intervenga qualche "specialista" dell'argomento, fresco di studi, che ci dica qualcosa in più sulla cardinalità di $uuu_(n in NN)\NN^n$.
a questo punto, spero che intervenga qualche "specialista" dell'argomento, fresco di studi, che ci dica qualcosa in più sulla cardinalità di $uuu_(n in NN)\NN^n$.
Lo spero anche io.
Ma cosa intendi quando dici che non spiego com'è fatta la funzione?
Insomma una volta definiti dominio e codominio, la regola e verificato che è ben definita cos'altro bisogna dire?
Ma cosa intendi quando dici che non spiego com'è fatta la funzione?
Insomma una volta definiti dominio e codominio, la regola e verificato che è ben definita cos'altro bisogna dire?
Ammetto di aver letto i messaggi precedenti con un po' di fretta.
Ecco la mia obiezione alla dimostrazione di mikk_90:
Siamo proprio sicuri di questa uguaglianza?
Prendiamo l'insieme $U$ dei numeri pari ovviamente sottoinsieme di $NN$ (e dunque $U\in P(NN)$).
Ma $U$ non appartiene a nessuno degli $A_n$...
Il problema è che non si sono considerati i sottoinsiemi di $NN$ di cardinalità infinita.
Ho sparato qualche cavolata?
Ecco la mia obiezione alla dimostrazione di mikk_90:
"Mikk_90":
Posso definire l'insieme delle parti come l'unione degli insiemi di sottoinsiemi di $NN$ che hanno la stessa cardinalità:
$P(NN)=\bigcup_{n=0}^{\infty} A_n$ con $A_n={ x sube NN | |x|=n}$
Siamo proprio sicuri di questa uguaglianza?
Prendiamo l'insieme $U$ dei numeri pari ovviamente sottoinsieme di $NN$ (e dunque $U\in P(NN)$).
Ma $U$ non appartiene a nessuno degli $A_n$...
Il problema è che non si sono considerati i sottoinsiemi di $NN$ di cardinalità infinita.
Ho sparato qualche cavolata?
Confermo, questa uguaglianza:
"Mikk_90":è falsa. Mikk_90, nella tua dimostrazione dimentichi i sottoinsiemi infiniti di $NN$.
$P(NN)=\bigcup_{n=0}^{\infty} A_n$
Effettivamente avevo notato che sono gli insiemi infiniti che si possono associare agli irrazionali in [0,1]
che danno problemi in quanto sono appunto non numerabili.
Un mio dubbio era anche se l'insieme $NN^oo$ fosse compreso.. sempre se questa scrittura abbia senso in quanto $oo$ non è un numero..
C'è una notazione che lo possa rappresentare?
Un'idea:
$P(NN)$ può essere rappresentato come l'unione di tutti gli $A_n$ sull'insieme degli indici $omega+1$ che essendo l'ordinale successore di $omega$ per l'appunto non è numerabile e quindi salta "l'unione numerabile di insiemi numerabili" sia per gli indici che per gli insiemi.
Si mi sembra la spiegazione giusta.
Grazie dell'aiuto
che danno problemi in quanto sono appunto non numerabili.
Un mio dubbio era anche se l'insieme $NN^oo$ fosse compreso.. sempre se questa scrittura abbia senso in quanto $oo$ non è un numero..
C'è una notazione che lo possa rappresentare?
Un'idea:
$P(NN)$ può essere rappresentato come l'unione di tutti gli $A_n$ sull'insieme degli indici $omega+1$ che essendo l'ordinale successore di $omega$ per l'appunto non è numerabile e quindi salta "l'unione numerabile di insiemi numerabili" sia per gli indici che per gli insiemi.
Si mi sembra la spiegazione giusta.
Grazie dell'aiuto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo