La cardinalità di un insieme A numerabile è minore della cardinalità di P(A)
Ho questa dimostrazione:
che io ho interpretato così:
$(1)$ le successioni $A_1A_2....$ sono le successioni di $0$ e $1$ associate a una funzione caratteristica di uno specifico sottoinsieme. di $A$.
Per esempio, se considero $ A=NN$ al sottoinsieme ${0}$ è associata la successione
$A_0=100000...$
al sottoinsieme ${1}$
$A_1=010000...$
............................
$A_k=a_(k1).... $
e così via
$(2)$ Ora, tra $NN$ e $2^(NN)$ esiste una funzione iniettiva $f$:$f(n)={n}$, ma supponiamo per assurdo che questa funzione sia anche suriettiva. Ciò significa che a ogni successione di $0$ e$1$ appartenente a $2^(NN)$ possiamo associare un elemento di $NN$
$(3)$ faccio un esempio concreto: la successione $S= 1011111111....$ corrispondente al sottoinsieme $0,2,3,4,5...$ di $2^(NN)$ non è controimmagine di $A_1=010000...$
$(4)$ In conclusione, se definisco $S= s_1s_2...$ in questo modo:
$s_k= { ( 0 rarr a_kk=1 ),( 1 rarr a_kk=0):}$ risulta che $ S!=A_1$ e arrivo a un assurdo.
Vi chiedo gentilmente se con i punti $1,2,3$ ho interpretato al meglio la dimostrazione.
Grazie infinite
che io ho interpretato così:
$(1)$ le successioni $A_1A_2....$ sono le successioni di $0$ e $1$ associate a una funzione caratteristica di uno specifico sottoinsieme. di $A$.
Per esempio, se considero $ A=NN$ al sottoinsieme ${0}$ è associata la successione
$A_0=100000...$
al sottoinsieme ${1}$
$A_1=010000...$
............................
$A_k=a_(k1).... $
e così via
$(2)$ Ora, tra $NN$ e $2^(NN)$ esiste una funzione iniettiva $f$:$f(n)={n}$, ma supponiamo per assurdo che questa funzione sia anche suriettiva. Ciò significa che a ogni successione di $0$ e$1$ appartenente a $2^(NN)$ possiamo associare un elemento di $NN$
$(3)$ faccio un esempio concreto: la successione $S= 1011111111....$ corrispondente al sottoinsieme $0,2,3,4,5...$ di $2^(NN)$ non è controimmagine di $A_1=010000...$
$(4)$ In conclusione, se definisco $S= s_1s_2...$ in questo modo:
$s_k= { ( 0 rarr a_kk=1 ),( 1 rarr a_kk=0):}$ risulta che $ S!=A_1$ e arrivo a un assurdo.
Vi chiedo gentilmente se con i punti $1,2,3$ ho interpretato al meglio la dimostrazione.
Grazie infinite
Risposte
No, hai frainteso completamente quello che la dimostrazione sta cercando di dirti (non è sorprendente, è scritta da schifo): $S$ non è costruita in dipendenza di una data successione $A_k$, cioè di un dato elemento $A$ di $2^X$ fissato (preferisco chiamare $X$ l'insieme di riferimento e $A$ i suoi sottoinsiemi); $S$ è invece un elemento di $2^A$ costruito in dipendenza di una ipotetica enumerazione di tutti gli elementi di $2^A$: l'assurdo che trovi, e che ti porta a concludere che tale enumerazione non può esistere, è che $S$ dovrebbe essere un elemento di tale enumerazione, e d'altra parte è costruito apposta per non esserlo.
(Per chi sa: il fatto veramente interessante dell'argomento diagonale di Cantor è che esso è, segretamente, un teorema di punto fisso relativo a un funzionale.)
(Per chi sa: il fatto veramente interessante dell'argomento diagonale di Cantor è che esso è, segretamente, un teorema di punto fisso relativo a un funzionale.)
Grazie per la delucidazione. Spero di aver capito. 
In sintesi l'insieme delle parti è dato da $2^A$ che si suppone numerabile perchè può essere indicizzato con $k in NN$ Ma alla fine si costruisce una successione $S !in 2^A$ e si arriva all'assurdo. È così?
In sintesi l'insieme delle parti è dato da $2^A$ che si suppone numerabile perchè può essere indicizzato con $k in NN$ Ma alla fine si costruisce una successione $S !in 2^A$ e si arriva all'assurdo. È così?
No.
"milos144":E' quanto di più lontano dall'essere così quanto si possa essere!
Grazie per la delucidazione. Spero di aver capito.
@ milos144: [ot]Per curiosità, è un libro napoletano?[/ot]
"milos144":
Grazie per la delucidazione. Spero di aver capito.
Quello che viene dimostrato è questo. Prima di tutto gli elementi di $2^A$ sono successioni con valori $0$ o $1$. Se $\sigma$ è una (qualunque) applicazione da $\mathbb{N}$ in $2^A$ si costruisce un elemento $S$ di $2^A$ (una successione) tale che $S!in\sigma(\mathbb{N})$.
Questo ti dice che nessuna tale $\sigma$ può essere surgetiva.
Ciao gugo82, la dimostrazione dimostrazione l'ho trovata sul Piacentini-cCattaneo. Precisamente un pdf che ho scaricato .
"milos144":
Ciao gugo82, la dimostrazione dimostrazione l'ho trovata sul Piacentini-cCattaneo. Precisamente un pdf che ho scaricato .
Ah, grazie.
Mi sembrava un altro testo, purtroppo in uso dalle mie parti.
Per la cronaca, a me sembra molto più chiaro riportare la dimostrazione di Cantor, che vale senza nessuna ipotesi su $A$, cioè la dimostrazione del teorema di Cantor, che afferma che dato un qualsiasi insieme $A$, si ha $|A| < |P(A)|$. La dimostrazione di questo fatto è la seguente: dati un insieme qualsiasi $A$ e una funzione qualsiasi $f:A to P(A)$ definiamo
[tex]B = \{a \in A\ :\ a \not \in f(a)\} \in P(A)[/tex].
Per costruzione $B$ non appartiene all'immagine della funzione $f$ (perché se fosse $B=f(x)$ con $x in A$ allora certamente $x$ appartiene o non appartiene a $B$, ma entrambi questi fatti portano a una contraddizione immediata), quindi $f$ non può essere suriettiva. Questo mostra che $|A| < |P(A)|$.
[tex]B = \{a \in A\ :\ a \not \in f(a)\} \in P(A)[/tex].
Per costruzione $B$ non appartiene all'immagine della funzione $f$ (perché se fosse $B=f(x)$ con $x in A$ allora certamente $x$ appartiene o non appartiene a $B$, ma entrambi questi fatti portano a una contraddizione immediata), quindi $f$ non può essere suriettiva. Questo mostra che $|A| < |P(A)|$.
Intanto grazie a tutti per la pazienza. Tenterò di nuovo di interpretare la dimostrazione:
$(1)$ chiamo $X$ l'insieme di riferimento quindi $2^X$ è l'insieme di tutti i sottoinsiemi di $X$
$(2)$ denoto ogni sottoinsieme $A sub X$ con una successione di $0$ e $1$ :
$A_1= a_(11)a_(12)a_(13)....$
$A_2= a_(21)a_(22)a_(23)....$
$A_3= a_(31)a_(32)a_(33)....$
$A_k=a_(k1)a_(k2)...$
Ora passo alla Dim:
data una funzione qualunque $ f : NN → 2^X$
mostriamo che $f$ non `e suriettiva.
Per ogni $ n in NN$, denoto con $(a_(nk) | k in NN)$ la
successione $f(n)$.
Per ogni $n$, sia $b_n= 0 $ se $a_(n n)=1 $ e sia $b_n = 1$ se invece $a_(n n) = 0$
Allora la successione $(b_k | k in NN$ che è un elemento di $2^X$ costruita in dipendenza di una ipotetica enumerazione, non appartiene all’immagine di $f$.
Infatti, per ogni $n, f(n) = a_(nk) | k in NN != b_k | k in NN$, visto che per la definizione data,
l’n-esimo elemento $a_(n n) != b_n$
$(1)$ chiamo $X$ l'insieme di riferimento quindi $2^X$ è l'insieme di tutti i sottoinsiemi di $X$
$(2)$ denoto ogni sottoinsieme $A sub X$ con una successione di $0$ e $1$ :
$A_1= a_(11)a_(12)a_(13)....$
$A_2= a_(21)a_(22)a_(23)....$
$A_3= a_(31)a_(32)a_(33)....$
$A_k=a_(k1)a_(k2)...$
Ora passo alla Dim:
data una funzione qualunque $ f : NN → 2^X$
mostriamo che $f$ non `e suriettiva.
Per ogni $ n in NN$, denoto con $(a_(nk) | k in NN)$ la
successione $f(n)$.
Per ogni $n$, sia $b_n= 0 $ se $a_(n n)=1 $ e sia $b_n = 1$ se invece $a_(n n) = 0$
Allora la successione $(b_k | k in NN$ che è un elemento di $2^X$ costruita in dipendenza di una ipotetica enumerazione, non appartiene all’immagine di $f$.
Infatti, per ogni $n, f(n) = a_(nk) | k in NN != b_k | k in NN$, visto che per la definizione data,
l’n-esimo elemento $a_(n n) != b_n$
@ Martino: [ot]Visto che il testo si intitola Algebra - un approccio algoritmico, immagino che una dimostrazione col procedimento diagonale sia stata ritenuta didatticamente più appropriata. Può essere?[/ot]
@Gugo: può darsi, ma spero che abbia almeno citato la dimostrazione classica, perché è molto più pulita.
Sul libro non si fa alcun cenno alla dimostrazione classica, che penso sia quella di gugo82.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo