[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":
Secondo voi è corretto?
E secondo te?
Non ne sono tanto sicuro perchè l'insieme vuoto nell'insieme dei sottoinsiemi finiti di N non avrebbe un elemento ad esso associato se valesse questa funzione, e ciò non la renderebbe biiettiva, ma allo stesso tempo non sono sicuro se l'insieme vuoto fà parte dell'insieme che contiene tutti i sottoinsiemi finiti di N.
Si, ne fa parte, comunque oltre a quello tutti gli insiemi con almeno 2 elementi non stanno nell'immagine. Insomma la tua funzione è ben lontana dall'essere suriettiva (però è iniettiva).
Scusa se ti rispondo in ritardo . . .
Comunque hai assolutamente ragione, però sono sicuro che ogni elemento del primo insieme possa essere associato in qualche modo ad ogni altro elemento del secondo essendo entrambi insiemi infiniti, ma non so con quale funzione.
Qualcosa di questo tipo?
{(a,A),(b,B) \( \subseteq NX\wp (N)fin \) : \( a≠b\wedge A≠B \)}
Cioè, avremo coppie diverse tra loro, immagino possa scriverlo anche così: \( (a,A)≠(b,B) \)
Comunque hai assolutamente ragione, però sono sicuro che ogni elemento del primo insieme possa essere associato in qualche modo ad ogni altro elemento del secondo essendo entrambi insiemi infiniti, ma non so con quale funzione.
Qualcosa di questo tipo?
{(a,A),(b,B) \( \subseteq NX\wp (N)fin \) : \( a≠b\wedge A≠B \)}
Cioè, avremo coppie diverse tra loro, immagino possa scriverlo anche così: \( (a,A)≠(b,B) \)
"AlexanderSC":
Scusa se ti rispondo in ritardo . . .
Ma figurati, rispondere il giorno stesso non è ritardo, anzi!
Comunque hai assolutamente ragione, però sono sicuro che ogni elemento del primo insieme possa essere associato in qualche modo ad ogni altro elemento del secondo essendo entrambi insiemi infiniti
Infatti è così, ma non per il motivo che hai detto (e tra l'altro affinché quello che hai detto non sia banale devi dire che lo associa in modo biunuvoco).
Qualcosa di questo tipo?
{(a,A),(b,B) \( \subseteq NX\wp (N)fin \) : \( a≠b\wedge A≠B \)}
Cioè, avremo coppie diverse tra loro, immagino possa scriverlo anche così: \( (a,A)≠(b,B) \)
Sinceramente è illeggibile, non ho la più pallida idea di cosa tu voglia dire. Comunque prova a scrivere le funzioni tramite la regola che le definisce piuttosto che col grafico, è molto più chiaro.
Ad ogni modo forse dovresti interpretare l'esercizio come "dimostra che esiste" quella funzione invece di "esibisci" perché non credo sia possibile fare la seconda cosa.
Ok grazie, farò un tuffo sulla teoria che credo sia quella che al momento mi manchi.
Poi proverò a dare una risposta più adatta!
Poi proverò a dare una risposta più adatta!
Ho appena capito che non esiste una relazione del genere.
Userò l'esempio del perché non tutti gli insiemi infiniti sono equipotenti fra loro:
Se prendo tutti i numeri di N che vanno da 0 all'infinito, e cerco di associarli senza alcun criterio particolare a tutti i sottoinsiemi finiti di N, mi ritroverò con una tabella del genere:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | . . .
La colonna di sinistra sono gli elementi di N.
Gli 0 e gli 1 all'interno della tabella, servono ad indicare quali numeri si trovano all'interno dell'insieme corrispondente al numero in tabella. ( nel primo caso la relazione farà corrispondere a 0 l'insieme che contiene lo 0)
Se prendessimo il sottoinsieme che contiene tutti i numeri corrispondenti alla diagonale della tabella ( partendo da sopra-sinistra) che al momento corrisponde a {1, 1, 1 . . .}:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | . . .
E ne prendessimo il complemento, cioè { 0, 0, 0 . . .}.
Quando lo andremo ad inserire nella rappresentazione tabellare della nostra Relazione, ci accorgeremo che che tale lista di 0 e 1, prima o poi incontrerà la diagonale vera e proprio, e nel punto in cui concida, non saremo in grado di stabilire quale numero andare a mettere:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . .
4 | 0 | 0 | 0 | 1 | ? | | | | | | . . .
Quindi la funzione non sarà iniettiva, visto che non sarà in grado di legare tutti gli N a distinti elementi.Giusto?
Userò l'esempio del perché non tutti gli insiemi infiniti sono equipotenti fra loro:
Se prendo tutti i numeri di N che vanno da 0 all'infinito, e cerco di associarli senza alcun criterio particolare a tutti i sottoinsiemi finiti di N, mi ritroverò con una tabella del genere:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | . . .
La colonna di sinistra sono gli elementi di N.
Gli 0 e gli 1 all'interno della tabella, servono ad indicare quali numeri si trovano all'interno dell'insieme corrispondente al numero in tabella. ( nel primo caso la relazione farà corrispondere a 0 l'insieme che contiene lo 0)
Se prendessimo il sottoinsieme che contiene tutti i numeri corrispondenti alla diagonale della tabella ( partendo da sopra-sinistra) che al momento corrisponde a {1, 1, 1 . . .}:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | . . .
E ne prendessimo il complemento, cioè { 0, 0, 0 . . .}.
Quando lo andremo ad inserire nella rappresentazione tabellare della nostra Relazione, ci accorgeremo che che tale lista di 0 e 1, prima o poi incontrerà la diagonale vera e proprio, e nel punto in cui concida, non saremo in grado di stabilire quale numero andare a mettere:
N | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | . . . NUMERI ALL' INTERNO DEL SOTTOINSIEME FINITO
-------------------------------------------------------
0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (0, {0})
1 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | . . . = (1, {1, 2, 3})
2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | . . . = (2, {sottoinsieme dei numeri pari})
3 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | . . .
4 | 0 | 0 | 0 | 1 | ? | | | | | | . . .
Quindi la funzione non sarà iniettiva, visto che non sarà in grado di legare tutti gli N a distinti elementi.Giusto?
"AlexanderSC":
Ho appena capito che non esiste una relazione del genere.
Invece si che esiste, infatti si può dimostrare che ogni insieme infinito è in biezione con l'insieme dei suoi sottoinsiemi finiti, anche se, che io sappia, non se ne conoscono di esplicite.
"AlexanderSC":
Quindi la funzione non sarà iniettiva. Giusto?
Per quanto detto sopra, no.
"otta96":
[quote="AlexanderSC"]Ho appena capito che non esiste una relazione del genere.
Invece si che esiste, infatti si può dimostrare che ogni insieme infinito è in biezione con l'insieme dei suoi sottoinsiemi finiti, anche se, che io sappia, non se ne conoscono di esplicite.
[/quote]
Beh, la dimostrazione di CSB (se esiste una iniezione $A\to B$ e una iniezione $B\to A$, esiste una biiezione $A\to B$) è costruttiva...
"otta96":
Invece si che esiste, infatti si può dimostrare che ogni insieme infinito è in biezione con l'insieme dei suoi sottoinsiemi finiti, anche se, che io sappia, non se ne conoscono di esplicite.
Un insieme infinito può essere messo in corrispondenza biunivoca con l'insieme dei suoi sottoinsiemi (quindi che non include solo sottoinsiemi finiti)?
O ciò è valido solo per la funzione che và da un insieme infinito all'insieme dei suoi sottoinsiemi finiti?
"AlexanderSC":
Un insieme infinito può essere messo in corrispondenza biunivoca con l'insieme dei suoi sottoinsiemi (quindi che non include solo sottoinsiemi finiti)?
Non si può, è un teorema di Cantor: non esiste nessuna funzione suriettiva da $X$ a $2^X$; se $X$ è finito, ovvio. Se $X$ è infinito, supponi esista (diciamo che si chiama $g$) e prendi il sottoinsieme $U = \{x\in X | x \notin gx\}$. Non può esistere nessun $y\in X$ tale che $gy=U$.
Non capisco perché hai preso il sottoinsieme U e neanche per cosa stia "gx" 
Poi chi è D? Il dominio?
Poi chi è D? Il dominio?
Ho preso $U$ per far funzionare la dimostrazione; $D$ è $U$, ho corretto. $gx$ è l'immagine di $x\in X$ mediante la funzione $g : X\to 2^X$.
"fmnq":
Non si può, è un teorema di Cantor: non esiste nessuna funzione suriettiva da $X$ a $2^X$; se $X$ è finito, ovvio. Se $X$ è infinito, supponi esista (diciamo che si chiama $g$) e prendi il sottoinsieme $U = \{x\in X | x \notin gx\}$. Non può esistere nessun $y\in X$ tale che $gy=U$.
Ok, allora questo insieme U, poichè non è formato da nessun elemento(visto che non troviamo un singolo elemento che soddisfi la sua proprietà), non sarebbe un insieme vuoto?
Poi l'esempio del teorema di Cantor usa una funzione biiettiva, non surriettiva, perchè stiamo usando quest'ultima?
$U$ non è vuoto; contiene tutti gli elementi di $X$ tali che $x$ non è un elemento di $g(x)$. Stiamo dimostrando che non esiste una funzione suriettiva da $X$ a $2^X$, perché allora non può esisterne nemmeno una biiettiva.
(Le mie risposte sono volutamente terse; è parte del mio invito a riflettere da solo su questi argomenti elementari).
(Le mie risposte sono volutamente terse; è parte del mio invito a riflettere da solo su questi argomenti elementari).
Uhm, credo di aver capito.
Se gli assegniamo una y a questo sottoinsieme U ( $ f(y) = U $ ) , vorrà dire che per definizione $ yin U $ , ma se entra a far parte degli elementi di U, ciò vuol dire che ora $ yin gy $ , e ciò andrebbe contro la definizione della stessa U.
Quindi ci ritroviamo in una situazione dove non possiamo assegnare un elemento a questo sottoinsieme, e quindi l'ipotetica funzione g non potrà essere suriettiva, anche se abbiamo ipotizzato che lo fosse, dimostrando che una funzione biiettiva ( cioè sia iniettiva che SURRIETTIVA) fra un insieme e l'insieme dei suoi sottoinsiemi non esiste.
Perfetto, grazie
La cosa strana è che prima mi hai detto che esisteva una funzione biiettiva fra un insieme e l'insieme dei suoi sottoinsiemi, why?
Se gli assegniamo una y a questo sottoinsieme U ( $ f(y) = U $ ) , vorrà dire che per definizione $ yin U $ , ma se entra a far parte degli elementi di U, ciò vuol dire che ora $ yin gy $ , e ciò andrebbe contro la definizione della stessa U.
Quindi ci ritroviamo in una situazione dove non possiamo assegnare un elemento a questo sottoinsieme, e quindi l'ipotetica funzione g non potrà essere suriettiva, anche se abbiamo ipotizzato che lo fosse, dimostrando che una funzione biiettiva ( cioè sia iniettiva che SURRIETTIVA) fra un insieme e l'insieme dei suoi sottoinsiemi non esiste.
Perfetto, grazie
La cosa strana è che prima mi hai detto che esisteva una funzione biiettiva fra un insieme e l'insieme dei suoi sottoinsiemi, why?
"otta96":
Invece si che esiste, infatti si può dimostrare che ogni insieme infinito è in biezione con l'insieme dei suoi sottoinsiemi finiti, anche se, che io sappia, non se ne conoscono di esplicite.
Mi riferisco a questo.
Sottoinsiemi finiti.
Sì, ma lo stesso esempio non può essere applicato anche qua?
L'insieme dei sottoinsiemi finiti di \( N \) non avrà comunque infiniti elementi?
Quindi non potrebbe comunque esistere un sottoinsieme $ U = { nin N : n notin gn} $ che viene costruito a mano a mano che associamo elementi di N agli elementi dell'insieme di sottoinsiemi finiti di N?
L'insieme dei sottoinsiemi finiti di \( N \) non avrà comunque infiniti elementi?
Quindi non potrebbe comunque esistere un sottoinsieme $ U = { nin N : n notin gn} $ che viene costruito a mano a mano che associamo elementi di N agli elementi dell'insieme di sottoinsiemi finiti di N?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo