Dimostrare che un insieme è finito

[fairyvilje]

Se riesco stasera scrivo il tutto in modo più simbolico. Di fatto riduco il problema di esistenza della biezione al contare il numero di mappe biettive possibli, arrivando a dimostrare che sono 0.

[Ianero]

Il fatto che questa dimostrazione sembri "ovvia" è dovuto al fatto che esistono due definizioni di insieme finito o infinito.

1) Un insieme è finito secondo Dedekind se non è possibile mapparlo biunivocamente in un suo sottoinsieme proprio
2) Un insieme è finito se è mappabile biunivocamente con un per qualche n.

Allora ciò che voglio io si può dimostrare se si fa vedere che un insieme infinito secondo Dedekind è anche infinito. Poi negando si ottiene che un insieme finito è anche finito secondo Dedekind e quindi la dimostrazione diventa in discesa.

Lemma 1:
Se è una funzione iniettiva, allora .

Dimostrazione:

poiché allora per tutti gli che appartengono ad e non ad , , ma a causa dell'iniettività di .
Per cui .

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Dimostro ora che un insieme A che sia Dedekind-infinito è anche infinito nel senso che non è possibile trovare una mappa biunivoca tra esso e un per qualsiasi .

Per assurdo sia Dedekind-infinito e finito, ovvero in corrispondenza biunivoca con un suo sottoinsieme proprio (tramite ) e in corrispondenza biunivoca con un , per qualche n naturale (tramite ).

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Chiamiamo il sottoinsieme proprio di , . Allora dal Lemma 1 (e siccome è biunivoca) è in corrispondenza biunivoca con un sottoinsieme proprio di .

Ora andiamo avanti per caso peggiore.
Nel peggiore dei casi (peggiore per me che voglio andare a trovare la contraddizione) il sottoinsieme proprio di con cui è in corrispondenza biunivoca è l'insieme che si ottiene eliminando da un solo elemento.
Sarà quindi o un insieme che è in corrispondenza biunivoca con esso.
Infatti poiché l'insieme è della forma posso scegliere ogni volta un elemento diverso da eliminare (diverso da ) e mettere tale insieme ottenuto in corrispondenza biunivoca con .

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

A questo punto posso riapplicare ad , ottenendo .
è un sottoinsieme proprio di per il Lemma 1.
Sempre per il Lemma 1 è in corrispondenza biunivoca (tramite una restrizione di ) nel caso peggiore con .

Sorgente FidoCadJ | Ingrandisci | Cos'è Fidocad

Posso ripetere questo discorso nel caso peggiore n volte arrivando a dire che , che è in corrispondenza biunivoca con (tramite ), è anche in corrispondenza biunivoca con (tramite ).

Assurdo.

Quindi un insieme Dedekind-infinito è anche infinito nel senso che non è possibile trovare una mappa biunivoca tra esso e un per qualsiasi .

Quindi un insieme finito è anche Dedekind-finito.

PS: leggendo in giro avevo trovato che per garantire l'equivalenza delle definizioni c'era inevitabilmente bisogno dell'assioma di scelta. Non mi sembra che nella mia costruzione ne abbia fatto uso però.

[DirtyDeeds]

Lemma 1:
Se è una funzione iniettiva, allora .

Partiamo da 'sto lemma, che così com'è scritto dice una cosa banale indipendente dall'iniettività: l'immagine di un sottoinsieme del dominio è contenuta nel codominio. Questo vale veramente per qualunque funzione, che sia iniettiva o no, ed è una conseguenza immediata della definizione di funzione.

Quindi, che lemma volevi veramente dimostrare? Prima di passare alle dimostrazioni complicate, bisogna avere ben chiare le idee semplici

[DirtyDeeds]

Visto che sembra interessarti la teoria degli insiemi, in questo messaggio ti avevo consigliato un libro, quello di Enderton, te lo consiglio ancora

[Ianero]

Grazie DirtyDeeds :)

Volevo dire che nel caso la funzione f non sia iniettiva non è garantito che un sottoinsieme proprio del dominio A venga mappato in un sottoinsieme ancora strettamente proprio di f(A).
È sbagliato?

Comunque sto cercando di sviscerare in modo completo e sistematico Zorich.
Il libro sulla teoria degli insiemi mi consigli di leggerlo ancora prima di questo?

[AjeieBrazov]

Per la dimostrazione puoi usare la cardinalità?

Edit: provo una dimostrazione, anche se mi sembra troppo semplice
Sia e
1) f è iniettiva se contiene al massimo un elemento
2) f è suriettiva contiene almeno un elemento
3) f è biettiva contiene uno ed un solo elemento.
Quindi, per la definizione stessa di funzione biettiva se e allora tale che , quindi la funzione non è biettiva ma suriettiva.
Forse servono anche le dimostrazioni di (1) e (2)?

[DirtyDeeds]

Volevo dire che nel caso la funzione f non sia iniettiva non è garantito che un sottoinsieme proprio del dominio A venga mappato in un sottoinsieme ancora strettamente proprio di f(A).

Allora hai sbagliato notazione, perché con hai prima indicato il codominio della funzione e poi l'immagine di . Quello che volevi dimostrare, allora, dovrebbe essere questo:

Se è una funzione iniettiva e , allora .

Comunque per dimostrare quello che vuoi dimostrare non dovrebbe servire l'assioma di scelta.

Il libro sulla teoria degli insiemi mi consigli di leggerlo ancora prima di questo?

Sono libri che vanno in direzioni diverse, ortogonali direi, uno è un libro di analisi, l'altro un libro di teoria degli insiemi. Lo Zorich ha una breve introduzione alla teoria degli insiemi, più che sufficiente per gli scopi dell'analisi. Se invece vuoi studiare la teoria degli insiemi, devi andare su un altro libro. A me l'Enderton è piaciuto molto (almeno per la parte che ho letto, diciamo un 50%), semplice e chiaro.

Puoi leggerli in qualunque ordine, però se vuoi metterti a fare dimostrazioni di teoremi non banali di teoria degli insiemi, probabilmente lo Zorich non ti basta. Cioè, gli assiomi sono quasi tutti lì, ma le tecniche dimostrative sono diverse.

Per curiosità, quello che stai cercando di dimostrare è un esercizio dello Zorich?

[AjeieBrazov]

Addendum a "quindi la funzione non è biettiva ma suriettiva" "e non iniettiva".

[Ianero]

Allora hai sbagliato notazione

E' vero, hai ragione.

Comunque per dimostrare quello che vuoi dimostrare non dovrebbe servire l'assioma di scelta.

Bene, un punto a favore verso il mio tentativo di dimostrazione
C'è qualche errore nel resto?

Per curiosità, quello che stai cercando di dimostrare è un esercizio dello Zorich?

Yes, sezione 2.2.5, esercizio 4.b.

Per la dimostrazione puoi usare la cardinalità?

Che vuoi dire?

[AjeieBrazov]

Se una funzione A->B è biettiva allora gli insiemi A e B hanno la stessa cardinalità (lo stesso numero di elementi).
Purtroppo in matematica discreta la cardinalità è un argomento affrontato dopo la dimostrazione che ho scritto quindi, se vogliamo essere rigorosi, non la possiamo utilizzare perché non ancora definita e dimostrata.
Perché la dimostrazione che ho proposto sia completa dovrei dimostrare anche i punti 1 e 2 (il terzo è una conseguenza dei due). Se ti interessa te la scrivo.