applicazioni(insiemistica)

[angus89]

Se $S$ è un insieme qualunque, dimostrare che è impossibile trovare un'applicazione di $S$ su $S^"*"$

Precisazioni:
"Applicazione su" vuol dire "applicazione surgettiva", quindi bisogna dimostrare che non esistono applicazioni surgettive da $S$ in $S^"*"$

$S^"*"$ è l'insieme i cui elementi sono tutti i sottoinsiemi di $S$


Bè la mia soluzione si ferma al caso $#S< \infty$, ovvero il caso in cui la cardinalità di $S$ è finita.
In tal caso basta osservare che $#S=n \Rightarrow #S^"*"=2^n$ e dunque $#S^"*">#S$ e qunque il codominio è più grande del dominio e pertanto non è possibile definire un'applicazione surgettiva.

Il problema è dimostrare la proposizione nel caso $#S=\infty$

[Chevtchenko]

http://it.wikipedia.org/wiki/Teorema_di_Cantor

[angus89]

Ad esser sincero la dimostrazione del teorema di Cantor che è lì non l'ho capita gran che...
non credo sia sufficientemente chiara..
Qulcuno ne conosce un'altra o è disposto a spiegare un pò di passaggi?

[killing_buddha]

Lemma Sia $X$ un insieme. Definiamo come $\mathbb{2}^X:=\{0,1\}^X$ l'insieme di tutte le funzioni da $X$ in $\{0,1\}$. Allora esiste una corrispondenza biunivoca tra $\mathbb{2}^X$ e $\mathcal{P}(X)$ (l'insieme delle parti di $X$).

Dimostrazione: Sia $A\subseteq X$. Associamo ad esso la sua funzione caratteristica $\chi_A\in \mathbb{2}^X$, $\chi_A:X\rightarrow \{0,1\}$ che manda $x$ in $1$ se $x\in A$ e in $0$ altrimenti.
La funzione $\Xi:\mathcal{P}(X)\rightarrow \mathbb{2}^X$ che manda $A$ in $\chi_A$ è biiettiva (è facile vederlo). Q.E.D.

Teorema. Sia $A$ un insieme, finito o numerabile. Allora si ha
$#A \le #\mathcal{P}(A)$
Dimostrazione: La mappa che manda $a\in A$ nel singoletto $\{a\}\in\mathcal{P}(A)$ è chiaramente iniettiva. Ora, dato che per il lemma precedente $\mathcal{P}(A)\sim \mathbb{2}^A$, basta mostrare che non si possono disporre in una successione numerabile $A_1A_2... A_k...$ l'insieme $\mathbb{2}^A$ delle successioni composte di $0$ e $1$. Supponiamo, per assurdo, che esista una biiezione tra $\mathbb{2}^A$ ed $NN$. Ciò vuol dire che ad ogni successione $A_j=a_{j1}a_{j2}a_{j3}...$ possiamo associare un indice $j\in NN$. Ma questo è assurdo, perchè se nella "griglia diagonale"
$A_1=a_{11}a_{12}a_{13}...$
$A_2=a_{21}a_{22}...$
.
.
.
$A_k = a_{k1}a_{k2}...$
definiamo la successione $S=s_1s_2s_3...$ come $s_k = 0$ se $a_{kk}=1$ e $s_k =1$ altrimenti, risulta chiaramente $S\ne A_i$ per ogni $i\in NN$. Q.E.D.
(da Algebra, un approccio algoritmico, Giulia Maria Piacentini Cattaneo, ed. Decibel Zanichelli)

[angus89]

allora questa non l'ho capita

basta mostrare che non si possono disporre in una successione numerabile $A_1A_2... A_k...$ l'insieme $\mathbb{2}^A$ delle successioni composte di $0$ e $1$.

[Chevtchenko]

Ad esser sincero la dimostrazione del teorema di Cantor che è lì non l'ho capita gran che...
non credo sia sufficientemente chiara..
Qulcuno ne conosce un'altra o è disposto a spiegare un pò di passaggi?

Probabilmente quella riportata da Wikipedia è la più semplice delle dimostrazioni, personalmente trovo che sia chiara in modo impressionante.
Comunque, quali passaggi non hai capito?

[angus89]

Comunque, quali passaggi non hai capito?

Quando viene definito l'insieme $B$, vengono dimostrate determinate cose e si arriva a contraddizione, e quello è ok...
ma chi mi dice che quell'insieme non è vuoto?

[Chevtchenko]

Comunque, quali passaggi non hai capito?

Quando viene definito l'insieme $B$, vengono dimostrate determinate cose e si arriva a contraddizione, e quello è ok...
ma chi mi dice che quell'insieme non è vuoto?

Non è rilevante per la dimostrazione che $B$ sia vuoto o no.