Teorema di Cantor, dimostrazione

[Angus1956]

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!

[Angus1956]

"megas_archon":

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.

[4131]

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

Perché?

"andreadel1988": supponiamo per assurdo che [tex]\color{red}S\subseteq f(X)[/tex],

[*:4r1mgyvo]In una dimostrazione per assurdo devi negare la tesi, quindi supponiamo per assurdo che...[/*:m:4r1mgyvo]
[*:4r1mgyvo]Se [tex]X=\{1,2,3\}[/tex] allora [tex]\mathcal{P}(X)=\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},X\}[/tex]. Preso [tex]S\subseteq X[/tex], ha senso scrivere [tex]S\subseteq\mathcal{P}(X)[/tex]?[/*:m:4r1mgyvo][/list:u:4r1mgyvo]


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


Perché?


"andreadel1988":
Ora se $x inS$ si avrebbe che [tex]x \in f(x)[/tex] 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 [tex]x\in S[/tex] oppure [tex]x\not\in S[/tex]:


[*:4r1mgyvo] se [tex]x\in S[/tex], allora [tex]x\not\in f(x)[/tex], ma [tex]f(x) = S[/tex], quindi contemporaneamente si ha [tex]x\in S[/tex] e [tex]x\not\in S[/tex], che è una contraddizione;[/*:m:4r1mgyvo]
[*:4r1mgyvo] se [tex]x\not\in S[/tex], allora [tex]x\in f(x)[/tex], ma [tex]f(x)=S[/tex], quindi contemporaneamente si ha [tex]x\in S[/tex] e [tex]x\not\in S[/tex], che è di nuovo una contraddizione.[/*:m:4r1mgyvo][/list:u:4r1mgyvo]


"andreadel1988":
Per cui tale [tex]\color{red}x[/tex] non può esistere e dunque [tex]\color{red}S\not\subseteq f(X)[/tex] e quindi [tex]\color{red}[/tex] non è suriettiva.


In ogni caso raggiungi una contraddizione, quindi...