Logica/Cardinalità/Dimostrazioni
Salve ragazzi, mi sto perdendo nell'ultimo capitolo delle mie dispense che parla di cardinalità. Più precisamente di dimostrazioni basate sul teorema di Cantor-Schröder-Bernstein. Ho cominciato a fare qualche ricerca sul forum ed ho trovato una discussione che mi ha portato su una pagina dove questo teorema è spiegato molto meglio ( Eccolo ) ma continuo a non capire come applicare la dimostrazione su altri esercizi (non sempre richiede l'utilizzo di questo teorema). Sulle dispense non ci sono esercizi svolti e non saprei proprio da dove partire. Qualcuno mi saprebbe indicare dove trovare degli esercizi svolti su questo argomento oppure aiutarmi a capire come impostare uno di questi esercizi? Vi elenco quelli che ho a disposizione.
sulle mie dispense si utilizzano questi simboli
$\preceq$ ("...si inietta in...")
$~~$ ("...è equipotente a...")
Esercizi:
Dimostrare che:
i) $X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y)$
ii) $(X \preceq Y ^^ Z \preceq W) -> X^Z \preceq Y^W$
iii) se $Y nn Z = \emptyset$, allora $X^{(YuuZ)} ~~ X^Y \times X^Z$
iv) $(X \times Y)^Z ~~ X^Z \times Y^Z$
v) $(X^Y)^Z ~~ X^{(Y \times Z)}$
L'unico esercizio svolto che ho a disposizione è un esercizio preso dall'ultimo esame:
Ricordiamo che l'insieme delle stringhe binarie finite è denotato con ${0,1}^{
Dimostrare che $S$ è in biezione con $NN$
Svolgimento:
Per definizione ${0,1}^{ NN$
Ovviamente $S$ è un sottoinsieme infinito di ${0,1}^{$ è un sottoinsieme infinito di $NN$ perciò è numerabile per definizione (se $X sube NN$ NON è finito, allora è numerabile). La restrizione del dominio di $f$ ad $S$ è la biezione desiderata verso $NN$.
Alternativamente, si puo ragionare così: $S \preceq {0,1}^{
sulle mie dispense si utilizzano questi simboli
$\preceq$ ("...si inietta in...")
$~~$ ("...è equipotente a...")
Esercizi:
Dimostrare che:
i) $X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y)$
ii) $(X \preceq Y ^^ Z \preceq W) -> X^Z \preceq Y^W$
iii) se $Y nn Z = \emptyset$, allora $X^{(YuuZ)} ~~ X^Y \times X^Z$
iv) $(X \times Y)^Z ~~ X^Z \times Y^Z$
v) $(X^Y)^Z ~~ X^{(Y \times Z)}$
L'unico esercizio svolto che ho a disposizione è un esercizio preso dall'ultimo esame:
Ricordiamo che l'insieme delle stringhe binarie finite è denotato con ${0,1}^{
Dimostrare che $S$ è in biezione con $NN$
Svolgimento:
Per definizione ${0,1}^{
Ovviamente $S$ è un sottoinsieme infinito di ${0,1}^{
Alternativamente, si puo ragionare così: $S \preceq {0,1}^{
Risposte
i) potrebbe essere che siccome ogni sottoinsieme di $X$ si inietta in un corrispondente sottoinsieme di $Y$ allora segue la tesi
ii)$X^Z$ si inietta in $X^W$ che si inietta a sua volta in $Y^W$
iii) loading...
iv) loading...
v)loading...
Per gli altri non lo so, in realtà non sono sicuro nemmeno di questi
ii)$X^Z$ si inietta in $X^W$ che si inietta a sua volta in $Y^W$
iii) loading...
iv) loading...
v)loading...
Per gli altri non lo so, in realtà non sono sicuro nemmeno di questi
ciao dan95, credo che la dimostrazione sia molto più complessa. Ho provato a svolgere la prima. Spero che tu o qualcun altro riusciate a dirmi se è questa la strada giusta.
Esercizio i)
Dimostrare che: $ X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y) $
Definizione: Un insieme $X$ si inietta in $Y$, in simboli $ X \preceq Y$, se c'è una funzione iniettiva $f:X->Y$; in questo caso scriveremo $|X|<=|Y| := Card(X)<=Card(Y)$.
Se $X \preceq Y$ con $X!=\emptyset$, allora c'è una suriezione $g: Y->X$
Quindi abbiamo $f:X->Y$ iniettiva con $x_0 in X$ e definiamo
Ora dimostriamo che $\mathcal{P}(X) \preceq \mathcal{P}(Y) $
Abbiamo $\mathcal{P}(X) = {Z | Z sube X}$ e $\mathcal{P}(Y) = {W | W sube Y}$
Sappiamo che esiste un'iniezione da $\mathcal{P}(X)$ in $\mathcal{P}(Y) $, denotiamola con $pi: \mathcal{P}(X)->\mathcal{P}(Y) $.
Sapendo che $X!=\emptyset$ anche $\mathcal{P}(X)!=\emptyset$ (anche se per definizione l'insieme delle parti non è mai vuoto),
allora abbiamo una suriezione $\lambda: \mathcal{P}(Y)->\mathcal{P}(X) $ .
Sia $pi: \mathcal{P}(X)->\mathcal{P}(Y) $ e sia $\emptyset in \mathcal{P}(X)$. Definiamo
In base alla definizione iniziale possiamo anche affermare che se $ X \preceq Y -> |X|<=|Y|$ allora $ \mathcal{P}(X) \preceq \mathcal{P}(Y) -> | \mathcal{P}(X)| <= | \mathcal{P}(Y)|$
Dimostrazione:
$|X|=n$, $|Y|=m$ con $n<=m$
allora
$|\mathcal{P}(X)|= 2^n$ e $|\mathcal{P}(Y)|=2^m$ con $2^n<=2^m$
Esercizio i)
Dimostrare che: $ X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y) $
Definizione: Un insieme $X$ si inietta in $Y$, in simboli $ X \preceq Y$, se c'è una funzione iniettiva $f:X->Y$; in questo caso scriveremo $|X|<=|Y| := Card(X)<=Card(Y)$.
Se $X \preceq Y$ con $X!=\emptyset$, allora c'è una suriezione $g: Y->X$
Quindi abbiamo $f:X->Y$ iniettiva con $x_0 in X$ e definiamo
$g(y)={(f^{-1}(y),if y in Im(f)),(x_0,text{altrimenti}):}$
Ora dimostriamo che $\mathcal{P}(X) \preceq \mathcal{P}(Y) $
Abbiamo $\mathcal{P}(X) = {Z | Z sube X}$ e $\mathcal{P}(Y) = {W | W sube Y}$
Sappiamo che esiste un'iniezione da $\mathcal{P}(X)$ in $\mathcal{P}(Y) $, denotiamola con $pi: \mathcal{P}(X)->\mathcal{P}(Y) $.
Sapendo che $X!=\emptyset$ anche $\mathcal{P}(X)!=\emptyset$ (anche se per definizione l'insieme delle parti non è mai vuoto),
allora abbiamo una suriezione $\lambda: \mathcal{P}(Y)->\mathcal{P}(X) $ .
Sia $pi: \mathcal{P}(X)->\mathcal{P}(Y) $ e sia $\emptyset in \mathcal{P}(X)$. Definiamo
$\lambda(W)={(f^{-1}(W),if W in Im(\pi)),(\emptyset,text{altrimenti}):}$
In base alla definizione iniziale possiamo anche affermare che se $ X \preceq Y -> |X|<=|Y|$ allora $ \mathcal{P}(X) \preceq \mathcal{P}(Y) -> | \mathcal{P}(X)| <= | \mathcal{P}(Y)|$
Dimostrazione:
$|X|=n$, $|Y|=m$ con $n<=m$
allora
$|\mathcal{P}(X)|= 2^n$ e $|\mathcal{P}(Y)|=2^m$ con $2^n<=2^m$
"darkfog":
Sappiamo che esiste un'iniezione da $\mathcal{P}(X)$ in $\mathcal{P}(Y) $, denotiamola con $pi: \mathcal{P}(X)->\mathcal{P}(Y) $.
Sono perplesso, non era quello che stavi cercando di dimostrare?
Si vict hai ragione, ero perplesso anche io mentre lo stavo scrivendo. Non so dove andare a parare e non so se c'è un minimo di verità in quello che ho scritto. Continuo ad elaborare idee... so che devo partire da questo errore 
[size=140]Edit[/size]: Sulle dispense c'è una proposizione che dice " Ogni biezione $f:X->Y$ induce una biezione $g:\mathcal{P}(X) -> \mathcal{P}(Y)$ t.c. $g(A) = f(A) = {f(x) | x in A}$"
Quindi questo mi porta a pensare che devo applicare il teorema di Cantor-Schroder-Bernstein per dimostrare che c'è una biezione tra $X$ ed $Y$ e di conseguenza una biezione sugli insiemi delle parti... quindi se c'è una biezione ci dev'essere per forza un'iniezione. Ci ragiono un po'...
[size=140]Edit[/size]: Sulle dispense c'è una proposizione che dice " Ogni biezione $f:X->Y$ induce una biezione $g:\mathcal{P}(X) -> \mathcal{P}(Y)$ t.c. $g(A) = f(A) = {f(x) | x in A}$"
Quindi questo mi porta a pensare che devo applicare il teorema di Cantor-Schroder-Bernstein per dimostrare che c'è una biezione tra $X$ ed $Y$ e di conseguenza una biezione sugli insiemi delle parti... quindi se c'è una biezione ci dev'essere per forza un'iniezione. Ci ragiono un po'...
Per gli ultimi tre punti, non basta che abbiano la stessa cardinalità?
Per esempio nel punto tre
Supponiamo che $|X|=n$, $|Y|=m$ e $|Z|=k$, poiché $Z nn Y=\O/$ allora $|X^(Y uu Z)|=n^{m+k}$, inoltre $|X^Y|=n^m$ e $|X^Z|=n^k$
Per esempio nel punto tre
Supponiamo che $|X|=n$, $|Y|=m$ e $|Z|=k$, poiché $Z nn Y=\O/$ allora $|X^(Y uu Z)|=n^{m+k}$, inoltre $|X^Y|=n^m$ e $|X^Z|=n^k$
@Dan95 : non dare consigli a caso. L'autore sta facendo un esame in cui questo tipo di operazioni sono da dimostrare.
Non ho fatto un corso con questi argomenti comunque.
(i) Immagino che se si debba semplicemente definire la funzione iniettiva e dimostrarne l'iniettività.
(ii) Pensò si debba procedere così \(X^Z\prec X^W\prec Y^W\). Il primo passò è facile, per il secondo bisogna forse usare una partizione di \(Y\).
Per gli ultimi 3 Immagino si debba usare il teorema citato. Ma come dico non so bene cosa posso usare e cosa no.
Non ho fatto un corso con questi argomenti comunque.
(i) Immagino che se si debba semplicemente definire la funzione iniettiva e dimostrarne l'iniettività.
(ii) Pensò si debba procedere così \(X^Z\prec X^W\prec Y^W\). Il primo passò è facile, per il secondo bisogna forse usare una partizione di \(Y\).
Per gli ultimi 3 Immagino si debba usare il teorema citato. Ma come dico non so bene cosa posso usare e cosa no.
@Vict85
Hai ragione, scusa
Hai ragione, scusa
Non ho capito perché con "applicare Cantor-Schroder-Bernstein" (d'ora in poi CSB) intendi ricalcarne la dimostrazione. Devi semplicemente costruirti due applicazioni iniettive, una in una direzione e una nell'altra e da ciò puoi concludere che esiste una biiezione proprio grazie a CSB.
Ad ogni modo assolutamente nessuno dei cinque esercizi necessita di CSB: devi semplicemente giocare con gli insiemi e con le applicazioni di cui disponi per ipotesi per poi costruirti le opportune funzioni iniettive (nei primi due) o biiettive (negli ultimi tre).
Per esempio in i) prendi un'iniezione \(f \colon X \rightarrow Y\) e consideri l'applicazione "immagine tramite f" che prende un sottoinsieme \(X'\subset X\) e lo invia nell'immagine \(f(X')=\{f(x)\mid x\in X' \}\subset Y\). In virtù dell'iniettività di f anche quest'applicazione è iniettiva (lo dimostri facilmente) e da ciò hai la tesi.
Oppure in iii) consideri l'applicazione \( X^{(Y\cup Z)} \rightarrow X^Y \times X^Z\) che manda un'applicazione \(f\colon Y\cup Z\rightarrow X\) nella coppia \( (f|_Y, f|_Z) \) delle restrizioni di $f$ ad $Y$ e a $Z$ e verifichi che è una biiezione (ti puoi trovare esplicitamente l'inversa).
Ad ogni modo assolutamente nessuno dei cinque esercizi necessita di CSB: devi semplicemente giocare con gli insiemi e con le applicazioni di cui disponi per ipotesi per poi costruirti le opportune funzioni iniettive (nei primi due) o biiettive (negli ultimi tre).
Per esempio in i) prendi un'iniezione \(f \colon X \rightarrow Y\) e consideri l'applicazione "immagine tramite f" che prende un sottoinsieme \(X'\subset X\) e lo invia nell'immagine \(f(X')=\{f(x)\mid x\in X' \}\subset Y\). In virtù dell'iniettività di f anche quest'applicazione è iniettiva (lo dimostri facilmente) e da ciò hai la tesi.
Oppure in iii) consideri l'applicazione \( X^{(Y\cup Z)} \rightarrow X^Y \times X^Z\) che manda un'applicazione \(f\colon Y\cup Z\rightarrow X\) nella coppia \( (f|_Y, f|_Z) \) delle restrizioni di $f$ ad $Y$ e a $Z$ e verifichi che è una biiezione (ti puoi trovare esplicitamente l'inversa).
Ciao ragazzi, grazie per gli spunti che mi date.
_fabricius_, il teorema di CSB so che serve per verificare la proprietà antisimmetrica della relazione d'ordine $<=$ sulla cardinalità degli insiemi e siccome l'ho visto utilizzare nell'esercizio dell'esame pensavo potesse tornare utile anche qui ma adesso che mi ci fai pensare lì c'era da verificare l'equipotenza di due insiemi quindi bisognava tirar fuori il teorema (anche se non è obbligatorio perchè si può davvero spaziare con le dimostrazioni, ed io non riesco a montarne neanche una
)
Spero di aver capito almeno l'esercizio i)
Non ho ben afferrato la costruzione che hai dato tu alla funzione; cioè se bisogna utilizzare solo una funzione o costruirne due. Ti prego di correggermi se ho sbagliato:
i) Dimostrare che: $ X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y) $
Abbiamo una funzione iniettiva $f: X -> Y$ tale che $f(X')={f(x)| x in X'} sub Y$ con $X' sub X$
Abbiamo i due insiemi potenza $\mathcal{P}(X)$ e $\mathcal{P}(Y)$
quindi c'è un'iniezione $g:\mathcal{P}(X) -> \mathcal{P}(Y)$ tale che $g(X')= f(X') in \mathcal{P}(Y)$ (non mi torna molto questa cosa che ho scritto, vorrei iniettare in $\mathcal{P}(Y)$ tutti i possibili sottoinsiemi di X però in questo caso i sottoinsiemi apparterranno a $\mathcal{P}(Y)$ mentre nella funzione precedente abbiamo utilizzato l'inclusione)
_fabricius_, il teorema di CSB so che serve per verificare la proprietà antisimmetrica della relazione d'ordine $<=$ sulla cardinalità degli insiemi e siccome l'ho visto utilizzare nell'esercizio dell'esame pensavo potesse tornare utile anche qui ma adesso che mi ci fai pensare lì c'era da verificare l'equipotenza di due insiemi quindi bisognava tirar fuori il teorema (anche se non è obbligatorio perchè si può davvero spaziare con le dimostrazioni, ed io non riesco a montarne neanche una
)Spero di aver capito almeno l'esercizio i)
Non ho ben afferrato la costruzione che hai dato tu alla funzione; cioè se bisogna utilizzare solo una funzione o costruirne due. Ti prego di correggermi se ho sbagliato:
i) Dimostrare che: $ X \preceq Y -> \mathcal{P}(X) \preceq \mathcal{P}(Y) $
Abbiamo una funzione iniettiva $f: X -> Y$ tale che $f(X')={f(x)| x in X'} sub Y$ con $X' sub X$
Abbiamo i due insiemi potenza $\mathcal{P}(X)$ e $\mathcal{P}(Y)$
quindi c'è un'iniezione $g:\mathcal{P}(X) -> \mathcal{P}(Y)$ tale che $g(X')= f(X') in \mathcal{P}(Y)$ (non mi torna molto questa cosa che ho scritto, vorrei iniettare in $\mathcal{P}(Y)$ tutti i possibili sottoinsiemi di X però in questo caso i sottoinsiemi apparterranno a $\mathcal{P}(Y)$ mentre nella funzione precedente abbiamo utilizzato l'inclusione)
No. Il punto è che sai che esiste \(\displaystyle f\colon X \to Y \). A questo punto definisci \(\displaystyle \tilde{f}\colon\mathscr{P}(X)\to \mathscr{P}(Y) \) come \(\displaystyle \tilde{f}(A) = \{ y\in T : \exists x,\,f(x) = y \} \). Questa è ovviamente una funzione. Devi dimostrare che è iniettiva. Supponi per assurdo che \(\displaystyle A,B\in\mathscr{P}(X) \) siano tali che \(\displaystyle \tilde{f}(A) = \tilde{f}(B) \) con \(\displaystyle A\smallsetminus B \neq \emptyset \) (eventualmente scambia tra di loro i due insiemi). Sia quindi \(\displaystyle a\in A\smallsetminus B \), siccome abbiamo supposto per assurdo che si avesse \(\displaystyle \tilde{f}(A) = \tilde{f}(B) \), allora esiste \(\displaystyle b\in B \) tale che \(\displaystyle f(a) = f(b) \). Per l'iniettività di \(\displaystyle f \) questo implica \(\displaystyle a = b\in B \) e quindi l'assurdo.
Nel secondo va usato un meccanismo simile. Nel senso che si deve costruire la funzione iniettiva in questione. Sia \(\displaystyle f\colon X\to Y \) e \(\displaystyle g\colon Z\to W \). Si costruisce per prima cosa la funzione iniettiva \(\displaystyle \tilde{f} \colon X^Z \to Y^Z \) come \(\displaystyle \omega\mapsto f \circ \omega \). Per il secondo passaggio posso usare invece una funzione suriettiva da \(\displaystyle Y^W \) in \(\displaystyle Y^Z \)? Perché la funzione iniettiva mi sembra meno immediata da costruire.
Nel secondo va usato un meccanismo simile. Nel senso che si deve costruire la funzione iniettiva in questione. Sia \(\displaystyle f\colon X\to Y \) e \(\displaystyle g\colon Z\to W \). Si costruisce per prima cosa la funzione iniettiva \(\displaystyle \tilde{f} \colon X^Z \to Y^Z \) come \(\displaystyle \omega\mapsto f \circ \omega \). Per il secondo passaggio posso usare invece una funzione suriettiva da \(\displaystyle Y^W \) in \(\displaystyle Y^Z \)? Perché la funzione iniettiva mi sembra meno immediata da costruire.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo