Dubbi sul teorema di cantor sugli insiemi
Ho appena cominciato analisi e non ho ben capito il significato di alcune parti della dimostrazione del Teorema di Cantor:
non esiste nessuna f surgettiva che porta da S a P(S) (insieme dei sottoinsiemi).
In particolere riprendo quella scritta da 'fields' sul forum:
Supponiamo per assurdo esista un biettività f fra S e Parti(S). Sia C l'insieme degli x∈S tali che x non appartiene a f(x). Allora esiste a∈S tale che f(a)=C. Ora se a non appartiene a C=f(a), allora per definizione a appartiene a C, assurdo. Se invece a appartiene a C=f(a), allora per definizione a non appartiene a C, assurdo.
Ora: f(x) se è immagine di S, appartiene a S perchè è sottoinsieme o perchè per assurdo si prende che f(x) è uguale a S?
In secondo luogo non capisco perchè prendo un altro insieme C se avevmo detto che c'è una surgettiva, e quindi se prendo un altro insieme C non lo dovrebbe più essere..
L'f(a) si riferisce sempre alla funzione surgettiva f:S-->P(S) di partenza o no?
In che modo consegue logicamente il fatto che se a non appartiene a C=f(a), allora per definiz. a appartiene a C?
Infine non capisco dove si tiene conto, in tutto questo, dell'insieme dei sottoinsiemi di S.
Scusate le numerose domande, ma non ci ho capito molto...
Grazie a chi mi vorrà rispondere..
non esiste nessuna f surgettiva che porta da S a P(S) (insieme dei sottoinsiemi).
In particolere riprendo quella scritta da 'fields' sul forum:
Supponiamo per assurdo esista un biettività f fra S e Parti(S). Sia C l'insieme degli x∈S tali che x non appartiene a f(x). Allora esiste a∈S tale che f(a)=C. Ora se a non appartiene a C=f(a), allora per definizione a appartiene a C, assurdo. Se invece a appartiene a C=f(a), allora per definizione a non appartiene a C, assurdo.
Ora: f(x) se è immagine di S, appartiene a S perchè è sottoinsieme o perchè per assurdo si prende che f(x) è uguale a S?
In secondo luogo non capisco perchè prendo un altro insieme C se avevmo detto che c'è una surgettiva, e quindi se prendo un altro insieme C non lo dovrebbe più essere..
L'f(a) si riferisce sempre alla funzione surgettiva f:S-->P(S) di partenza o no?
In che modo consegue logicamente il fatto che se a non appartiene a C=f(a), allora per definiz. a appartiene a C?
Infine non capisco dove si tiene conto, in tutto questo, dell'insieme dei sottoinsiemi di S.
Scusate le numerose domande, ma non ci ho capito molto...
Grazie a chi mi vorrà rispondere..
Risposte
Teorema: la cardinalità di $P(A)$ è maggiore della cardinalità di $A$.
Dimostrazione. Che la cardinalità di $P(A)$ sia maggiore o uguale a quella di $A$ è ovvio. Non resta che provare che l'uguaglianza non può valere.
Per assurdo, sia $f:A\to P(A)$ biunivoca. Sia $x\in A$; allora $f(x)\in P(A)$, quindi $f(x)$ è un sottoinsieme di $A$: $f(x)\subset A$.
Consideriamo l'insieme (è un po' strano!) ${x\in A | x\notin f(x)}$. Questo insieme è sicuramente un sottoinsieme di $A$. Dal momento che $f$ è (in particolare) suriettiva, esso dovrà "provenire" da un elemento $x_0$ di $A$. In altre parole, esiste $x_0\in A$ tale che $f(x_0)={x\in A | x\notin f(x)}$.
Ne segue: $x\in f(x_0)$ se e solo se $x\notin f(x)$.
Ponendo $x=x_0$ si ha l'assurdo.
Si tratta di una dimostrazione semplice, ma anche molto elegante.
Dimostrazione. Che la cardinalità di $P(A)$ sia maggiore o uguale a quella di $A$ è ovvio. Non resta che provare che l'uguaglianza non può valere.
Per assurdo, sia $f:A\to P(A)$ biunivoca. Sia $x\in A$; allora $f(x)\in P(A)$, quindi $f(x)$ è un sottoinsieme di $A$: $f(x)\subset A$.
Consideriamo l'insieme (è un po' strano!) ${x\in A | x\notin f(x)}$. Questo insieme è sicuramente un sottoinsieme di $A$. Dal momento che $f$ è (in particolare) suriettiva, esso dovrà "provenire" da un elemento $x_0$ di $A$. In altre parole, esiste $x_0\in A$ tale che $f(x_0)={x\in A | x\notin f(x)}$.
Ne segue: $x\in f(x_0)$ se e solo se $x\notin f(x)$.
Ponendo $x=x_0$ si ha l'assurdo.
Si tratta di una dimostrazione semplice, ma anche molto elegante.
"Lorenzo Pantieri":
Che la cardinalità di $P(A)$ sia maggiore o uguale a quella di $A$ è ovvio. Non resta che provare che l'uguaglianza non può valere.
Posso chiedere perchè?
"WiZaRd":
[quote="Lorenzo Pantieri"]
Che la cardinalità di $P(A)$ sia maggiore o uguale a quella di $A$ è ovvio. Non resta che provare che l'uguaglianza non può valere.
Posso chiedere perchè?[/quote]
Facile: l'insieme delle parti contiene in particolare tutti i singoletti ${x}$ dove $x$ sta in $A$. La funzione $g: A\to P(A)$, $g(x)={x}$, è manifestamente iniettiva. In altre parole, $P(A)$ contiene un sottoinsieme che è in corrispondenza biunivoca con $A$, quindi la sua cardinalità non può essere inferiore ad $A$.
Giustissimo.
Grazie per la cortese spiegazione.
Grazie per la cortese spiegazione.
Grazie per la spiegazione . Quindi l'assurdo sarebbe nel dire che f è suriettiva e poi dire che c'è un elemento esterno alla f che dovrebbe comunque stare all'interno di f per definizione? (scusa per il linguaggio astruso)
Correggimi se sbaglio e grazie ancora. Quindi P(A) non è in corrispondenza biunivoca perchè esiste sempre almeno un elemento di P(A) non contenuto in A, giusto?
. Quindi l'assurdo sarebbe nel dire che f è suriettiva e poi dire che c'è un elemento esterno alla f che dovrebbe comunque stare all'interno di f per definizione? (scusa per il linguaggio astruso)Correggimi se sbaglio e grazie ancora. Quindi P(A) non è in corrispondenza biunivoca perchè esiste sempre almeno un elemento di P(A) non contenuto in A, giusto?
"tonyzz":
Grazie per la spiegazione
Il tuo linguaggio è troppo impreciso, sorry.
L'assurdo sta, nelle notazioni di prima, nel concludere che $x_0\in f(x_0)$ se e solo se $x_0\notin f(x_0$)$.
"tonyzz":
Correggimi se sbaglio e grazie ancora. Quindi P(A) non è in corrispondenza biunivoca perchè esiste sempre almeno un elemento di P(A) non contenuto in A, giusto?
No, non è esatto: tutti gli elementi di $P(A)$ sono sottoinsiemi di $A$. Il fatto è che questi sottoinsiemi sono di più degli elementi di $A$.
Sì scusa, mi sono spiegato male ma è quello che intendevo dire.
Penso di aver capito allora, nella spiegazione mi ero perso quel prendere f(xo)=f(x) e non riuscivo a capacitarmi dell'assurdo
Penso di aver capito allora, nella spiegazione mi ero perso quel prendere f(xo)=f(x) e non riuscivo a capacitarmi dell'assurdo
"tonyzz":
Sì scusa, mi sono spiegato male ma è quello che intendevo dire.
Penso di aver capito allora, nella spiegazione mi ero perso quel prendere f(xo)=f(x) e non riuscivo a capacitarmi dell'assurdo
Faccio un piccolo commento "didattico". Nella "mia" dimostrazione del teorema di Cantor avevo (consapevolmente!) lasciato due piccolissimi vuoti da colmare:
1. il fatto che l'insieme delle parti ha un numero di elementi non inferiore ad $A$;
2. l'assurdo finale.
Le due richieste di chiarimento confermano (se ce ne fosse bisogno) l'importanza della chiarezza e della completezza espositiva: quando si spiegano (e si appredono!) le cose, in matematica, non si è mai troppo precisi né troppo attenti ai dettagli.
Un saluto a tutti.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo