Teorema di Cantor... non capisco la dimostrazione!!!
Ciao a tutti...
qualcuno potrebbe spiegarmi bene bene, a parole, la dimostrazione del teorema di Cantor che dimostra che non esiste una funzione suriettiva da X a parti di X, ovvero che l'insieme delle parti di un insieme ha sempre cardinalità maggiore di quella dell'insieme stesso??
Non riesco proprio a capirla...
Grazie mille!
qualcuno potrebbe spiegarmi bene bene, a parole, la dimostrazione del teorema di Cantor che dimostra che non esiste una funzione suriettiva da X a parti di X, ovvero che l'insieme delle parti di un insieme ha sempre cardinalità maggiore di quella dell'insieme stesso??
Non riesco proprio a capirla...
Grazie mille!
Risposte
Ciao. Provo a spiegare.
Se l'insieme $X$ è formato da un numero finito di elementi, $card(X)=n$, $card(P(X))=2^n$, da cui la tesi è evidente.
La parte più difficile è la dimostrazione nel caso in cui $X$ ha infiniti elementi. In questo caso si suppone per assurdo che esista una funzione suriettiva $f$ da $X$ a $P(X)$.
Si definisce l'insieme $A$ di tutti gli elementi di $X$ che non sono contenuti nella propria immagine. Ad esempio, se $X$ è l'insieme dei numeri naturali, e se fosse:
$f(1)={2, 3, 5}$ si ha che $1notinf(1)$
$f(2)={1, 2, 5, 23}$ si ha che $2in f(2)$
L'insieme $A$ è sicuramente non vuoto, poichè, dato che la funzione è suriettiva, esiste $x inA$ tale che $f(x)=i nsiemevuot o$, e certamente $x notin f(x)$. Allora $x inA$, per la definizione stessa di $A$.
L'insieme $A$ è un sottoinsieme di $X$, quindi $AinP(X)$. Sempre per il fatto che la $f$ è suriettiva, esiste sicuramente un $y in A$ tale che $f(y)=A$.
Se $y in A$, $y$ è contenuto nella propria immagine, quindi dovrebbe essere $y notin A$, data la definzione di $A$. (contraddizione)
Se invece $y notin A$, $y$ non è contenuto nella propria immagine, quindi dovrebbe essere $y in A$, data la definizione di $A$. (contraddizione)
L'esistenza di questo $y$ porta inevitabilmente a contraddizioni. Allora $y$ non può esistere. L'insieme $A$ non è immagine di nessun elemento di $X$, nonostante $A in P(X)$. Questo significa che $f$ non è suriettiva.
Se l'insieme $X$ è formato da un numero finito di elementi, $card(X)=n$, $card(P(X))=2^n$, da cui la tesi è evidente.
La parte più difficile è la dimostrazione nel caso in cui $X$ ha infiniti elementi. In questo caso si suppone per assurdo che esista una funzione suriettiva $f$ da $X$ a $P(X)$.
Si definisce l'insieme $A$ di tutti gli elementi di $X$ che non sono contenuti nella propria immagine. Ad esempio, se $X$ è l'insieme dei numeri naturali, e se fosse:
$f(1)={2, 3, 5}$ si ha che $1notinf(1)$
$f(2)={1, 2, 5, 23}$ si ha che $2in f(2)$
L'insieme $A$ è sicuramente non vuoto, poichè, dato che la funzione è suriettiva, esiste $x inA$ tale che $f(x)=i nsiemevuot o$, e certamente $x notin f(x)$. Allora $x inA$, per la definizione stessa di $A$.
L'insieme $A$ è un sottoinsieme di $X$, quindi $AinP(X)$. Sempre per il fatto che la $f$ è suriettiva, esiste sicuramente un $y in A$ tale che $f(y)=A$.
Se $y in A$, $y$ è contenuto nella propria immagine, quindi dovrebbe essere $y notin A$, data la definzione di $A$. (contraddizione)
Se invece $y notin A$, $y$ non è contenuto nella propria immagine, quindi dovrebbe essere $y in A$, data la definizione di $A$. (contraddizione)
L'esistenza di questo $y$ porta inevitabilmente a contraddizioni. Allora $y$ non può esistere. L'insieme $A$ non è immagine di nessun elemento di $X$, nonostante $A in P(X)$. Questo significa che $f$ non è suriettiva.
Ciao, volevo ringraziarti per la tua spiegazione perfetta!
In molti siti si trova la stessa dimostrazione lacunosa (tipo wikipedia) e poco chiara.
Secondo me dovresti correggerla anche lì.
Grazie, ciao
In molti siti si trova la stessa dimostrazione lacunosa (tipo wikipedia) e poco chiara.
Secondo me dovresti correggerla anche lì.
Grazie, ciao
"charliebrown":Ho sistemato l'articolo di wikipedia, prova a vedere se adesso è chiaro.
correggerla anche lì.
Francamente, secondo me ancora no.
Personalmente mi bloccavo su due punti: il primo era nella definizione dell'insieme "di tutti gli elementi di $X$ che non sono contenuti nella propria immagine" (da robbstark chiamato $A$ e su wikipedia chiamato $B$). L'esempio di robbstark chiarisce cosa significa che $x \in f(x)$. Non riuscivo a focalizzare che "$f(x)$" era un generico sottoinsieme di $X$ e continuavo a vederlo come l'insieme formato da un unico elemento (mea culpa!).
Il secondo punto importante è la spiegazione del fatto che l'insieme $A$ sia necessariamente non vuoto.
Grazie, ciao
Personalmente mi bloccavo su due punti: il primo era nella definizione dell'insieme "di tutti gli elementi di $X$ che non sono contenuti nella propria immagine" (da robbstark chiamato $A$ e su wikipedia chiamato $B$). L'esempio di robbstark chiarisce cosa significa che $x \in f(x)$. Non riuscivo a focalizzare che "$f(x)$" era un generico sottoinsieme di $X$ e continuavo a vederlo come l'insieme formato da un unico elemento (mea culpa!).
Il secondo punto importante è la spiegazione del fatto che l'insieme $A$ sia necessariamente non vuoto.
Grazie, ciao
"charliebrown":Quindi non ti è ancora chiara la dimostrazione in wikipedia? Mi spiegheresti perché?
Francamente, secondo me ancora no.
Personalmente mi bloccavo su due punti: il primo era nella definizione dell'insieme "di tutti gli elementi di $X$ che non sono contenuti nella propria immagine" (da robbstark chiamato $A$ e su wikipedia chiamato $B$). L'esempio di robbstark chiarisce cosa significa che $x \in f(x)$. Non riuscivo a focalizzare che "$f(x)$" era un generico sottoinsieme di $X$ e continuavo a vederlo come l'insieme formato da un unico elemento (mea culpa!).
Il secondo punto importante è la spiegazione del fatto che l'insieme $A$ sia necessariamente non vuoto.
Grazie, ciao
Inoltre non capisco perché dici che $A$ dev'essere non vuoto: $A$ può essere anche vuoto, la dimostrazione funziona in ogni caso. Anche $B$ può benissimo essere vuoto (mi riferisco agli $A$ e $B$ della dimostrazione di wikipedia).
"robbstark":Il fatto che $A$ sia non vuoto non serve.
L'insieme $A$ è sicuramente non vuoto, poichè, dato che la funzione è suriettiva, esiste $x inA$ tale che $f(x)=i nsiemevuot o$, e certamente $x notin f(x)$. Allora $x inA$, per la definizione stessa di $A$.
Hai ragione, effettivamente ora mi è chiara, ero vittima di una prima dimostrazione che induceva a pensare una cosa errata introducendo un'ulteriore funzione e non riuscivo a liberarmi da quell'idea (e come me le altre persone che studiavano con me... probabilmente ci stavamo male influenzando a vicenda).
Continuo comunque a pensare che la spiegazione di robbstark sia ancora più esauriente in quanto con il suo esempio elimina tutti i possibili equivoci venutisi a creare in testa.
Personalmente nella dimostrazione di wikipedia credo mi avrebbe aiutato sostituire la frase "A tal fine è sufficiente individuare un sottoinsieme di $A$..." con la frase "A tal fine è sufficiente individuare un elemento di $P(A)$, ovvero un sottoinsieme di $A$, ...", perché continuavo a pensare che si stesse cercando di individuare un sottoinsieme del dominio, anziché un elemento del codominio. Ma ho capito che è stato un problema tutto personale
Grazie per il tuo interessamento, ciao.
Continuo comunque a pensare che la spiegazione di robbstark sia ancora più esauriente in quanto con il suo esempio elimina tutti i possibili equivoci venutisi a creare in testa.
Personalmente nella dimostrazione di wikipedia credo mi avrebbe aiutato sostituire la frase "A tal fine è sufficiente individuare un sottoinsieme di $A$..." con la frase "A tal fine è sufficiente individuare un elemento di $P(A)$, ovvero un sottoinsieme di $A$, ...", perché continuavo a pensare che si stesse cercando di individuare un sottoinsieme del dominio, anziché un elemento del codominio. Ma ho capito che è stato un problema tutto personale
Grazie per il tuo interessamento, ciao.
Ho sistemato l'articolo wiki come hai detto.
Ehi, troppa importanza, grazie!
"charliebrown":Perché? In effetti avevi ragione, non era scritto troppo bene.
Ehi, troppa importanza, grazie!
Comunque il fatto che B del teorema di cantor esiste, è perchè la sua definizione è consistente con le ipotesi(è lecita), e solo per questo motivo, poichè poi, successivamente, se ne dimostra la contradditorietà, allora non è lecita l'assunzione di suriettività della funzione.
Scusate se mi intrometto nella discussione...la dimostrazione mi è chiara e tutto ho solo un piccolo dubbio: potreste spiegarmi la scrittura $ (2)^(n) $ circa la cardinalità di un insieme? Perchè ho una mezza idea, ma molto confusa e imprecisa... se poteste aiutarmi ve ne sarei grato =)
Se ti riferisci a quel che ho scritto io è semplicemente un numero.
Ad esempio: $X={1, 2, 3}$ ha cardinalità $3$, $P(X)$ ha cardinalità $2^3$ cioè $8$.
Ad esempio: $X={1, 2, 3}$ ha cardinalità $3$, $P(X)$ ha cardinalità $2^3$ cioè $8$.
Rappresenta la cardinalità, espressa dalla potenza come ti indica robbstark, dell'insieme delle parti di un insieme che ha cardinalità finita. E non è un fatto scontato deve dimostrarsi. Parti dal fatto che un insieme che ha cardinalità $1$ ha certamente un insieme delle parti di cardinalità $2^1$, quindi la proprietà, che voglio dimostrare valida per ogni intero $n$, è vera quando $n=1$, ergo l'insieme degli interi per cui vale contiene $1$, adesso devi poter dimostrare che se contiene $m$ allora contiene $m+1$, cioè se assumi che valga per $m$ per cui la cardinalità sarà quindi espressa da $2^m$, allora vale per $m+1$ per cui la cardinalità sarà espressa da $2^(m+1)$. Per dimostrarlo devi considerare che, data l'ipotesi induttiva, cioè se è vera la proprietà per $m$ allora la cardinalità è $2^m$, considerando ora l'aggiunta di un elemento distinto dai precedenti(osservazione superflua?), l'insieme conterrà $m+1$ elementi(per inciso non esiste nessun altro intero tra $m$ e $m+1$), il nuovo insieme delle parti potrà formarsi allora semplicemente considerando quell'oggetto facente parte o meno di ogni elemento dell'insieme delle parti precedente, quindi per ognuno di questi se ne avranno due, il che significa moltiplicare per 2 la precedente cardinalità.
grazie mille per l'aiuto 
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo