Teorema di Cantor, dimostrazione

[andreadel1988]

Sia $X$ un insieme e sia $P(X)$ l’insieme delle parti di $X$, cioè l’insieme i cui elementi sono tutti e soli i sottoinsiemi di $X$. Se $f:X->P(X)$ è una funzione, allora si provi che $f$ non è suriettiva.

Per dimostrarlo ho pensato di fare così:
Consideriamo l'insieme $S={x inX|xnotinf(x)}inP(X)$, supponiamo per assurdo che $Ssubef(X)$, quindi $EEx inX$ tale che $f(x)=S$. Ora se $x inS$ si avrebbe che $x inf(x)$ il che assurdo poichè siccome $x inS$ si dovrebbe avere $xnotinf(x)$, mentre se $xnotinS$ allora $xnotinf(x)$ e quindi per definizione di $S$ si avrebbe $x inS$ assurdo. Per cui tale $x$ non può esistere e dunque $Snotsubef(X)$ e quindi $f$ non è suriettiva, va bene?

[megas_archon]

Per dimostrarlo ho pensato di fare così:

Sì, va essenzialmente bene, ma l'idea di dimostrarlo così non è venuta a te!

[andreadel1988]

Per dimostrarlo ho pensato di fare così:

Sì, va essenzialmente bene, ma l'idea di dimostrarlo così non è venuta a te!

No intendevo dire come l'avrei dimostrata io, non che l'ho dimostrata io, haahhaha.

[413]

Consideriamo l'insieme $S={x inX|xnotinf(x)}inP(X)$,

Perché?

supponiamo per assurdo che \( \displaystyle \color{red}S\subseteq f(X) \) ,

• In una dimostrazione per assurdo devi negare la tesi, quindi supponiamo per assurdo che...
• Se \( \displaystyle X=\{1,2,3\} \) allora \( \displaystyle \mathcal{P}(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\} \) . Preso \( \displaystyle S\subseteq X \) , ha senso scrivere \( \displaystyle S\subseteq\mathcal{P}(X) \) ?

quindi $EEx inX$ tale che $f(x)=S$.

Perché?

Ora se $x inS$ si avrebbe che \( \displaystyle x \in f(x) \) il che assurdo poichè siccome $x inS$ si dovrebbe avere $xnotinf(x)$, mentre se $xnotinS$ allora $xnotinf(x)$ e quindi per definizione di $S$ si avrebbe $x inS$ assurdo.

Un po' ingarbugliato... ci sono due possibilità, o \( \displaystyle x\in S \) oppure \( \displaystyle x\not\in S \) :

• se \( \displaystyle x\in S \) , allora \( \displaystyle x\not\in f(x) \) , ma \( \displaystyle f(x) = S \) , quindi contemporaneamente si ha \( \displaystyle x\in S \) e \( \displaystyle x\not\in S \) , che è una contraddizione;
• se \( \displaystyle x\not\in S \) , allora \( \displaystyle x\in f(x) \) , ma \( \displaystyle f(x)=S \) , quindi contemporaneamente si ha \( \displaystyle x\in S \) e \( \displaystyle x\not\in S \) , che è di nuovo una contraddizione.

Per cui tale \( \displaystyle \color{red}x \) non può esistere e dunque \( \displaystyle \color{red}S\not\subseteq f(X) \) e quindi \( \displaystyle \color{red} \) non è suriettiva.

In ogni caso raggiungi una contraddizione, quindi...