Non esiste funzione suriettiva da A alle parti di A
Teorema: Sia A un insieme. Non esiste alcuna applicazione suriettiva tra $A$ e $P(A)$.
Dimostrazione: Sia $ f: A \mapsto P(A)$ una applicazione suriettiva e consideriamo l'insieme $E = {x \in A: x \notin f(x)}$. Poiché $f$ è suriettiva, esisterà un $e \in A$ tale che $E = f(e)$. Ci chiediamo ora: $e$ appartiene ad $E$ oppure no?
Sfruttando il paradosso di Russell l'autore conclude la dimostrazione. Non ho capito perché definisce $E$ in quel modo. Se fosse definito in un altro modo?
Dimostrazione: Sia $ f: A \mapsto P(A)$ una applicazione suriettiva e consideriamo l'insieme $E = {x \in A: x \notin f(x)}$. Poiché $f$ è suriettiva, esisterà un $e \in A$ tale che $E = f(e)$. Ci chiediamo ora: $e$ appartiene ad $E$ oppure no?
Sfruttando il paradosso di Russell l'autore conclude la dimostrazione. Non ho capito perché definisce $E$ in quel modo. Se fosse definito in un altro modo?
Risposte
Tipo come?
Dato che $E \in P(A)$ non penso che si possa definire. È uno dei sottoinsiemi di $A$, come vengono "generati" questi sottoinsiemi è più una questione di calcolo combinatorio. Ciò che dice il teorema è chiaro, così come è facile capire che se ho 2 libretti e 4 studenti, non posso dare un libretto a ciascuno degli studenti. Il problema è il passo indicato della dimostrazione.
"universo":
Dato che $E \in P(A)$ non penso che si possa definire.
Certo che si può definire, lo hai appena fatto.
come vengono "generati" questi sottoinsiemi è più una questione di calcolo combinatorio
Magari!
La dimostrazione rimane non chiara per me.
Ma cosa c'è che non ti è chiaro?
$P(A)$ è determinato a partire dagli elementi di A. Siccome bisogna dimostrare il teorema per ogni A, perché scegliere proprio $E$ così definito?
"universo":
$P(A)$ è determinato a partire dagli elementi di A. Siccome bisogna dimostrare il teorema per ogni A, perché scegliere proprio $E$ così definito?
Perché per ogni $A$ esiste l'$E$ che riesce a dimostrare che non esiste una suriezione $A \to PA$. E il motivo per cui esiste è che riesci a scriverlo: come disse Homer Simpson, "la teoria degli insiemi è la causa di, e la soluzione a, tutti i miei problemi".
"universo":È una dimostrazione per assurdo. Questo significa che è un argomento che a partire dalla negazione della tesi arriva a un assurdo. Quindi la tesi è vera. Si poteva usare un argomento diverso, sì, ma questo non significa che l'argomento usato non vada bene. Qualsiasi argomento che funziona è una dimostrazione.
$P(A)$ è determinato a partire dagli elementi di A. Siccome bisogna dimostrare il teorema per ogni A, perché scegliere proprio $E$ così definito?
Se proprio non ti piace una dimostrazione per assurdo, prova a dimostrare questo risultato più generale:
Se esiste una suriezione \(S \to \hom(S,V)\) allora ogni funzione $g : V \to V$ ha almeno un punto fisso.
Corollario: non esiste una suriezione $S\to 2^S$ perché \(\lnot : 2\to 2\) non ha punti fissi.
Altrimenti, c'è anche una dimostrazione che invece di far vedere che non esiste una suriezione $S \to 2^S$ mostra che non esiste una iniezione $2^S\to S$ (queste due asserzioni non sono equivalenti).
Se esiste una suriezione \(S \to \hom(S,V)\) allora ogni funzione $g : V \to V$ ha almeno un punto fisso.
Corollario: non esiste una suriezione $S\to 2^S$ perché \(\lnot : 2\to 2\) non ha punti fissi.
Altrimenti, c'è anche una dimostrazione che invece di far vedere che non esiste una suriezione $S \to 2^S$ mostra che non esiste una iniezione $2^S\to S$ (queste due asserzioni non sono equivalenti).
Comunque quella dimostrazione non c'era ragione di scriverla come un assurdo. Infatti quello che stai davvero dimostrando è il seguente:
Teorema: Sia \(A\) un insieme e \(f\colon A\to \mathcal{P}(A)\), allora esiste \(E\in \mathcal{P}(A)\) tale che \(E \notin f(A)\).
L'insieme \(E\) scelto nella dimostrazione da te proposta (e che dipende da \(f\)), è ben posto e soddisfa questa condizione. Infatti, se \(a\in E\) allora \(f(a)\neq E\) perché \(a\notin f(a)\) per la definizione di \(E\). E se \(a\notin E\) allora \(f(a)\neq E\) perché \(a\in f(a)\) per definizione di \(E\).
Teorema: Sia \(A\) un insieme e \(f\colon A\to \mathcal{P}(A)\), allora esiste \(E\in \mathcal{P}(A)\) tale che \(E \notin f(A)\).
L'insieme \(E\) scelto nella dimostrazione da te proposta (e che dipende da \(f\)), è ben posto e soddisfa questa condizione. Infatti, se \(a\in E\) allora \(f(a)\neq E\) perché \(a\notin f(a)\) per la definizione di \(E\). E se \(a\notin E\) allora \(f(a)\neq E\) perché \(a\in f(a)\) per definizione di \(E\).
"Martino":
Si poteva usare un argomento diverso, sì, ma questo non significa che l'argomento usato non vada bene. Qualsiasi argomento che funziona è una dimostrazione.
Penso che il punto importante da capire per l'OP sia questo, ben evidenziato da Martino: se funziona, per quanto astrusa possa essere la dimostrazione, va bene
Qualsiasi argomento che funziona è una dimostrazione.
Questo punto di vista però è perlomeno semplicistico rispetto a un problema che, al di fuori della matematica classica, è piuttosto sentito.
Scusate per il ritardo,per questioni di organizzazione mi sono buttato su Algebra I e ho rimandato la questione.
In ogni caso ho capito cosa non mi era chiaro: se l'esistenza di B fosse sempre possibile. Dovrebbe essere garantita dall'assioma di specificazione. Ad ogni modo basta prendere un qualsiasi $x \in X$ e mandarlo in $\emptyset$ per avere che $x \notin f(x)$ e B esiste sempre.
In ogni caso ho capito cosa non mi era chiaro: se l'esistenza di B fosse sempre possibile. Dovrebbe essere garantita dall'assioma di specificazione. Ad ogni modo basta prendere un qualsiasi $x \in X$ e mandarlo in $\emptyset$ per avere che $x \notin f(x)$ e B esiste sempre.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo