Cos'è ElectroYou | Login Iscriviti

ElectroYou - la comunità dei professionisti del mondo elettrico

Ricerca personalizzata

Dimostrare che un insieme è finito

Analisi, geometria, algebra, topologia...

Moderatori: Foto UtenteDirtyDeeds, Foto UtentePietroBaima, Foto UtenteIanero

0
voti

[11] Re: Dimostrare che un insieme è finito

Messaggioda Foto Utentefairyvilje » 4 set 2017, 10:03

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.
"640K ought to be enough for anybody" Bill Gates (?) 1981
Qualcosa non ha funzionato...

Lo sapete che l'arroganza in informatica si misura in nanodijkstra? :D
Avatar utente
Foto Utentefairyvilje
8.257 4 9 12
Master EY
Master EY
 
Messaggi: 2033
Iscritto il: 24 gen 2012, 18:23

0
voti

[12] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteIanero » 4 set 2017, 14:31

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 E_n=\begin{Bmatrix}
1,2,...n
\end{Bmatrix} 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 g:A\rightarrow B è una funzione iniettiva, allora g(A'\subset A)=B'\subset B.

Dimostrazione:

poiché A'\subset A allora per tutti gli a che appartengono ad A e non ad A', g(a) \in B, ma g(a)\notin B' a causa dell'iniettività di g.
Per cui B'\subset B.



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 E_n=\begin{Bmatrix}
1,2,...n
\end{Bmatrix} per qualsiasi n.

Per assurdo sia A Dedekind-infinito e A finito, ovvero A in corrispondenza biunivoca con un suo sottoinsieme proprio (tramite f) e A in corrispondenza biunivoca con un E_n=\begin{Bmatrix}
1,2,...n
\end{Bmatrix}, per qualche n naturale (tramite g).



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

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



A questo punto posso riapplicare f ad A', ottenendo A''.
A'' è un sottoinsieme proprio di A' per il Lemma 1.
Sempre per il Lemma 1 A'' è in corrispondenza biunivoca (tramite una restrizione di g) nel caso peggiore con E_{n-2}.



Posso ripetere questo discorso nel caso peggiore n volte arrivando a dire che A^{n}, che è in corrispondenza biunivoca con A (tramite f), è anche in corrispondenza biunivoca con \phi (tramite g).

Assurdo.

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

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ò.
Avatar utente
Foto UtenteIanero
5.405 5 8 13
Master
Master
 
Messaggi: 2714
Iscritto il: 21 mar 2012, 14:47

3
voti

[13] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteDirtyDeeds » 4 set 2017, 19:40

Ianero ha scritto:Lemma 1:
Se g:A\rightarrow B è una funzione iniettiva, allora g(A'\subset A)=B'\subset B.


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 ;-)
It's a sin to write sin instead of \sin (Anonimo).
...'cos you know that cos ain't \cos, right?
You won't get a sexy tan if you write tan in lieu of \tan.
Take a log for a fireplace, but don't take log for \logarithm.
Avatar utente
Foto UtenteDirtyDeeds
54,8k 7 11 13
G.Master EY
G.Master EY
 
Messaggi: 7006
Iscritto il: 13 apr 2010, 15:13
Località: Somewhere in nowhere

0
voti

[14] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteDirtyDeeds » 4 set 2017, 19:59

Visto che sembra interessarti la teoria degli insiemi, in questo messaggio ti avevo consigliato un libro, quello di Enderton, te lo consiglio ancora ;-)
It's a sin to write sin instead of \sin (Anonimo).
...'cos you know that cos ain't \cos, right?
You won't get a sexy tan if you write tan in lieu of \tan.
Take a log for a fireplace, but don't take log for \logarithm.
Avatar utente
Foto UtenteDirtyDeeds
54,8k 7 11 13
G.Master EY
G.Master EY
 
Messaggi: 7006
Iscritto il: 13 apr 2010, 15:13
Località: Somewhere in nowhere

0
voti

[15] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteIanero » 4 set 2017, 20:21

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?
Avatar utente
Foto UtenteIanero
5.405 5 8 13
Master
Master
 
Messaggi: 2714
Iscritto il: 21 mar 2012, 14:47

0
voti

[16] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteAjeieBrazov » 4 set 2017, 20:34

Per la dimostrazione puoi usare la cardinalità?

Edit: provo una dimostrazione, anche se mi sembra troppo semplice :?
Sia f:A\rightarrow B e
1) f è iniettiva \Leftrightarrow \forall b\in B f^{-1}(b) se contiene al massimo un elemento
2) f è suriettiva \Leftrightarrow \forall b\in B f^{-1}(b) contiene almeno un elemento
3) f è biettiva \Leftrightarrow \forall b\in B f^{-1}(b) contiene uno ed un solo elemento.
Quindi, per la definizione stessa di funzione biettiva se (B\subset A) e A\cap B\neq \varnothing allora \exists a \in (B\cap A) tale che f(a) \notin B, quindi la funzione non è biettiva ma suriettiva.
Forse servono anche le dimostrazioni di (1) e (2)?
Ultima modifica di Foto UtenteAjeieBrazov il 4 set 2017, 21:21, modificato 3 volte in totale.
Avatar utente
Foto UtenteAjeieBrazov
895 3 7
---
 
Messaggi: 392
Iscritto il: 23 mag 2017, 20:53

2
voti

[17] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteDirtyDeeds » 4 set 2017, 20:47

Ianero ha scritto: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 B hai prima indicato il codominio della funzione e poi l'immagine di A. Quello che volevi dimostrare, allora, dovrebbe essere questo:

Se g:X\rightarrow Y è una funzione iniettiva e A\subset B\subset X, allora g(A)\subset g(B).

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

Ianero ha scritto: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?
It's a sin to write sin instead of \sin (Anonimo).
...'cos you know that cos ain't \cos, right?
You won't get a sexy tan if you write tan in lieu of \tan.
Take a log for a fireplace, but don't take log for \logarithm.
Avatar utente
Foto UtenteDirtyDeeds
54,8k 7 11 13
G.Master EY
G.Master EY
 
Messaggi: 7006
Iscritto il: 13 apr 2010, 15:13
Località: Somewhere in nowhere

0
voti

[18] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteAjeieBrazov » 4 set 2017, 21:56

Addendum a "quindi la funzione non è biettiva ma suriettiva" "e non iniettiva".
Avatar utente
Foto UtenteAjeieBrazov
895 3 7
---
 
Messaggi: 392
Iscritto il: 23 mag 2017, 20:53

0
voti

[19] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteIanero » 4 set 2017, 23:27

DirtyDeeds ha scritto: 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 :mrgreen:
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.


AjeleBrazov ha scritto: Per la dimostrazione puoi usare la cardinalità?


Che vuoi dire?
Avatar utente
Foto UtenteIanero
5.405 5 8 13
Master
Master
 
Messaggi: 2714
Iscritto il: 21 mar 2012, 14:47

0
voti

[20] Re: Dimostrare che un insieme è finito

Messaggioda Foto UtenteAjeieBrazov » 4 set 2017, 23:32

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.
Avatar utente
Foto UtenteAjeieBrazov
895 3 7
---
 
Messaggi: 392
Iscritto il: 23 mag 2017, 20:53

PrecedenteProssimo

Torna a Matematica generale

Chi c’è in linea

Visitano il forum: Nessuno e 5 ospiti