Wczoraj udowodniłem dokładnie , że takich relacji symetrycznych jest dokładnie \(\displaystyle{ 2 ^{ \frac{n \cdot \left( n+1\right) }{2} }.}\) Wyznaczyłem też ilość wszystkich relacji antysymetrycznych w niepustym zbiorze skończonym \(\displaystyle{ n}\)- elementowym. Przedstawię teraz dowody tych faktów.Wyznaczyć liczbę wszystkich relacji zwrotnych oraz liczbę wszystkich relacji symetrycznych, jakie utworzyć można w zbiorze \(\displaystyle{ n}\)-elementowym.
Niech \(\displaystyle{ X}\) będzie niepustym zbiorem skończonym \(\displaystyle{ n}\)- elementowym, oznaczmy więc \(\displaystyle{ X= \left\{ x _{1}, x _{2}, \ldots, x_n \right\}.}\)
Niech:
\(\displaystyle{ \mathbb{B}=\left\{ R \subset X \times X\Bigl| \ \ R \hbox{ jest relacją symetryczną}\right\}.}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
Wykażemy, że \(\displaystyle{ \left| \mathbb{B}\right| = 2 ^{ \frac{n \cdot \left( n+1\right) }{2} }.}\)
DOWÓD TEGO FAKTU:
Skończony zbiór \(\displaystyle{ X}\) uporządkujmy liniowo porządkiem \(\displaystyle{ x _{1}< x _{2}<\ldots < x_n}\), i rozważmy zbiór:
\(\displaystyle{ X _{\ \uparrow }= \left\{ \left( x,y\right) \in X \times X\Bigl| \ \ y \ge x \right\} }\),
(jest to górna połowa kwadratu \(\displaystyle{ X \times X}\), wraz z przekątną).
I rozważmy funkcję określoną w następujący sposób:
Dla dowolnego zbioru \(\displaystyle{ A \subset X _{ \uparrow } \subset X \times X}\), rozważmy zbiór:
\(\displaystyle{ R'= A \cup \underbrace{A ^{-1} }_{ \subset X \times X},}\)
a więc \(\displaystyle{ R' \subset X \times X.}\)
I relacja \(\displaystyle{ R'}\) jest symetryczna, gdyż \(\displaystyle{ R'= \left( R'\right) ^{-1}}\), gdyż:
\(\displaystyle{ \left( R'\right) ^{-1}= \left( A \cup A ^{-1} \right) ^{-1}= A ^{-1} \cup \left( A ^{-1} \right) ^{-1}= A ^{-1} \cup A= A \cup A ^{-1}= R',}\)
a więc relacja \(\displaystyle{ R'}\) jest symetryczna.
A zatem \(\displaystyle{ R' \in \mathbb{B }}\), i w ten sposób otrzymujemy funkcję \(\displaystyle{ f}\) działającą w poniższy sposób:
\(\displaystyle{ A \subset X _{ \uparrow } \rightarrow R' \in \mathbb{B}.}\)
Wykażemy, że taka funkcja jest bijekcją.
Wykażemy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa.
Podajmy najpierw pewien Lemat:
Niech:
\(\displaystyle{ X _{ \downarrow }= \left\{ \left( x,y\right): \ \ y<x \right\} .}\)
(Jest to dolna połowa kwadratu \(\displaystyle{ X \times X}\)).
Wykażemy, że:
Lemat: Jeśli \(\displaystyle{ A \subset X _{\uparrow }}\), to: \(\displaystyle{ A ^{-1} \setminus X _{ \downarrow } = A \cap I_X}\),
gdzie \(\displaystyle{ I_X}\)- jest to relacja identyczności na zbiorze \(\displaystyle{ X}\).
DOWÓD TEGO FAKTU::
jeśli \(\displaystyle{ f\left( A_1\right) = f\left( A_2\right)}\) , to to oznacza, z definicji tej funkcji, że:
\(\displaystyle{ A_1 \cup A_1 ^{-1}= A_2 \cup A_2 ^{-1},}\)
a zatem również:
\(\displaystyle{ \left( A_1 \cup A_1 ^{-1} \right) \setminus X _{\downarrow} = \left( A_2 \cup A_2 ^{-1} \right) \setminus X _{\downarrow},}\)
a zatem:
\(\displaystyle{ \left( A_1 \setminus X _{\downarrow} \right) \cup \left( A_1 ^{-1} \setminus X _{\downarrow} \right) = \left( A_2 \setminus X _{\downarrow} \right) \cup \left( A_2 ^{-1} \setminus X _{\downarrow} \right);
}\)
i ponieważ \(\displaystyle{ A _{1}, A _{2} \subset X _{\uparrow}}\), więc zbiory \(\displaystyle{ A_1}\) i \(\displaystyle{ X _{\downarrow}}\) są rozłączne, a zatem \(\displaystyle{ A_1 \setminus X _{\downarrow}= A_1}\); i podobnie zbiory \(\displaystyle{ A_2}\) i \(\displaystyle{ X _{\downarrow}}\) są rozłączne, więc \(\displaystyle{ A_2 \setminus X _{\downarrow}= A_2}\), a zatem otrzymujemy, że:
A\(\displaystyle{ _1 \cup \left( A_1 ^{-1} \setminus X _{\downarrow} \right)= A_2 \cup \left( A_2 ^{-1} \setminus X _{\downarrow} \right),}\)
a zatem, na mocy powyższego Lematu:
\(\displaystyle{ A_1= A_1 \cup \left( \underbrace{A_1 \cap I_X}_{ \subset A_1}\right) = A_2 \cup \left( \underbrace{A_2 \cap I_X}_{ \subset A_2}\right) =A_2,}\)
czyli \(\displaystyle{ A_1=A_2}\), i funkcja \(\displaystyle{ f}\) jest różnowartościowa.
Wykażemy teraz, że funkcja \(\displaystyle{ f}\) jest funkcją 'na'.
Niech \(\displaystyle{ R \in \mathbb{B}.}\) Wtedy \(\displaystyle{ R\subset X \times X}\) i \(\displaystyle{ R}\) jest relacją symetryczną.
Rozważmy zbiór:
\(\displaystyle{ A= \left\{ \left( x,y\right) \in R: \ y \ge x \right\} \subset X _{\uparrow}.}\)
Wtedy:
\(\displaystyle{ f(A)= A \cup A ^{-1}= \left\{ \left( x,y\right) \in R: \ y \ge x \right\} \cup \left\{ \left( y,x\right): \ \ \left( x,y\right) \in A \right\} = \left\{ \left(x,y \right) \in R: \ y \ge x \right\} \cup \left\{ \left( y,x\right) \in X \times X: \ \left( x,y\right) \in R \hbox{ i } y \ge x \right\} =}\)
i ponieważ relacja \(\displaystyle{ R}\) jest symetryczna, więc ten zbiór jest równy:
\(\displaystyle{ =\left\{ \left( x,y\right) \in R: \ y \ge x \right\} \cup \left\{ \left( y,x\right) \in X \times X: \ \left( y,x\right) \in R \hbox{ i } y \ge x \right\} = \left\{ \left( x,y\right) \in R: \ y \ge x \right\} \cup \left\{ \left( x,y\right): \ \left( x,y\right) \in R \hbox{ i } x \ge y \right\} =R }\),
gdyż zbiór \(\displaystyle{ X= \left\{ x_1, x_2, \ldots, x_n\right\} }\) jest liniowo uporządkowany przez porządek \(\displaystyle{ x_1< x_2<\ldots < x_n.}\)
A zatem \(\displaystyle{ R= f\left( A\right)}\), a więc relacja \(\displaystyle{ R}\) jest wartością funkcji \(\displaystyle{ f}\). Z dowolności wyboru takiej relacji otrzymujemy, że funkcja \(\displaystyle{ f}\) jest funkcją 'na'.
A zatem \(\displaystyle{ \mathbb{B}\sim P\left( X _{\uparrow} \right).}\)
Ponieważ \(\displaystyle{ I_X\sim n}\), więc \(\displaystyle{ \left| X _{\uparrow} \right| = \left[ n \cdot n-n\right] /2 +n= \frac{n \cdot \left( n-1\right) +2n }{2}= \frac{n \cdot \left( n+1\right) }{2}.}\)
A zatem \(\displaystyle{ \left| \mathbb{B}\right|=2 ^{\left| X _{\uparrow} \right| } = 2 ^{ \frac{n \cdot \left( n+1\right) }{2} }. \square}\)
A ilość relacji zwrotnych na niepustym skończonym zbiorze \(\displaystyle{ n}\) -elementowym, to \(\displaystyle{ 2 ^{\left( n \cdot n\right) -n} =2 ^{n \cdot \left( n-1\right) } }\), gdyż takie relacje zwrotne muszą zawierać przekątną, a poza przekątną mogą być dowolne, skąd trzeba zliczyć wszystkie podzbiory takiego obszaru, którego moc wynosi \(\displaystyle{ \left( n \cdot n -n\right) }\), i stąd ten wzór.
Zliczymy jeszcze relacje antysymetryczne na zbiorze skończonym. Tzn.:
Niech \(\displaystyle{ X}\) będzie niepustym zbiorem skończonym \(\displaystyle{ n}\)-elementowym; oznaczmy więc \(\displaystyle{ X=\left\{ x _{1}, x_2,\ldots, x_n \right\}.}\)
Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich relacji antysymetrycznych w zbiorze \(\displaystyle{ X}\), tzn. niech:
\(\displaystyle{ \mathbb{B}= \left\{ R \subset X \times X\Bigl| \ \ R\hbox{ jest relacją antysymetryczną}\right\}.}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
ROZWIĄZANIE:
Dla dowolnego punktu leżącego na przekątnej musimy zdecydować czy on należy do relacji antysymetrycznej czy też nie, a zatem ponieważ \(\displaystyle{ I_X\sim n}\), więc mamy tu \(\displaystyle{ 2 ^{n}}\) możliwości; a dla dowolnego punktu leżącego powyżej przekątnej (których to punktów jest dokładnie \(\displaystyle{ \frac{n \cdot n- n}{2} }\) ) mamy trzy możliwości (gdyż rozważamy tu relacje antysymetryczne): albo ten punkt należy do relacji, a przeciwległy do niego punkt, względem przekątnej, nie należy; albo na odwrót; albo obydwa nie należą; i tak dla dowolnego punktu z górnej połowy naszego kwadratu kartezjańskiego, a zatem mamy tu \(\displaystyle{ 3 ^{ \frac{n \cdot n-n}{2} }}\) możliwości, i, uwzględniając przekątną, mamy łącznie \(\displaystyle{ 3 ^{ \frac{n\left( n-1\right) }{2} } \cdot 2 ^{n}}\) relacji antysymetrycznych.\(\displaystyle{ \square}\)
Na koniec, wykażemy prawo, które ostatnio udowodniłem:
Jeśli \(\displaystyle{ \mathbb{A}, \mathbb{B}}\) są rodzinami zbiorów, to mamy prawo:
\(\displaystyle{ \left( \bigcup \mathbb{A}\right) \cap \left( \bigcup\mathbb{B}\right) = \bigcup _{A \in \mathbb{A}, B \in \mathbb{B} } \left( A \cap B\right) .}\)
Czyli aby wyznaczyć przekrój dwóch sum uogólnionych wystarczy wyznaczyć wszystkie możliwe (niepuste) przekroje postaci \(\displaystyle{ A \cap B}\), gdzie \(\displaystyle{ A \in \mathbb{A}, B \in \mathbb{B}}\), i wziąć sumę wszystkich takich przekrojów.
DOWÓD TEGO FAKTU:
Mamy:
\(\displaystyle{ \bigcup_{A \in \mathbb{A}, B \in \mathbb{B}} \left( A \cap B\right) = \bigcup_{A \in \mathbb{A}} \left( \bigcup_{B \in \mathbb{B}} \left( A \cap B\right) \right) = \bigcup_{A \in \mathbb{A}} \left[ A \cap \left( \bigcup_{B \in \mathbb{B}} B\right) \right] = \bigcup_{A \in \mathbb{A}} \left[ A \cap \bigcup\mathbb{B}\right] = \bigcup_{A \in \mathbb{A}} \left[ \bigcup\mathbb{B} \cap A\right] =}\)
gdzie zauważamy, że zbiór \(\displaystyle{ \bigcup\mathbb{B}}\) jest jednym ustalonym zbiorem, więc kontynuując nasze równości, to jest równe:
\(\displaystyle{ = \bigcup\mathbb{B} \cap \left( \bigcup_{A \in \mathbb{A}} A \right) = \left( \bigcup\mathbb{B}\right) \cap \left( \bigcup\mathbb{A}\right) = \left( \bigcup\mathbb{A}\right) \cap \left( \bigcup\mathbb{B}\right).\square}\)
Dodano po 3 miesiącach 25 dniach 5 minutach 9 sekundach:
Wykazałem wczoraj, że na zbiorze liczb rzeczywistych istnieje dokładnie \(\displaystyle{ 2 ^{\left| \RR\right|} }\) wszystkich relacji symetrycznych, a następnie wykorzystałem to dowodu, że na zbiorze liczb rzeczywistych istnieje również dokładnie \(\displaystyle{ 2 ^{\left| \RR\right| } }\) wszystkich relacji antysymetrycznych.
Wykazałem też dzisiaj, że na zbiorze liczb całkowitych istnieje dokładnie continuum relacji symetrycznych. Przedstawię teraz dowody tych ciekawych faktów.
Niech:
\(\displaystyle{ \mathbb{B}= \left\{ R \subset \RR \times \RR\Bigl| \ \ R \hbox{ jest relacją symetryczną w zbiorze } \RR\right\}.}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
Niech:
\(\displaystyle{ S= \left\{ \left( x,y\right) \in \RR ^{2}: \ y \ge x \right\},}\)
będzie górną polową płaszczyzny wraz z przekątną \(\displaystyle{ y=x.}\)
Dla dowolnego zbioru \(\displaystyle{ A \subset S}\) rozważmy relację \(\displaystyle{ R_A}\), daną jako:
\(\displaystyle{ R_A= \underbrace{A}_{ \subset \RR ^{2} } \cup \underbrace{ A ^{-1}}_{ \subset \RR ^{2} } \subset \RR ^{2}. }\)
Wtedy, jak łatwo sprawdzić, relacja \(\displaystyle{ R_A}\) jest relacją symetryczną, a zatem \(\displaystyle{ R_A \in \mathbb{B}}\), i w ten sposób otrzymujemy funkcję \(\displaystyle{ f}\) działającą w następujący sposób:
\(\displaystyle{ A \subset S \stackrel{f}{ \rightarrow } R_A \in \mathbb{B}.}\)
Wykażemy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa.
Niech:
\(\displaystyle{ S'= \RR ^{2} \setminus S= \left\{ \left( x,y\right) \in \RR^2: \ y<x \right\},}\)
będzie dolna połową płaszczyzny.
Podajmy najpierw pewien Lemat.
Lemat: Dla dowolnego zbioru \(\displaystyle{ A \subset S}\), mamy: \(\displaystyle{ A ^{-1} \setminus I_X \subset S'.}\)
DOWÓD TEGO FAKTU::
DOWÓD TEGO FAKTU::
\(\displaystyle{ }\)
Z jednej strony \(\displaystyle{ S\supset I_R\sim \RR}\), a więc \(\displaystyle{ \left| S\right| \ge \left| \RR\right|}\),
a z drugiej strony \(\displaystyle{ S \subset \RR^2}\), a zatem: \(\displaystyle{ \left| S\right| \le \left| \RR^2\right| = \left| \RR\right|}\),
i na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ S\sim \RR.}\)
Ponieważ wykazaliśmy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa, więc:
\(\displaystyle{ \left| P(S)\right| \le\left| \mathbb{B}\right|}\), tzn.
\(\displaystyle{ \left| \mathbb{B}\right| \ge \left| P(S)\right| \stackrel{S\sim \RR} {=} \left| P(\RR)\right| = \left| 2=\left\{ 0,1\right\} ^{\RR} \right|}\),
czyli:
\(\displaystyle{ \left| \mathbb{B} \right| \ge \left| 2 ^{\RR} \right|. }\)
Ale:
\(\displaystyle{ \mathbb{B} \subset P\left( \RR \times \RR\right) }\),
a zatem:
\(\displaystyle{ \left| \mathbb{B}\right| \le \left| P\left( \RR \times \RR\right) \right|\stackrel{\RR \times \RR\sim \RR}{=} \left| P(\RR)\right|= \left| 2 ^{\RR} \right|.}\)
I na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \mathbb{B}\sim 2 ^{\RR}}\),
czyli istnieje dokładnie \(\displaystyle{ 2 ^{\left| \RR\right| }}\) wszystkich relacji symetrycznych na zbiorze liczb rzeczywistych\(\displaystyle{ .\square}\)
Wyznaczymy jeszcze ilość wszystkich relacji antysymetrycznych na zbiorze liczb rzeczywistych, tzn. niech:
\(\displaystyle{ \mathbb{B}= \left\{ R \subset \mathbb{R} \times \mathbb{R}\Bigl| \ \ R \hbox{ jest relacją antysymetryczną w zbiorze } \RR\right\} .}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
Wykażemy, że: \(\displaystyle{ \left| \mathbb{B}\right|= 2 ^{\left| \RR\right| }. }\)
DOWÓD TEGO FAKTU:
Niech:
\(\displaystyle{ \mathbb{A}= \left\{ R \subset \mathbb{R} \times \mathbb{R}\Bigl| \ \ R \hbox{ jest relacją symetryczną }\right\} \sim 2 ^{\RR}.}\)
Bowiem, na mocy dowodu powyżej, ta rodzina ma moc równą \(\displaystyle{ 2 ^{\left| \RR\right| } .}\)
Niech:
\(\displaystyle{ S'= \left\{ \left( x,y\right) \in \RR ^{2}: \ y<x \right\};}\)
jest to dolna połowa płaszczyzny.
Rozważmy funkcję \(\displaystyle{ \alpha}\) działającą w następujący sposób:
\(\displaystyle{ R \in \mathbb{A} \stackrel{ \alpha }{ \rightarrow } R'= R \setminus S' \subset R \subset \mathbb{R} ^{2}.}\)
Łatwo jest pokazać, że relacja \(\displaystyle{ R'}\) jest antysymetryczna,
a zatem \(\displaystyle{ R' \in \mathbb{B}}\), i funkcja:
\(\displaystyle{ R \in \mathbb{A} \stackrel{ \alpha }{\rightarrow} R' \in \mathbb{B},}\)
jest dobrze określona.
Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.
DOWÓD TEGO FAKTU::
\(\displaystyle{ \left| \mathbb{A}\right| \le \left| \mathbb{B}\right|}\) ,
czyli:
\(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \mathbb{A}\right|=\left| 2= \left\{ 0,1\right\} ^{\RR} \right|.}\)
Ale mamy:
\(\displaystyle{ \mathbb{B} \subset P\left( \RR \times \RR\right)}\),
a zatem:
\(\displaystyle{ \left| \mathbb{B}\right| \le \left| P\left( \RR \times \RR\right) \right| \stackrel{\RR \times \RR\sim \RR}= \left| P(\RR)\right|= \left| 2=\left\{ 0,1\right\} ^{\RR} \right|.}\)
Na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \mathbb{B} \sim 2 ^{\RR}.\square}\)
Na koniec wykażemy, że wszystkich relacji symetrycznych na zbiorze liczb całkowitych jest continuum.
Tzn. niech:
\(\displaystyle{ \mathbb{B}= \left\{ R \subset \mathbb{Z} \times \mathbb{Z}\Bigl| \ \ R \hbox{ jest relacją symetryczną}\right\}.}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
Wykażemy, że ta rodzina \(\displaystyle{ \mathbb{B}}\) jest mocy continuum.\(\displaystyle{ }\)\(\displaystyle{ }\)
DOWÓD TEGO FAKTU:
Niech:
\(\displaystyle{ S= \left\{ \left( x,y\right) \in \ZZ \times \ZZ \Bigl| \ \ y \ge x \right\} ,}\)
będzie górną połową kratownicy \(\displaystyle{ \ZZ \times \ZZ,}\) wraz z przekątną \(\displaystyle{ y=x.}\)
Dla dowolnego zbioru \(\displaystyle{ A \subset S}\) rozważmy zbiór \(\displaystyle{ R_A,}\) dany jako:
\(\displaystyle{ R_A= \underbrace {A}_{ \subset \ZZ \times \ZZ} \cup \underbrace{A ^{-1}}_{ \subset \ZZ \times \ZZ} \subset \ZZ \times \ZZ.}\)
Wtedy relacja \(\displaystyle{ R_A}\), jak łatwo sprawdzić, jest relacją symetryczną, a zatem \(\displaystyle{ R_A \in \mathbb{B}}\), i w ten sposób otrzymujemy funkcję \(\displaystyle{ f}\) działającą w następujący sposób:
\(\displaystyle{ A \subset S\stackrel{f}{ \rightarrow } R_A \in \mathbb{B}.}\)
Wykażemy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa.
W tym celu weźmy dwa różne zbiory \(\displaystyle{ A_1, A_2 \subset S}\).
Wtedy \(\displaystyle{ A_1\not \subset A_2}\) lub \(\displaystyle{ A_2\not \subset A_1.}\)
Jeśli \(\displaystyle{ A_1\not\subset A_2,}\) to wtedy istnieje puinkt \(\displaystyle{ \left( x,y\right) \in A_1}\), taki, że \(\displaystyle{ \left( x,y\right)\not\in A_2.}\)
Wtedy \(\displaystyle{ \left( x,y\right) \in R _{A_1}= A_1 \cup A_{1} ^{-1}}\), a \(\displaystyle{ \left( x,y\right)\not\in R _{A_2}= A_2 \cup A_2 ^{-1}. }\)
Gdyby bowiem byłoby \(\displaystyle{ \left( x,y\right) \in R _{A_2}}\), to ponieważ \(\displaystyle{ \left( x,y\right) \not \in A_2}\), to \(\displaystyle{ \left( x,y\right) \in A_2 ^{-1}}\), a wtedy, z definicji relacji odwrotnej: \(\displaystyle{ \left( y,x\right) \in A_2 \subset S}\), a stąd \(\displaystyle{ x \ge y}\). Ponieważ jednak \(\displaystyle{ \left( x,y\right) \in A_1 \subset S}\), więc \(\displaystyle{ y \ge x}\), a zatem, z antysymetrii porządku na liczbach rzeczywistych otrzymujemy: \(\displaystyle{ x=y}\). Wtedy jednak \(\displaystyle{ \left( x,y\right) = \left( x,x\right) = \left( y,x\right) \in A_2}\)- sprzeczność.
Wobec czego \(\displaystyle{ \left( x,y\right) \not \in R _{A_2}}\), a \(\displaystyle{ \left( x,y\right) \in R _{A_1}}\), wobec czego: \(\displaystyle{ R _{A_1} \neq R _{A_2}}\).
Jeśli \(\displaystyle{ A_2\not \subset A_1}\), to analogicznie otrzymujemy, że: \(\displaystyle{ R _{A_1} \neq R _{A_2}.}\)
A zatem funkcja \(\displaystyle{ f}\) jest różnowartościowa.
A zatem \(\displaystyle{ \left| P\left( S\right) \right| \le \left| \mathbb{B}\right|.}\)
Łatwo jest zauważyć, że \(\displaystyle{ S\sim \NN}\),
gdyż \(\displaystyle{ S\supset I _{\ZZ}\sim \ZZ\sim \NN}\), a zatem \(\displaystyle{ \left| S\right| \ge \left| \NN\right|}\), (a z drugiej strony \(\displaystyle{ S \subset \ZZ \times \ZZ\sim \NN}\)), a zatem \(\displaystyle{ S\sim \NN.}\)
A zatem:
\(\displaystyle{ \left| \mathbb{B}\right| \ge \left| P(S)\right| \stackrel{S\sim \NN} {= } \left| P\left( \NN\right) \right|= \left| \RR\right|.}\)
Z drugiej strony:
\(\displaystyle{ \mathbb{B} \subset P\left( \ZZ \times \ZZ\right) }\),
a zatem:
\(\displaystyle{ \left| \mathbb{B}\right| \le \left| P\left( \ZZ \times \ZZ\right) \right|\stackrel{\ZZ \times \ZZ\sim \NN} {=} \left| P(\NN)\right| = \left| \RR\right| .}\)
Na mocy twierdzenia Cantora- Bernsteina \(\displaystyle{ \mathbb{B}\sim \RR}\),
czyli istnieje dokładnie continuum relacji symetrycznych na zbiorze liczb całkowitych.\(\displaystyle{ \square}\)
Na koniec podam zagadkę:
Podać przykład funkcji \(\displaystyle{ f:\NN \rightarrow \NN}\), której zbiór wartości jest dokładnie zbiorem wszystkich liczb parzystych.
ROZWIĄZANIE:
