Dubbio su simbolo insiemi
La scrittura $ {0,1}^(x) $ significa fare x volte il prodotto cartesiano tra $ {0,1} $ ?
Risposte
Penso con $ x in NN $
Un'altra questione... Nn ho chiaro come si dimostri che $ |X| < |P(X)| $ . Ho capito che, esistendo una funzione $ f: Xrarr P(X) $ iniettiva si ha $ |X| leq|P(X)| $ . Ma nn ho afferrato come si arriva a dire che la cardinalità di X sia strettamente minore di quella del suo insieme delle parti.
Quindi basta dimostrare che $ AA n in NN $ è $ n < 2^(n) $ ?
Ci provo per induzione...
Per $ n = 0 $ si ha $ 0 < 1 $ che è vera.
Suppongo che per n= k>0 sia $ k< 2^k $
Dimostro che vale $ k+1< 2^(k+1) $ .
Infatti ció equivale a $ k < 2^(k+1)-1 $ .
Ma k è anche minore di $ 2^k $ .
Potrà quindi essere o $ 2^k geq 2^(k+1)-1 $ o $ 2^k < 2^(k+1)-1 $
Pongo per assurdo che sia $ 2^k geq 2^(k+1)-1 $ che è equivalente a $ 2^kleq 1 $
Ovvero $ kleq 0 $ che va contro l'ipotesi k>0.
Sarà quindi $ 2^k < 2^(k+1)-1 $ , ma essendo $ k< 2^k $ sarà $ k < 2^(k+1)-1 $ ovvero
$ k+1< 2^(k+1) $
È giusto?
Ci provo per induzione...
Per $ n = 0 $ si ha $ 0 < 1 $ che è vera.
Suppongo che per n= k>0 sia $ k< 2^k $
Dimostro che vale $ k+1< 2^(k+1) $ .
Infatti ció equivale a $ k < 2^(k+1)-1 $ .
Ma k è anche minore di $ 2^k $ .
Potrà quindi essere o $ 2^k geq 2^(k+1)-1 $ o $ 2^k < 2^(k+1)-1 $
Pongo per assurdo che sia $ 2^k geq 2^(k+1)-1 $ che è equivalente a $ 2^kleq 1 $
Ovvero $ kleq 0 $ che va contro l'ipotesi k>0.
Sarà quindi $ 2^k < 2^(k+1)-1 $ , ma essendo $ k< 2^k $ sarà $ k < 2^(k+1)-1 $ ovvero
$ k+1< 2^(k+1) $
È giusto?
Questa dimostrazione non vale per insiemi infiniti... Qualcubo saprebbe darmene una che valga anche per quelli?
Come ti spiegava Sergio, con il simbolo $Y^X$, dove $X$ e $Y$ sono insiemi, si intende l'insieme di tutte le funzioni da $X$ a $Y$.
Con l'identificazione insiemistica $2={0,1}$ ottieni dunque che $2^X$ è l'insieme di tutte le funzioni da $X$ a ${0,1}$.
E' chiaro che $2^X$ ha la stessa cardinalità di \(\mathcal{P}(X)\) (la funzione che associa ad ogni elemento di \(A\in\mathcal{P}(X)\) la sua funzione caratteristica $\chi_A\in 2^X$ è biunivoca).
Provo a dare una dimostrazione di $|X|<|2^X|$. Spero sia corretta.
Come hai già notato tu stesso vale $|X|<=|2^X|$. Per dimostrare che non può mai essere $|X|=|2^X|$ supponiamo per assurdo che esista un insieme $X$ siffatto. Allora dovrebbe esistere anche una funzione $g\ :2^X->X$ biiettiva.
Quindi la funzione $g$ dovrebbe essere una funzione biiettiva che come argomento ha una funzione da $X$ a ${0,1}$ e restituisce un elemento di $X$. Scelto un qualunque elemento $x\in X$ denotiamo $f_x$ la funzione (unica) tale che $g(f_x)=x$.
Ora costruiamo la funzione $F:X->{0,1}$ nel seguente modo: $F(x)=1-f_x(x)\ \forall x\in X$.
La funzione $g$ mapperà tale $F$ in un elemento di $X$. Diciamo $y=g(F)\in X$.
Per l'iniettività di $g$, dato che $g(F)=y$ e $g(f_y)=y$ deve necessariamente essere $F=f_y$, ma ciò è assurdo, in quanto la funzione $F$ non può essere identica alla $f_y$, infatti $F(y)=1-f_y(y)\ne f_y(y)$.
L'ipotesi di partenza deve dunque essere falsa, dunque non esiste alcun insieme $X$ tale che $|X|=|2^X|$.
NB: per le cardinalità si definisce $|X|^{|Y|}=|X^Y|$ quindi, dato che $|{0,1}|=2$, al posto di $|2^X|$ di solito si preferisce scrivere $2^{|X|}$.
Con l'identificazione insiemistica $2={0,1}$ ottieni dunque che $2^X$ è l'insieme di tutte le funzioni da $X$ a ${0,1}$.
E' chiaro che $2^X$ ha la stessa cardinalità di \(\mathcal{P}(X)\) (la funzione che associa ad ogni elemento di \(A\in\mathcal{P}(X)\) la sua funzione caratteristica $\chi_A\in 2^X$ è biunivoca).
Provo a dare una dimostrazione di $|X|<|2^X|$. Spero sia corretta.
Come hai già notato tu stesso vale $|X|<=|2^X|$. Per dimostrare che non può mai essere $|X|=|2^X|$ supponiamo per assurdo che esista un insieme $X$ siffatto. Allora dovrebbe esistere anche una funzione $g\ :2^X->X$ biiettiva.
Quindi la funzione $g$ dovrebbe essere una funzione biiettiva che come argomento ha una funzione da $X$ a ${0,1}$ e restituisce un elemento di $X$. Scelto un qualunque elemento $x\in X$ denotiamo $f_x$ la funzione (unica) tale che $g(f_x)=x$.
Ora costruiamo la funzione $F:X->{0,1}$ nel seguente modo: $F(x)=1-f_x(x)\ \forall x\in X$.
La funzione $g$ mapperà tale $F$ in un elemento di $X$. Diciamo $y=g(F)\in X$.
Per l'iniettività di $g$, dato che $g(F)=y$ e $g(f_y)=y$ deve necessariamente essere $F=f_y$, ma ciò è assurdo, in quanto la funzione $F$ non può essere identica alla $f_y$, infatti $F(y)=1-f_y(y)\ne f_y(y)$.
L'ipotesi di partenza deve dunque essere falsa, dunque non esiste alcun insieme $X$ tale che $|X|=|2^X|$.
NB: per le cardinalità si definisce $|X|^{|Y|}=|X^Y|$ quindi, dato che $|{0,1}|=2$, al posto di $|2^X|$ di solito si preferisce scrivere $2^{|X|}$.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo