Dubbi sul teorema di cantor sugli insiemi

[tonyzz]

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

[Lorenzo Pantieri]

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.

[G.D.]

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è?

[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è?

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

[G.D.]

Giustissimo.

Grazie per la cortese spiegazione.

[tonyzz]

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?

[Lorenzo Pantieri]

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)

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

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

[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

[Lorenzo Pantieri]

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.