[Risolto] Quesito anti-noia #12: insieme delle parti

La dimostrazione è di G. Cantor, spero di ripeterla senza errori.

Non scrivo i preliminari del caso.

$ f : X → \mathcal{P}(X)$

dimostrare che non è surgettiva. 

Lo si dimostra per assurdo.

Se fosse surgettiva per ogni sottoinsieme S di X esisterebbe un x₀∈X tale che f(x₀) = S.

Scegliamo come sottoinsieme di X l'insieme A così definito (suggerimento)

$A = \{x  \in X \,| \, x \notin  f(x)\}$

cioè l'insieme delle x tali che l'immagine tramite f non contenga l'elemento di partenza.

Essendo f surgettiva deve esistere un elemento x* in X tale che f(x*) = A.

Si possono verificare solo due casi:

i) x*∈A. In questo caso, per come è definito A, x* non può appartenere ad A, x*∉A. Assurdo.

ii) x*∉A. In tal caso, per come è definito A, x*∈A. Assurdo.

Visto che le conclusioni sono assurde allora l'ipotesi di surgettività risulta errata.

Esprimo il concetto in forma grezza e tu lo tradurrai in termini rigorosi. 

L'insieme delle parti é più numeroso di X perché non contiene solo singoletti. 

Per definizione di funzione le immagini di f sono in numero minore o uguale 

della numerosità di X perché a nessun elemento di quest'ultimo corrisponde 

più di una immagine. 

Queste due affermazioni sono in particolare in contraddizione se si richiede

che f sia suriettiva.