Teoria mocy zbiorów
: 22 sty 2020, o 00:05
Podam parę ciekawych faktów z teorii mocy zbiorów.
Przypominam \(\displaystyle{ \NN \times \NN\sim\NN}\), \(\displaystyle{ 2^{\NN}=\left\{ 0,1\right\} ^{\NN}\sim\RR. }\)
\(\displaystyle{ A \times B\sim C \times D,}\) jeśli tylko \(\displaystyle{ A\sim C, B\sim D.}\)
Szkic dowodu:
Niech \(\displaystyle{ f:A \rightarrow C}\) będzie bijekcją, \(\displaystyle{ g:B \rightarrow D}\) będzie bijekcją. Rozważmy funkcję \(\displaystyle{ h:A \times B \rightarrow C \times D}\) określoną jako:
\(\displaystyle{ h(a,b)=\left( f(a),g(b)\right). }\)
Funkcja \(\displaystyle{ h}\) jest dobrze określona, i jest różnowartościowa, bo funkcje \(\displaystyle{ f,g}\) są różnowartościowe ( jako bijekcje). Aby pokazać, że jest 'na' zbiór \(\displaystyle{ C \times D}\), to niech \(\displaystyle{ \left( c,d\right)\in C \times D}\). Wtedy \(\displaystyle{ c\in C, d\in D}\). Ponieważ \(\displaystyle{ c\in C}\), a \(\displaystyle{ f:A \rightarrow C}\) jest 'na' zbiór \(\displaystyle{ C}\), to \(\displaystyle{ f(a)=c}\), dla pewnego \(\displaystyle{ a\in A.}\) Ponieważ \(\displaystyle{ d\in D}\), a \(\displaystyle{ g:B \rightarrow D}\) jest 'na' zbiór \(\displaystyle{ D}\), więc \(\displaystyle{ g(b)=d}\), dla pewnego \(\displaystyle{ b\in B}\). Wtedy \(\displaystyle{ h(a,b)=(f(a),g(b))=(c,d)}\), a więc para \(\displaystyle{ (c,d)}\) jest wartością funkcji \(\displaystyle{ h}\). Wobec dowolności wyboru takiej pary otrzymujemy, że \(\displaystyle{ h}\) jest 'na'. A więc \(\displaystyle{ h}\) jest bijekcją, i zbiory \(\displaystyle{ A\times B}\) i \(\displaystyle{ C \times D}\) są równoliczne. \(\displaystyle{ \square}\)
Kolejny fakt:
\(\displaystyle{ 2^X=\left\{ 0,1\right\} ^{X} \sim P(X). }\)
Dowód: Niech \(\displaystyle{ X}\) będzie zbiorem. Zdefiniujmy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{X} =2^X \rightarrow P(X)}\) jako:
\(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}. }\)
Funkcja \(\displaystyle{ \alpha}\) jest dobrze zdefiniowana. Aby wykazać różnowartościowość, to niech funkcje \(\displaystyle{ f,g\in2^X}\), będą takie, że \(\displaystyle{ \alpha \left( f\right) = \alpha \left( g\right)}\). Wtedy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\), i co za tym idzie \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=X \setminus \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=X \setminus\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}= \stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\},}\) czyli \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\}}\) oraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\) ,a więc funkcje \(\displaystyle{ f,g}\) na każdym argumencie przyjmują te same wartości, skąd \(\displaystyle{ f=g}\), a więc \(\displaystyle{ \alpha}\) jest różnowartościowa. Aby wykazać, że jest 'na' to niech \(\displaystyle{ B\subset X}\), wtedy zdefiniujmy \(\displaystyle{ f:X \rightarrow \left\{ 0,1\right\}}\) jako: \(\displaystyle{ f(x)=1}\), jeśli \(\displaystyle{ x\in B}\), i \(\displaystyle{ f(x)=0}\)jeśli \(\displaystyle{ x\not\in B. }\)Otrzymujemy \(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=B}\), a więc zbiór \(\displaystyle{ B}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiego zbioru wnioskujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'. \(\displaystyle{ \square}\)
Przypominam ważny fakt, że dla dowolnych trzech zbiorów \(\displaystyle{ A,B,C}\)
\(\displaystyle{ \left( A^B\right) ^{C}=A ^{B \times C}. }\)
Możemy teraz wykazać bardzo prosto, że iloczyn kartezjański dowolnych dwóch zbiorów przeliczalnych (równolicznych z \(\displaystyle{ \NN}\)) jest zbiorem przeliczalnym.
Niech zbiory \(\displaystyle{ A,B\sim\NN}\). Wtedy na mocy prawa o równoliczności iloczynów kartezjańskich \(\displaystyle{ A \times B\sim \NN\times\NN\sim \NN}\), a więc \(\displaystyle{ A \times B\sim \NN}\), czyli zbiór \(\displaystyle{ A \times B}\) jest przeliczalny. \(\displaystyle{ \square}\)
Możemy wykazać, że \(\displaystyle{ 2^{\NN}\times 2 ^{\NN}\sim 2^{\NN}.}\)
Aby to wykazać rozważmy parę ciągów zero-jedynkowych \(\displaystyle{ f=(f_0,f_1,f_2,\ldots), g=(g_0,g_1,g_2,\ldots),}\) przypiszmy im ciąg
\(\displaystyle{ h=(f_0,g_0,f_1,g_1,f_2,g_2,\dots).}\)
Wtedy \(\displaystyle{ h\in \left( \left\{ 0,1\right\} \cup \left\{ 0,1\right\} \right) ^{\NN}=\left\{ 0,1\right\} ^{\NN}=2^ {\NN}. }\)
Pokażemy, że funkcja \(\displaystyle{ \alpha: 2^{\NN} \times 2 ^{\NN} \rightarrow 2^{\NN} }\) jest bijekcją.
Aby pokazać różnowartościowość, weźmy dwie różne pary ciągów \(\displaystyle{ \left( f_1,g_1\right);\left( f_2,g_2\right) }\), oznaczmy przypisane im ciągi jako odpowiednio \(\displaystyle{ h_1,h_2}\). Wiemy, że \(\displaystyle{ \left( f_1,g_1\right) \neq \left( f_2,g_2\right) }\),więc \(\displaystyle{ f _{1} \neq f _{2}}\) lub \(\displaystyle{ g _{1} \neq g _{2}}\). Jeśli \(\displaystyle{ f _{1} \neq f _{2}}\), to istnieje \(\displaystyle{ n}\) naturalne, takie, że \(\displaystyle{ f_1(n) \neq f_2\left( n\right)}\). Wtedy \(\displaystyle{ h _{1}\left( 2n\right)=f _{1}(n) \neq f_2\left( n\right)= h _{2}\left( 2n\right)}\), a więc \(\displaystyle{ h_1 \neq h_2}\). Drugi przypadek (tzn.\(\displaystyle{ g _{1} \neq g _{2}}\)) jest analogiczny. A więc jest to przekształcenie różnowartościowe. Aby wykazać, że jest 'na', niech \(\displaystyle{ h\in 2^{\NN}}\), tzn. \(\displaystyle{ h=\left( h_0,h_1,h_2,\ldots\right)}\), rozważmy podciągi \(\displaystyle{ f_n=h _{2n}=\left( h _{0},h _{2},h _{4},\ldots \right)}\); oraz \(\displaystyle{ g_n= h_{2n+1}=\left( h_1,h _{3},h _{5},\ldots \right)}\), wtedy \(\displaystyle{ \alpha \left( f,g\right)=\left( f_0,g_0,f_1,g_1,\ldots\right)=\left( h_0,h_1,h_2,h_3,\ldots \right)=h}\), a więc ciąg \(\displaystyle{ h}\) jest wartością funkcji \(\displaystyle{ \alpha }\). Otrzymujemy, że funkcja \(\displaystyle{ \alpha }\) jest 'na', a więc jest bijekcją. \(\displaystyle{ \square}\)
Wnioskiem z tego jest (oraz z tego, że \(\displaystyle{ 2^{\NN}}\) jest mocy continuum), mamy, że \(\displaystyle{ \RR \times \RR\sim\RR.}\)
Mamy bowiem \(\displaystyle{ \RR \times \RR \sim 2^{\NN} \times2^{\NN} \sim 2^{\NN}\sim\RR. \square}\)
A więc płaszczyzna kartezjańska jest równoliczna z prostą.
Na koniec podam ciekawy fakt, ze jeśli mamy dwie pary zbiorów, wraz z bijekcjami między nimi, to jeśli dziedziny tych funkcji są rozłączne i zbiory wartości tych funkcji są rozłączne, to suma mnogościowa tych bijekcji jest bijekcją ze sumy dziedzin w sumę zbiorów wartości. Jest to przydatny fakt. Dowód mogę podesłać zainteresowanym (ale z tego co kojarzę, to dowód jest trochę żmudny).
Więcej zadań z teorii mocy zbiorów można znaleźć też tutaj: Ciekawe zadania.
Przypominam \(\displaystyle{ \NN \times \NN\sim\NN}\), \(\displaystyle{ 2^{\NN}=\left\{ 0,1\right\} ^{\NN}\sim\RR. }\)
\(\displaystyle{ A \times B\sim C \times D,}\) jeśli tylko \(\displaystyle{ A\sim C, B\sim D.}\)
Szkic dowodu:
Niech \(\displaystyle{ f:A \rightarrow C}\) będzie bijekcją, \(\displaystyle{ g:B \rightarrow D}\) będzie bijekcją. Rozważmy funkcję \(\displaystyle{ h:A \times B \rightarrow C \times D}\) określoną jako:
\(\displaystyle{ h(a,b)=\left( f(a),g(b)\right). }\)
Funkcja \(\displaystyle{ h}\) jest dobrze określona, i jest różnowartościowa, bo funkcje \(\displaystyle{ f,g}\) są różnowartościowe ( jako bijekcje). Aby pokazać, że jest 'na' zbiór \(\displaystyle{ C \times D}\), to niech \(\displaystyle{ \left( c,d\right)\in C \times D}\). Wtedy \(\displaystyle{ c\in C, d\in D}\). Ponieważ \(\displaystyle{ c\in C}\), a \(\displaystyle{ f:A \rightarrow C}\) jest 'na' zbiór \(\displaystyle{ C}\), to \(\displaystyle{ f(a)=c}\), dla pewnego \(\displaystyle{ a\in A.}\) Ponieważ \(\displaystyle{ d\in D}\), a \(\displaystyle{ g:B \rightarrow D}\) jest 'na' zbiór \(\displaystyle{ D}\), więc \(\displaystyle{ g(b)=d}\), dla pewnego \(\displaystyle{ b\in B}\). Wtedy \(\displaystyle{ h(a,b)=(f(a),g(b))=(c,d)}\), a więc para \(\displaystyle{ (c,d)}\) jest wartością funkcji \(\displaystyle{ h}\). Wobec dowolności wyboru takiej pary otrzymujemy, że \(\displaystyle{ h}\) jest 'na'. A więc \(\displaystyle{ h}\) jest bijekcją, i zbiory \(\displaystyle{ A\times B}\) i \(\displaystyle{ C \times D}\) są równoliczne. \(\displaystyle{ \square}\)
Kolejny fakt:
\(\displaystyle{ 2^X=\left\{ 0,1\right\} ^{X} \sim P(X). }\)
Dowód: Niech \(\displaystyle{ X}\) będzie zbiorem. Zdefiniujmy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{X} =2^X \rightarrow P(X)}\) jako:
\(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}. }\)
Funkcja \(\displaystyle{ \alpha}\) jest dobrze zdefiniowana. Aby wykazać różnowartościowość, to niech funkcje \(\displaystyle{ f,g\in2^X}\), będą takie, że \(\displaystyle{ \alpha \left( f\right) = \alpha \left( g\right)}\). Wtedy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\), i co za tym idzie \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=X \setminus \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=X \setminus\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}= \stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\},}\) czyli \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\}}\) oraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\) ,a więc funkcje \(\displaystyle{ f,g}\) na każdym argumencie przyjmują te same wartości, skąd \(\displaystyle{ f=g}\), a więc \(\displaystyle{ \alpha}\) jest różnowartościowa. Aby wykazać, że jest 'na' to niech \(\displaystyle{ B\subset X}\), wtedy zdefiniujmy \(\displaystyle{ f:X \rightarrow \left\{ 0,1\right\}}\) jako: \(\displaystyle{ f(x)=1}\), jeśli \(\displaystyle{ x\in B}\), i \(\displaystyle{ f(x)=0}\)jeśli \(\displaystyle{ x\not\in B. }\)Otrzymujemy \(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=B}\), a więc zbiór \(\displaystyle{ B}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiego zbioru wnioskujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'. \(\displaystyle{ \square}\)
Przypominam ważny fakt, że dla dowolnych trzech zbiorów \(\displaystyle{ A,B,C}\)
\(\displaystyle{ \left( A^B\right) ^{C}=A ^{B \times C}. }\)
Możemy teraz wykazać bardzo prosto, że iloczyn kartezjański dowolnych dwóch zbiorów przeliczalnych (równolicznych z \(\displaystyle{ \NN}\)) jest zbiorem przeliczalnym.
Niech zbiory \(\displaystyle{ A,B\sim\NN}\). Wtedy na mocy prawa o równoliczności iloczynów kartezjańskich \(\displaystyle{ A \times B\sim \NN\times\NN\sim \NN}\), a więc \(\displaystyle{ A \times B\sim \NN}\), czyli zbiór \(\displaystyle{ A \times B}\) jest przeliczalny. \(\displaystyle{ \square}\)
Możemy wykazać, że \(\displaystyle{ 2^{\NN}\times 2 ^{\NN}\sim 2^{\NN}.}\)
Aby to wykazać rozważmy parę ciągów zero-jedynkowych \(\displaystyle{ f=(f_0,f_1,f_2,\ldots), g=(g_0,g_1,g_2,\ldots),}\) przypiszmy im ciąg
\(\displaystyle{ h=(f_0,g_0,f_1,g_1,f_2,g_2,\dots).}\)
Wtedy \(\displaystyle{ h\in \left( \left\{ 0,1\right\} \cup \left\{ 0,1\right\} \right) ^{\NN}=\left\{ 0,1\right\} ^{\NN}=2^ {\NN}. }\)
Pokażemy, że funkcja \(\displaystyle{ \alpha: 2^{\NN} \times 2 ^{\NN} \rightarrow 2^{\NN} }\) jest bijekcją.
Aby pokazać różnowartościowość, weźmy dwie różne pary ciągów \(\displaystyle{ \left( f_1,g_1\right);\left( f_2,g_2\right) }\), oznaczmy przypisane im ciągi jako odpowiednio \(\displaystyle{ h_1,h_2}\). Wiemy, że \(\displaystyle{ \left( f_1,g_1\right) \neq \left( f_2,g_2\right) }\),więc \(\displaystyle{ f _{1} \neq f _{2}}\) lub \(\displaystyle{ g _{1} \neq g _{2}}\). Jeśli \(\displaystyle{ f _{1} \neq f _{2}}\), to istnieje \(\displaystyle{ n}\) naturalne, takie, że \(\displaystyle{ f_1(n) \neq f_2\left( n\right)}\). Wtedy \(\displaystyle{ h _{1}\left( 2n\right)=f _{1}(n) \neq f_2\left( n\right)= h _{2}\left( 2n\right)}\), a więc \(\displaystyle{ h_1 \neq h_2}\). Drugi przypadek (tzn.\(\displaystyle{ g _{1} \neq g _{2}}\)) jest analogiczny. A więc jest to przekształcenie różnowartościowe. Aby wykazać, że jest 'na', niech \(\displaystyle{ h\in 2^{\NN}}\), tzn. \(\displaystyle{ h=\left( h_0,h_1,h_2,\ldots\right)}\), rozważmy podciągi \(\displaystyle{ f_n=h _{2n}=\left( h _{0},h _{2},h _{4},\ldots \right)}\); oraz \(\displaystyle{ g_n= h_{2n+1}=\left( h_1,h _{3},h _{5},\ldots \right)}\), wtedy \(\displaystyle{ \alpha \left( f,g\right)=\left( f_0,g_0,f_1,g_1,\ldots\right)=\left( h_0,h_1,h_2,h_3,\ldots \right)=h}\), a więc ciąg \(\displaystyle{ h}\) jest wartością funkcji \(\displaystyle{ \alpha }\). Otrzymujemy, że funkcja \(\displaystyle{ \alpha }\) jest 'na', a więc jest bijekcją. \(\displaystyle{ \square}\)
Wnioskiem z tego jest (oraz z tego, że \(\displaystyle{ 2^{\NN}}\) jest mocy continuum), mamy, że \(\displaystyle{ \RR \times \RR\sim\RR.}\)
Mamy bowiem \(\displaystyle{ \RR \times \RR \sim 2^{\NN} \times2^{\NN} \sim 2^{\NN}\sim\RR. \square}\)
A więc płaszczyzna kartezjańska jest równoliczna z prostą.
Na koniec podam ciekawy fakt, ze jeśli mamy dwie pary zbiorów, wraz z bijekcjami między nimi, to jeśli dziedziny tych funkcji są rozłączne i zbiory wartości tych funkcji są rozłączne, to suma mnogościowa tych bijekcji jest bijekcją ze sumy dziedzin w sumę zbiorów wartości. Jest to przydatny fakt. Dowód mogę podesłać zainteresowanym (ale z tego co kojarzę, to dowód jest trochę żmudny).
Więcej zadań z teorii mocy zbiorów można znaleźć też tutaj: Ciekawe zadania.