Teorema di Cantor (teoria degli insiemi)

[pop_dirac]

Ciao a tutti,
ho da poco iniziato il corso di Analisi 1 e mi trovo già bloccato ad un passaggio di uno dei primi teoremi che abbiamo affrontato: il teorema che afferma che, preso un insieme X, l'insieme delle parti di X, p(X), ha cardinalità maggiore. (Abbiamo poi dimostrato anche il noto fatto che la cardinalità di p(X) è $2^n$, con n pari al numero degli elementi di X).

$card(x)<=card[p(x)]$

Dimostrazione per assurdo:
Se $card(x)>=card[p(x)]$ allora $EE y: X -> p(X)$ surgettiva
Sia $ F = {x in X: x !in y(x)} $ (*)
$ F sub X => EE ainX: F = y(a) $ (**)

1) se $ainF => a!iny(a)=F => a!inF$
2) se $a!inF => ainy(a)=F => ainF$

che è assurdo in entrambi i casi.

In particolare, non capisco il punto (*): forse ho sbagliato a scrivere? Che significa che $x!iny(x)$? Ciò non contraddirebbe il fatto che y sia una funzione definita in quel dominio?
Allo stesso modo, non riesco a interpretare il punto (**), ossia cosa $FsubX$ implichi (e perché).


Vi ringrazio in anticipo e scusate la banalità della domanda

PS: forse a questo punto ho sbagliato a scrivere negli appunti la dimostrazione... ma non la trovo su internet fatta in questo modo. Settimana prossima comunque proverò ad andare a ricevimento.

[solaàl]

Tutti hanno questi problemi all'inizio, perché pensano che gli insiemi siano punti dentro i quali non si può guardare. Questo è falso.

Qui \(y(x)\) è un sottoinsieme di \(X\), i cui elementi sono quindi elementi di \(X\), e quindi per ogni \(x\in X\) e ogni funzione \(y : X \to PX\) ha senso formare ("evocare": perché gli insiemi sono formule magiche in un grimorio, e chi li chiama è un po' uno stregone) l'insieme \(F_y=F\) i cui elementi sono tutti gli \(x\in X\) che soddisfano la proprietà \(x\notin y(x)\).

Sorpresa: qualsiasi sia \(y\), si scopre che \(F_y\) non può stare nella sua immagine, quindi non esiste nessuna suriezione da \(X\) a \(PX\).

[84f45e194ee50365c2aa8ead271e4a9d9bb017bb]

"pop_dirac":
Sia $ F = {x in X: x !in y(x)} $ (*)

Hai che \( y \) è una funzione, se ti disturba la lettera \(y\) chiamala pure \(f\). Ed è suriettiva per ipotesi poiché stai supponendo per assurdo che esiste una suriezione tra \(X \) e \( \mathcal{P}(X)\). Quindi per ipotesi esiste almeno una funzione \(y\) suriettiva da \(X\) a \(\mathcal{P}(X)\). Per quanto riguarda \(y(x) \) è l'immagine di \(x \) tramite la funzione \(y\). Cos'è l'immagine di un elemento \(x\) tramite \(y\)? È semplicemente un elemento di \( \mathcal{P}(X)\) o in altre parole è un sottoinsieme di \(X\). Infatti l'insieme delle parti di \(X\) è formato dalla collezione dei sottoinsiemi di \(X\). Pertanto \( y(x) \subseteq X \). Quindi puoi domandarti se prendo un elemento \(x \in X \) esso apparterrà anche a \(y(x) \) ?
Costruisci così l'insieme \(F\) che è costituito da tutti quegli elementi \(x \in X \) tale che non sono elemento della loro immagine tramite \(y\).

"pop_dirac":
$ F sub X => EE ainX: F = y(a) $ (**)

Chiaramente \(F\) è un sottoinsieme di \(X\) poiché è formato da elementi in \(X\), quindi è un elemento di \( \mathcal{P}(X) \), pertanto siccome \(y\) è suriettiva deve esistere per definizione di suriezione un elemento \(a \in X \) tale che \( y(a)=F\).

[pop_dirac]

Vi ringrazio entrambi! Sono riuscito finalmente a capire, a ricevimento.

Chiaramente \(F\) è un sottoinsieme di \(X\) poiché è formato da elementi in \(X\), quindi è un elemento di \( \mathcal{P}(X) \), pertanto siccome \(y\) è suriettiva deve esistere per definizione di suriezione un elemento \(a \in X \) tale che \( y(a)=F\).

Era esattamente questo il passaggio che mi mancava! Il professore non era stato esplicito (in effetti era banale) sul fatto che dato che \(F\) è sottoinsieme di \(X\) allora esso è anche un sottoinsieme di \(p(X)\) e posso scrivere quella relazione.