[Teoria Degli Insiemi]Funzione biiettiva?
"Definisci, se esiste, una funzione biiettiva fra l'insieme dei numeri naturali e l'insieme dei suoi sottoinsiemi finiti."
Questo è il testo dell'esercizio su cui ho avuto un paio di incertezze.
Quello che mi chiede è di definire una funzione, io l'ho definita in questo modo:
F:N --> P(N)fin = {(a,{b})€ N X P(N)fin : a=b }
Secondo voi è corretto?
Dovevo specificare/aggiungere qualcos'altro?
Non ho usato LaTeX perchè al momento sto postando dal telefono, quindi mi scuso se le espressioni non sono belle da vedere
Questo è il testo dell'esercizio su cui ho avuto un paio di incertezze.
Quello che mi chiede è di definire una funzione, io l'ho definita in questo modo:
F:N --> P(N)fin = {(a,{b})€ N X P(N)fin : a=b }
Secondo voi è corretto?
Dovevo specificare/aggiungere qualcos'altro?
Non ho usato LaTeX perchè al momento sto postando dal telefono, quindi mi scuso se le espressioni non sono belle da vedere
Risposte
"AlexanderSC":
L'insieme dei sottoinsiemi finiti di \( N \) non avrà comunque infiniti elementi?
Sì, certo, ne avrà infiniti, ma quanti? Ci sono tanti infiniti, e certi infiniti sono più infiniti di altri, come stiamo discettando da parecchio tempo. Non si capisce la domanda che hai in testa.
Voglio capire perché può esistere una corrispondenza biunivoca tra l'insieme \( \aleph \) e l'insieme dei suoi sottoinsiemi finiti (che per semplicità chiamerò \( F \) ), e non fra \( \aleph \) e \( \wp (\aleph ) \) .
Applico il teorema di Cantor per dimostrare che non esiste una \( f:\aleph \rightarrow F \) \( biiettiva \) :
Per assurdo ipotizzo che esista una \( f \) \( suriettiva \) chiamata \( g \) che da $ aleph $ va in $ F $ .
Fra tutti i sottoinsiemi finiti, mi prendo quel sottoinsieme $ U={x in aleph : x notin g(x)} $ .
Qualsiasi elemento di $ aleph $ io prenda, esso non potrà essere associato al sottoinsieme $ U $ , perché risulterebbe in una contraddizione infinita, così dimostrando che l'insieme $ aleph $ non si trova in corrispondenza biunivoca con $ F $ .
Applico il teorema di Cantor per dimostrare che non esiste una \( f:\aleph \rightarrow F \) \( biiettiva \) :
Per assurdo ipotizzo che esista una \( f \) \( suriettiva \) chiamata \( g \) che da $ aleph $ va in $ F $ .
Fra tutti i sottoinsiemi finiti, mi prendo quel sottoinsieme $ U={x in aleph : x notin g(x)} $ .
Qualsiasi elemento di $ aleph $ io prenda, esso non potrà essere associato al sottoinsieme $ U $ , perché risulterebbe in una contraddizione infinita, così dimostrando che l'insieme $ aleph $ non si trova in corrispondenza biunivoca con $ F $ .
E' spiegato in maniera terribile, e con una notazione che grida vendetta al cielo, ma spero tu abbia capito cosa intendevo.
"fmnq":
ma spero tu abbia capito cosa intendevo.
Non capisco a cosa ti riferisci, fino ad ora le uniche cose che ho capito sono che :
-Esiste una funzione iniettiva che va da l'insieme dei numeri Naturali $ aleph $ , all' insieme dei suoi sottoinsiemi finiti $ F $ .( $ f:aleph rarr F $ è biiettiva)
-Non esiste invece una funzione iniettiva che va da l'insieme dei numeri Naturali $ aleph $ , all' insieme delle parti dei numeri Naturali( \( f:\aleph \rightarrow \wp (\aleph ) \) è biiettiva)
Della seconda affermazione me ne capacito perché mi hai dimostrato con Cantor che è così.
Della prima affermazione no, perché non riesco a trovare una differenza fra questo caso ed il secondo, anche avendo come spunto Cantor, che ho cercato di replicare applicandolo a questo caso.
Questa applicazione l'ho fatta solo per darti una dimostrazione del mio ragionamento e magari darti un indizio su cosa non sto capendo, affinché tu possa aiutarmi ad arrivarci.
Per caso la risposta risiede nel fatto che il sottoinsieme U={x∈ℵ:x∉g(x)} non è un sottoinsieme finito ?
"AlexanderSC":
Per caso la risposta risiede nel fatto che il sottoinsieme U={x∈ℵ:x∉g(x)} non è un sottoinsieme finito ?
Tralascio di commentare il resto, che è un pandemonio. Sì, la risposta è sì.
Ok, mi serviva questo.
Visto che non possiamo dimostrare il contrario, affermiamo che esiste una funzione biiettiva f:ℵ→F ?
Mi aiuti a definire una funzione del genere?
Visto che non possiamo dimostrare il contrario, affermiamo che esiste una funzione biiettiva f:ℵ→F ?
Mi aiuti a definire una funzione del genere?
Non finché ti ostini a indicare con $\aleph$ (che non significa niente, tutt'al più potrebbe indicare la classe propria dei -di certi?- cardinali), quello che andrebbe denotato con $NN$.
Al netto di questo, sia $X$ un insieme infinito, vuoi dimostrare che l'insieme dei sottoinsiemi finiti di $X$ è in biiezione con $X$; per CSB ti basta trovare una funzione iniettiva da $P_0X$ a (un insieme con la stessa cardinalità di) $X$; quest'ultimo insieme è \(X' = \coprod_{n\in\mathbb N} X^n\), per il motivo evidente che esiste una funzione iniettiva $P_0X\to X'$ che manda una $n$-upla di elementi di $X$ (cioè il sottoinsieme finito $A = \{x_1,...,x_n\}\subset X$) in $(x_1,..,x_n)\in X^n$.
Il fatto che $X'$ abbia la stessa cardinalità di $X$ segue da un facile argomento di aritmetica (hint: \(|X\times\mathbb N| = |X|\)).
Al netto di questo, sia $X$ un insieme infinito, vuoi dimostrare che l'insieme dei sottoinsiemi finiti di $X$ è in biiezione con $X$; per CSB ti basta trovare una funzione iniettiva da $P_0X$ a (un insieme con la stessa cardinalità di) $X$; quest'ultimo insieme è \(X' = \coprod_{n\in\mathbb N} X^n\), per il motivo evidente che esiste una funzione iniettiva $P_0X\to X'$ che manda una $n$-upla di elementi di $X$ (cioè il sottoinsieme finito $A = \{x_1,...,x_n\}\subset X$) in $(x_1,..,x_n)\in X^n$.
Il fatto che $X'$ abbia la stessa cardinalità di $X$ segue da un facile argomento di aritmetica (hint: \(|X\times\mathbb N| = |X|\)).
"fmnq":
Non finché ti ostini a indicare con $\aleph$ (che non significa niente, tutt'al più potrebbe indicare la classe propria dei -di certi?- cardinali), quello che andrebbe denotato con $NN$.
Scusa, non trovando nel programma $NN$, pensavo che $\aleph$ fosse il simbolo con cui si indicasse l'Insieme dei numeri naturali.
"fmnq":
Al netto di questo, sia $X$ un insieme infinito, vuoi dimostrare che l'insieme dei sottoinsiemi finiti di $X$ è in biiezione con $X$; per CSB ti basta trovare una funzione iniettiva da $P_0X$ a (un insieme con la stessa cardinalità di) $X$;
Uhm, posso riscrivere il tuo messaggio in questo modo per confondermi di meno?
per CSB ti basta trovare una funzione iniettiva da $P_0X$ a \( X' \) (cioè un insieme con la stessa cardinalità di $X$)
o "un insieme con la stessa cardinalità di \( X \)" si riferisce a $P_0X$ ?
"fmnq":
quest'ultimo insieme è \(X' = \coprod_{n\in\mathbb N} X^n\)
Non capisco cosa \(\coprod_{n\in\mathbb N} X^n\) stia ad indicare ( con una veloce ricerca su google ho trovato che \( \amalg \) è un coprodotto, ma in tutte le rappresentazioni è accompagnato da una 'i=n' sotto di esso, e una 'm' sopra di esso, quindi non capisco cosa voglia dire in questo caso).
"fmnq":
per il motivo evidente che esiste una funzione iniettiva $P_0X\to X'$
Non era $P_0X\to X$ ?
"fmnq":
che manda una $n$-upla di elementi di $X$ (cioè il sottoinsieme finito $A = \{x_1,...,x_n\}\subset X$) in $(x_1,..,x_n)\in X^n$.
Il fatto che $X'$ abbia la stessa cardinalità di $X$ segue da un facile argomento di aritmetica (hint: \(|X\times\mathbb N| = |X|\)).
Penso che per capire questa parte, dovrò prima capire l'inizio.
Sì, non ti è per niente chiaro cosa devi fare, perché l'ho scritto ma non l'hai capito. Pensaci sopra.
PS: \(\coprod_{n\in\mathbb N} X^n = \coprod_{n=0}^\infty X^n\)
PS: \(\coprod_{n\in\mathbb N} X^n = \coprod_{n=0}^\infty X^n\)
Ancora, grazie per il tempo che mi hai dedicato fin'ora.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo