[Teoria Degli Insiemi]Funzione biiettiva?

[AlexanderSC]

"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

[otta96]

Secondo voi è corretto?

E secondo te?

[AlexanderSC]

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.

[otta96]

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).

[AlexanderSC]

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) \)

[otta96]

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.

[AlexanderSC]

Ok grazie, farò un tuffo sulla teoria che credo sia quella che al momento mi manchi.
Poi proverò a dare una risposta più adatta!

[AlexanderSC]

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?

[otta96]

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.

Quindi la funzione non sarà iniettiva. Giusto?

Per quanto detto sopra, no.

[fmnq]

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.

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...