Twierdzenie Cantora-Bernsteina- warunki równoważne.

[Jakub Gurak]

No nic, totalna nuda na forum, a mam potrzebę działać.

Dla dowolnych zbiorów \(\displaystyle{ A,B,C}\) poniższe 3 warunki są równoważne:

(1) \(\displaystyle{ \left| A\right| \le \left| B\right| \hbox{ i } \left| B\right| \le \left| A\right| \Longrightarrow A\sim B.}\)(Twierdzenie Cantora-Bernsteina)

(2) \(\displaystyle{ \left| A\right| \le \left| B\right| \hbox{ i } B \subset A \Longrightarrow A\sim B.}\)
(3) \(\displaystyle{ \left| A\right| <\left| B\right| \hbox{ i } \left| B\right| <\left| C\right| \Longrightarrow \left| A\right| <\left| C\right|.}\) (Przechodniość silnej nierówności mocy zbiorów).

Dowód: (2) \(\displaystyle{ \Longrightarrow}\)(1) \(\displaystyle{ \Longrightarrow}\)(3)\(\displaystyle{ \Longrightarrow}\)(2)

(2) \(\displaystyle{ \Longrightarrow}\)(1)

Załóżmy, że \(\displaystyle{ \left| A\right| \le \left| B\right|}\) i \(\displaystyle{ \left| B\right| \le \left| A\right|}\). Pokażemy, ze \(\displaystyle{ A\sim B.}\) Niech \(\displaystyle{ f:B \rightarrow A}\) będzie funkcją różnowartościową. Niech \(\displaystyle{ B_0=f _{P}= \stackrel{ \rightarrow }{f}\left( B\right).}\) Zatem \(\displaystyle{ B\sim B_0}\) oraz \(\displaystyle{ B_0\subset A.}\) Mamy \(\displaystyle{ \left| A\right| \le \left| B _0{} \right|}\), bo \(\displaystyle{ \left| A\right| \le \left| B\right|=\left| B_0\right|,}\) mamy \(\displaystyle{ B_{0} \subset A.}\) Zatem z (2) \(\displaystyle{ A\sim B_0\sim B}\), a więc \(\displaystyle{ A\sim B.}\)

(1) \(\displaystyle{ \Longrightarrow}\)(3)

Załóżmy, że \(\displaystyle{ \left| A\right|< \left| B\right|}\) i \(\displaystyle{ \left| B\right| < \left| C\right|}\). Pokażemy, że \(\displaystyle{ \left| A\right| <\left| C\right|.}\) Wiemy, że \(\displaystyle{ \left| A\right|< \left| B\right|}\) zatem możemy to osłabić do \(\displaystyle{ \left| A\right| \le \left| B\right|}\). Podobnie drugie założenie możemy osłabić, i otrzymać \(\displaystyle{ \left| B\right| \le \left| C\right|}\). Zatem z przechodniości (słabej ) nierówności mocy zbiorów( co odpowiada faktowi, że złożenie funkcji różnowartościowych jest funkcją różnowartościową) otrzymujemy \(\displaystyle{ \left| A\right| \le \left| C\right|.}\) Przypuśćmy, że \(\displaystyle{ A\sim C.}\) Ponieważ \(\displaystyle{ \left| B\right| \le \left| C\right|=\left| A\right|}\) więc \(\displaystyle{ \left| B\right| \le \left| A\right|.}\)Ponieważ \(\displaystyle{ \left| B\right| \le \left| A\right|.}\) i \(\displaystyle{ \left| A\right| \le \left| B\right|}\) zatem z (1) dostajemy \(\displaystyle{ A\sim B}\). Ale \(\displaystyle{ \left| A\right|< \left| B\right|}\) co daje sprzeczność. Zatem zbiory \(\displaystyle{ A,C}\) nie mogą być równoliczne- \(\displaystyle{ A\not\sim C}\) i \(\displaystyle{ \left| A\right| \le \left| C\right|.}\) więc \(\displaystyle{ \left| A\right| <\left| C\right|.}\)

(3)\(\displaystyle{ \Longrightarrow}\)(2)

Załóżmy, że \(\displaystyle{ \left| A\right| \le \left| B\right|}\) i \(\displaystyle{ B \subset A.}\). Pokażemy, ze \(\displaystyle{ A\sim B}\).
Ponieważ \(\displaystyle{ B \subset A}\), więc \(\displaystyle{ \left| B\right| \le \left| A\right|}\)(świadczy o tym identyczność \(\displaystyle{ I_B}\)). Przypuśćmy, że \(\displaystyle{ A\not\sim B}\). Doprowadzimy ten przypadek do sprzeczności. Wtedy \(\displaystyle{ \left| A\right| \le \left| B\right|}\), \(\displaystyle{ A\not\sim B}\), więc \(\displaystyle{ \left| A\right|< \left| B\right|}\) Podobnie, ponieważ \(\displaystyle{ \left| B\right| \le \left| A\right|}\), \(\displaystyle{ A\not\sim B}\), wiec \(\displaystyle{ \left| B\right|< \left| A\right|.}\) Ponieważ \(\displaystyle{ \left| A\right|< \left| B\right|}\) i \(\displaystyle{ \left| B\right|< \left| A\right|.}\) więc z (3) \(\displaystyle{ \left| A\right| < \left| A \right|,}\) więc \(\displaystyle{ A\not\sim A}\)- sprzeczność.

\(\displaystyle{ \square}\)

Pokazaliśmy równoważność trzech warunków nie pokazując czy którykolwiek z nich jest prawdziwy. Teraz pokażemy (1)- twierdzenie Cantora-Bernsteina. Już to pokazywałem (w liście ciekawych trików- w takim temacie). Zaprezentuję szybszy dowód korzystający również z lematu Banacha oraz prostego faktu o sumie mnogościowej bijekcji, co udowodniłem tu- pod koniec.

Dowód:

Niech \(\displaystyle{ X,Y}\) będą zbiorami, a \(\displaystyle{ f:X \rightarrow Y}\),oraz \(\displaystyle{ g:Y \rightarrow X}\) funkcjami różnowartościowymi. Znajdziemy bijekcję z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Na mocy lematu Banacha( patrz tu, tu tez jest ten szczegółowy dowód twierdzenia Cantora-Bernsteina) istnieją rozłączne zbiory \(\displaystyle{ X_1,X_2}\) wzajemnie uzupełniające się do \(\displaystyle{ X}\)( tzn. takie, że \(\displaystyle{ X_1\cup X_2=X}\)), jak i istnieją rozłączne zbiory \(\displaystyle{ Y_1,Y_2}\) wzajemnie uzupełniające się do \(\displaystyle{ Y}\), dla których \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( X_{1} \right)=Y_1}\), i symetrycznie \(\displaystyle{ \stackrel{ \rightarrow }{g}\left( Y_{2} \right)=X_2}\). Ponieważ \(\displaystyle{ f,g}\) są funkcjami różnowartościowymi, więc funkcja \(\displaystyle{ f _{|X_1}}\) zawężona do zbioru \(\displaystyle{ X_1}\) jest bijekcją z \(\displaystyle{ X_1}\) do \(\displaystyle{ Y_1.}\) Podobnie \(\displaystyle{ g ^{-1} _{|X_2}}\) jest bijekcją z \(\displaystyle{ X_2}\) do \(\displaystyle{ Y_2}\). Zatem ich sklejenie, czyli suma mnogościowa \(\displaystyle{ f _{|X_1} \cup g ^{-1} _{|X_2}}\) jest bijekcją z \(\displaystyle{ X_1\cup X_2=X}\) do \(\displaystyle{ Y_1\cup Y_2=Y.\square}\)

Zatem udowodniliśmy twierdzenie Cantora-Bernsteina, a zatem pozostałe dwa warunki również.

Jako przykład zastosowania udowodnimy, że wszystkich silnie rosnących funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest dokładnie continuum.

Najpierw udowodnijmy krótko, że \(\displaystyle{ \NN ^{\NN}}\) jest mocy continuum.

Oczywiście \(\displaystyle{ \left| 2^{\NN}=\left\{ 0,1\right\} ^{\NN}\right| \le \left| \NN ^{\NN}\right|}\), bo \(\displaystyle{ \left\{ 0,1\right\} ^{\NN} \subset \NN ^{\NN}.}\) Aby uzyskać nierówność mocy w drugą stronę szacujemy:

\(\displaystyle{ \left| \NN ^{\NN}\right| \le \left| \left( 2^{\NN}\right)^{\NN}\right|=\left| 2 ^{\NN \times \NN} =\left\{ 0,1\right\} ^{\NN \times \NN} \right| =\left| 2 ^{\NN}\right| .}\)

Zatem (na mocy twierdzenia Cantora-Bernsteina) funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum. Przechodzimy do wcześniejszego zadania.


Tych funkcji silnie rosnących oczywiście nie może ich być więcej niż continuum, bo \(\displaystyle{ \NN^{\NN}}\) jest mocy continuum. Pokażemy teraz, że zbiór takich funkcji silnie rosnących (oznaczmy go \(\displaystyle{ Z}\)) jest nie mniejszy względem mocy niż continuum, poprzez zdefiniowanie funkcji różnowartościowej z \(\displaystyle{ 2^{\NN}}\) w \(\displaystyle{ Z}\).

Niech \(\displaystyle{ f\in 2^{\NN}=\left\{ 0,1\right\} ^{\NN}.}\) Definiujemy funkcję \(\displaystyle{ f':\NN \rightarrow \NN}\) jako \(\displaystyle{ f'\left( n\right)=2n+f\left( n\right).}\)

To dodane \(\displaystyle{ f\left( n\right)}\) to jest \(\displaystyle{ 0}\) lub \(\displaystyle{ 1}\), w zależności od tego jaką wartość przyjmuje dla \(\displaystyle{ n}\) ten ciąg zero-jedynkowy.

Zwróćmy uwagę, że funkcja \(\displaystyle{ f'}\) jest zawsze silnie rosnąca, ponieważ dla \(\displaystyle{ n<m}\) mamy \(\displaystyle{ f'(n) = 2n+f(n) \leq 2n+1 < 2n+2 =2(n+1)\leq 2m\leq 2m+f(m)=f'(m).}\)

Zatem \(\displaystyle{ f'}\) jest zawsze silnie rosnąca.


Jeśli \(\displaystyle{ f,g\in 2^{\mathbb{N}}= \left\{ 0,1\right\} ^{\NN}}\) i \(\displaystyle{ f\neq g}\), to również \(\displaystyle{ f'\neq g'}\), ponieważ jeśli \(\displaystyle{ f(n) \neq g(n)}\), dla pewnego \(\displaystyle{ n\in\mathbb{N}}\), (to wtedy jedna z tych funkcji przyjmuje wartość \(\displaystyle{ 0}\) a druga \(\displaystyle{ 1}\)), to \(\displaystyle{ f'(n) = 2n+f(n)\neq 2n + g(n) = g'(n).}\)

Zdefiniowane przekształcenie jest zatem różnowartościowe. Zatem \(\displaystyle{ \left| 2 ^{\NN}\right| \le \left| Z\right| .}\) i \(\displaystyle{ Z\subset \NN^\NN\sim 2^{\NN}.}\)
Twierdzenie Cantora-Bernsteina gwarantuje, że funkcji tych jest dokładnie continuum.

[Jakub Gurak]

No nic, nuda, a mam potrzebę działać.

W podobny sposób dowodzimy, że zbiór \(\displaystyle{ \RR ^{\RR}}\) jest równoliczny z \(\displaystyle{ 2 ^{\RR}}\), czy nawet, że jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to zbiór \(\displaystyle{ X ^{X}}\) jest równoliczny z \(\displaystyle{ 2^X}\), oto dowód (korzystający z twierdzenia Hessenberga):

Oczywiście \(\displaystyle{ \left| 2^X\right| \le \left| X^X\right| .}\) Aby uzyskać nierówność mocy w drugą stronę, szacujemy:

\(\displaystyle{ \left| X^X\right| \le \left| \left( 2^{X}\right) ^{X}\right|=\left| 2^{ X\times X} \right|=\left| 2^X\right|,}\) gdzie ostatnia równość mocy wynika z tego, że zbiór \(\displaystyle{ X}\) jest nieskończony, zatem na mocy twierdzenia Hessenberga \(\displaystyle{ X \times X\sim X.}\)

Na mocy twierdzenia Cantora-Bernsteina zbiór \(\displaystyle{ X^X}\) jest równoliczny z \(\displaystyle{ 2^X}\).

Kolejne zadanie: Czy na płaszczyźnie istnieje okrąg taki że każdy jego punkt ma przynajmniej jedną współrzędną niewymierną

Taki okrąg istnieje. Ale go nie wskaże, tylko dowodzimy to przypuszczając, że każdy okrąg tego nie spełnia, i doprowadzamy do sprzeczności. Jeśli każdy okrąg tego nie spełnia, to każdy okrąg płaszczyzny nie każdy jego punkt ma przynajmniej jedną współrzędną niewymierną, czyli ma punkt, który nie ma współrzędnej niewymiernej, czyli obie współrzędne są wymierne. Zatem każdy okrąg ma punkt o obu współrzędnych wymiernych. Rozważmy okręgi o środku w \(\displaystyle{ (0,0)}\). Jest ich tyle ile liczb rzeczywistych, czyli continuum, i są one rozłączne. Ponieważ każdy taki okrąg ma punkt o obu współrzędnych wymiernych, to możemy utworzyć funkcję przypisując dowolnemu okręgowi taki punkt (stosując aksjomat wyboru). Takie punkty są elementami \(\displaystyle{ \QQ \times \QQ}\), a więc elementami zbioru przeliczalnego. Ponieważ okręgi są rozłączne, a okręgowi przypisujemy jego punkt, więc taka funkcja jest różnowartościowa. Zatem zbiór okręgów jest mocy nie większej niż \(\displaystyle{ \QQ \times \QQ}\), a więc zbiór przeliczalny, zatem zbiór okręgów jest co najwyżej przeliczalny, a ten zbiór okręgów jest jak mówiliśmy mocy continuum ,a więc nieprzeliczalny- sprzeczność. \(\displaystyle{ \square}\)

[Jakub Gurak]

Bardzo ciekawym rozwiązaniem jest rozwiązanie takiego zadania:

Jaką moc ma największy (względem mocy) łańcuch w \(\displaystyle{ \left( P\left(\NN\right), \subset \right)}\)

Łańcuch taki musi być podzbiorem \(\displaystyle{ P\left(\NN\right)\sim\RR,}\) a więc nie może być większej mocy niż continuum. Wykażemy, że istnieje w \(\displaystyle{ \left( P\left( \NN\right) , \subset\right)}\) łańcuch mocy continuum.

Rozważmy najpierw zamiast zbioru liczb naturalnych zbiór liczb wymiernych, tzn. \(\displaystyle{ \left( P\left(\QQ\right), \subset\right)}\)

Wskażemy tu łańcuch mocy continuum. Dla dowolnej liczby rzeczywistej \(\displaystyle{ x \in \left[ 0,1\right]}\) definiujemy podzbiór zbioru \(\displaystyle{ \QQ:}\)

\(\displaystyle{ F _{x}=\left[ 0,x\right] \cap \QQ.}\)

Pozostaje wykazać, że funkcja \(\displaystyle{ x \rightarrow F _{x}}\) jest różnowartościowa. Niech \(\displaystyle{ x,y \in \left[ 0,1\right]}\) będą różnymi liczbami rzeczywistymi. Załóżmy, że \(\displaystyle{ x<y.}\) Wtedy istnieje liczba wymierna \(\displaystyle{ z}\), taka, że \(\displaystyle{ x<z<y}\) , a więc \(\displaystyle{ z \in F _{y}}\) (z definicji zbioru \(\displaystyle{ F _{y}}\)), ale \(\displaystyle{ z\not\in F _{x},}\) więc z zasady równości zbiorów \(\displaystyle{ F _{x} \neq F _{y}.}\) Drugi przypadek jest symetryczny. Zatem \(\displaystyle{ F}\) jest różnowartościowa. A zatem zbiór \(\displaystyle{ F _{P}= \left\{ F _{x}: \ \ x \in \left[ 0,1\right] \right\}}\) jest łańcuchem w \(\displaystyle{ \left( P\left(\QQ\right), \subset \right)}\) mocy continuum.

Zachodzi ciekawy fakt, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ B}\) dowolnym rozkładem zbioru \(\displaystyle{ X}\), to \(\displaystyle{ B}\) ma moc co najwyżej jak zbiór \(\displaystyle{ X}\).

Aby to uzasadnić, to wystarczy dowolnemu zbiorowi \(\displaystyle{ A \in B}\) przypisać jeden jego element (stosując aksjomat wyboru ), i taka funkcja będzie różnowartościowa gdyż zbiory rozkładu \(\displaystyle{ B}\) są rozłączne. Zatem \(\displaystyle{ \left| B\right| \le \left| X\right|. \square}\)

[Jakub Gurak]

No nic, trzeba coś podziałać.

Jeszcze jeden dowód, że \(\displaystyle{ \RR^{\RR}\sim 2^{\RR}}\).

Najpierw udowodnię mały lemat, że \(\displaystyle{ 2^{\NN} \times 2^{\NN}\sim 2^{\NN} }\) :

DOWÓD LEMATU:    

Weźmy dowolną parę \(\displaystyle{ \left( f,g\right) \in \left( 2=\left\{ 0,1\right\} \right) ^{\NN} \times 2 ^{\NN}}\), tzn. parę ciągów zero-jedynkowych, \(\displaystyle{ f=\left( f_0,f_1,f_2,\ldots\right); g=\left( g_0,g_1,g_2,\ldots\right)}\); rozważmy ciąg \(\displaystyle{ h=\left( f_0,g_0,f_1,g_1,f_2,g_2,\ldots\right)}\) , wtedy \(\displaystyle{ h\in \left\{ 0,1\right\} ^{\NN}=2^{\NN}}\). Pozostaje pokazać, że ta funkcja \(\displaystyle{ a: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\in2^{\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{ a\left( f,g\right)=\left( f_0,g_0,f_1,g_1\ldots\right)=\left( h_0,h_1,h_2,h_3,\right)=h}\), a więc ciąg \(\displaystyle{ h}\) jest wartością funkcji \(\displaystyle{ a}\). Otrzymujemy, że funkcja \(\displaystyle{ a}\) jest 'na', a więc jest bijekcją. \(\displaystyle{ \square}\)

Mamy \(\displaystyle{ \left| 2^{\mathbb{R}}\right| \leq \left| \mathbb{R}^{\mathbb{R}}\right| }\), ponieważ \(\displaystyle{ \displaystyle \{a,b\}^{\mathbb{R}}\subset \mathbb{R}^{\mathbb{R}}}\), gdzie \(\displaystyle{ \displaystyle a}\) jest liczbą rzeczywistą \(\displaystyle{ \displaystyle 0}\), a \(\displaystyle{ \displaystyle b}\) liczbą rzeczywistą \(\displaystyle{ \displaystyle 1}\). Równocześnie \(\displaystyle{ \left| \mathbb{R}^{\mathbb{R}}\right|= \left| \left( 2^{\mathbb{N}}\right) ^{\mathbb{R}} \right|= \left| 2^{\mathbb{N}\times\mathbb{R}} \right| \leq \left| 2^{\mathbb{R}\times\mathbb{R}}\right|= \left| 2^{2^{\mathbb{N}}\times 2^{\mathbb{N}}} \right|}\), na podstawie udowodnionego lematu, ten ostatni zbiór jest równoliczny z \(\displaystyle{ 2^{2^{\mathbb{N} }}}\), który to zbiór jest równoliczny, (gdyż \(\displaystyle{ 2^{\NN}}\) jest zbiorem mocy continuum) ze zbiorem \(\displaystyle{ 2^{\mathbb{R}}}\) . Otrzymujemy więc, że \(\displaystyle{ \left| \mathbb{R}^{\mathbb{R}}\right| \le \left| 2^{\RR}\right| }\). Korzystając z twierdzenia Cantora-Bernsteina, wnioskujemy, że \(\displaystyle{ \displaystyle \mathbb{R}^{\mathbb{R}} \sim 2^{\mathbb{R}}. }\)

Kolejne zadanie, wykażemy, że

Dowolna rodzina \(\displaystyle{ \mathbb{B}\subset \mathcal{P}(\mathbb{N})}\) podzbiorów \(\displaystyle{ \NN}\) taka, że dla dowolnych dwóch różnych zbiorów w \(\displaystyle{ \mathbb{B}}\) ich przecięcie jest co najwyżej jednoelementowe, taka rodzina jest co najwyżej przeliczalna.

Aby to wykazać, dzielimy rodzinę \(\displaystyle{ \mathbb{B}}\) na dwie części: \(\displaystyle{ \mathbb{B_1}}\) i \(\displaystyle{ \mathbb{B_2}.}\) Niech rodzina \(\displaystyle{ \mathbb{B_1}}\) będzie złożona z wszystkich zero i jednoelementowych zbiorów z \(\displaystyle{ \mathbb{B}}\), jest ich co najwyzęj przeliczalnie wiele, gdyż są to jednoelementowe podzbiory \(\displaystyle{ \NN}\) (i jeden pusty). Pozostaje wykazać, że zbiór \(\displaystyle{ \mathbb{B_2}}\) (tzn. \(\displaystyle{ \mathbb{B_2}=\mathbb{B} \setminus \mathbb{B_1}}\)) jest co najwyżej przeliczalny, i wtedy \(\displaystyle{ \mathbb{B}}\) jako unia (suma) dwóch zbiorów co najwyżej przeliczalnych przeliczalnych będzie również co najwyżej przeliczalny. Aby wykazać, że \(\displaystyle{ \mathbb{B_2}}\) jest co najwyżej przeliczalny, rozważmy funkcję \(\displaystyle{ f: \mathbb{B_2}\to \mathbb{N}\times\mathbb{N}}\) określoną jako:
\(\displaystyle{ f(A) = (n,m)}\), jeśli \(\displaystyle{ n}\) jest najmniejszym elementem \(\displaystyle{ A}\), a \(\displaystyle{ m}\) jest najmniejszym elementem w \(\displaystyle{ A\setminus\{n\}}\) .

Funkcja \(\displaystyle{ f}\) jest dobrze zdefiniowana, gdyż każdy zbiór w \(\displaystyle{ \mathbb{B_2}}\) ma co najmniej dwa elementy( i na podstawie zasady minimum), i prowadzi w zbiór przeliczalny. Pozostaje wykazać, że \(\displaystyle{ f}\) jest różnowartościowa. Jeśli \(\displaystyle{ X,Y \in\mathbb{B_2}}\),i \(\displaystyle{ f(X) = (n,m)=f(Y)}\), to \(\displaystyle{ X\cap Y \supset \{ n,m\}}\), gdzie \(\displaystyle{ \displaystyle n\neq m}\). Wnioskujemy, że przecięcie \(\displaystyle{ \displaystyle X}\) i \(\displaystyle{ \displaystyle Y}\) jest co najmniej dwuelementowe, a zatem \(\displaystyle{ X=Y}\)( gdyby było \(\displaystyle{ X \neq Y}\), to ponieważ \(\displaystyle{ X,Y\in\mathbb{B}}\), więc na mocy założenia odnośnie tej rodziny zbiór \(\displaystyle{ X \cap Y}\) jest co najwyżej jednoelementowy- sprzeczność), a więc \(\displaystyle{ X=Y}\), i funkcja \(\displaystyle{ f}\) jest różnowartościowa, co należało wykazać.\(\displaystyle{ \square}\)