Jeśli \(\displaystyle{ X}\) jest zbiorem, to na ile sposobów zbiór \(\displaystyle{ X}\) można przedstawić w postaci sumy dwóch jego istotnych podzbiorów??
Udało się to przedwczoraj rozwiązać( też uogólniłem na pokrycie przez \(\displaystyle{ n}\) zbiorów). Przedstawię teraz te proste rozwiązania. (Dla zbiorów skończonych nie wyznaczyłem dokładnej ilości tych wszystkich sposobów, tylko mogę oszacować tą ilość, a dla zbiorów nieskończonych będzie to \(\displaystyle{ 2 ^{\left| X\right| }}\), gdzie \(\displaystyle{ \left| X\right|}\) oznacza moc zbioru \(\displaystyle{ X}\), czyli uogólnienia pojęcia ilości elementów zbioru, na zbiory nieskończone ). Przedstawię teraz dowody tych ciekawych faktów.
Niech \(\displaystyle{ X}\) będzie zbiorem. Przez przedstawienie zbioru \(\displaystyle{ X}\) w postaci sumy rozumiemy parę jego podzbiorów, których suma daje cały zbiór, tzn. rozważamy rodzinę \(\displaystyle{ \mathbb{B}}\) takich par określoną jako:
\(\displaystyle{ \mathbb{B}=\left\{ (A,B)\in P(X) \times P(X)\Bigl | \ \ A \cup B=X , A \neq X, B \neq X\right\}. }\)
Jest to rodzina par istotnych podzbiorów zbioru \(\displaystyle{ X}\), których suma daje cały zbiór \(\displaystyle{ X}\).
I pytamy o moc \(\displaystyle{ \left| \mathbb{B}\right|}\).
Jeśli \(\displaystyle{ X}\) jest co najmniej dwuelementowy ( w zbiorze jednoelementowym i zero-elementowym nie da się w ogóle znaleźć takich sposobów), rozważmy najpierw przypadek gdy zbiór \(\displaystyle{ X}\) jest skończony, \(\displaystyle{ n}\)-elementowy. tzn. \(\displaystyle{ X=\left\{ x_1, x_2,\ldots, x_n\right\} .}\)
Niech \(\displaystyle{ A}\) będzie dowolnym ustalonym niepustym i różnym od całego zbioru \(\displaystyle{ X}\) podzbiorem zbioru \(\displaystyle{ X}\)- \(\displaystyle{ A\subsetneq X.}\)
Rozważmy zbiór \(\displaystyle{ B=A'=X \setminus A}\). Wtedy \(\displaystyle{ B\subset X}\). Mamy też \(\displaystyle{ A \cup B=A \cup A'=X}\), mamy też \(\displaystyle{ A \neq X }\) i \(\displaystyle{ B \neq X}\)( gdyby byłoby \(\displaystyle{ B=X}\), to \(\displaystyle{ A'=X}\), a zatem \(\displaystyle{ A=(A')'=X'=\emptyset}\), czyli \(\displaystyle{ A=\emptyset}\)- sprzeczność). A zatem \(\displaystyle{ B \neq X,A \neq X, A \cup B=X}\), więc możemy wnioskować, że \(\displaystyle{ (A,B) \in \mathbb{B}.}\)
Rozważmy teraz funkcję \(\displaystyle{ \left\{ \right\} \neq A\subsetneq X \rightarrow \left( A.B \right) \in \mathbb{B}.}\)
Jeśli \(\displaystyle{ A_1,A_2\subset X}\)( i gdy zbiory \(\displaystyle{ A_1,A_2}\) są niepustymi i różnymi od całego zbioru \(\displaystyle{ X}\) podzbiorami), to jeśli \(\displaystyle{ A_1 \neq A_2}\), to oczywiście dla przypisanych par zbiorów mamy: \(\displaystyle{ (A_1, B_1) \neq (A_2, B_2)}\), a zatem funkcja \(\displaystyle{ f: P(X) \setminus \left\{ \emptyset ,X\right\} \rightarrow \mathbb{B}}\) jest różnowartościowa. A zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{n}-2.}\)
Zauważmy, że już dla \(\displaystyle{ n=3}\) mamy dwie kolejne, nieuzyskane w powyższy sposób, możliwości, i dla większych \(\displaystyle{ n}\) podobnie, co oznacza, że dla zbiorów skończonych \(\displaystyle{ n}\)-elementowych, poczynając od \(\displaystyle{ n=3}\), mamy co najmniej \(\displaystyle{ 2 ^{n}}\) takich sposobów.
Ilość tych sposobów możemy ograniczyć z góry przez \(\displaystyle{ 2^n \cdot 2 ^{n}}\)- gdyż każde takie przedstawienie jest parą podzbiorów zbioru \(\displaystyle{ X}\), zbioru \(\displaystyle{ n}\)-elementowego. Wszystkich podzbiorów zbioru \(\displaystyle{ X}\) jest \(\displaystyle{ 2^n}\), więc par takich podzbiorów może być tylko \(\displaystyle{ 2 ^{n} \cdot 2 ^{n}=2 ^{\left( 2n\right) }}\), może nie będę się trudził aby dociekać ile ich jest dokładnie, na ogół dużo, dokładnie jak dużo- mało to ciekawe.
Niech teraz \(\displaystyle{ X}\) będzie zbiorem nieskończonym.
Niech \(\displaystyle{ \left\{ \right\} \neq A\subsetneq X }\) będzie niepustym istotnym podzbiorem. Rozważmy zbiór \(\displaystyle{ B=A'=X \setminus A\subset X.}\) Wtedy \(\displaystyle{ A \cup B=A \cup A'=X, A \neq X, B \neq X }\)( ostatni fakt łatwo nie wprost udowodnić), czyli \(\displaystyle{ B \neq X,A \neq X, A \cup B=X}\), skąd możemy wnioskować, że \(\displaystyle{ (A,B) \in \mathbb{B}.}\)
I rozważmy funkcję \(\displaystyle{ \left\{ \right\} \neq A\subsetneq X \stackrel{f}{\rightarrow} (A,B) \in \mathbb{B}.}\)
Oczywiście taka funkcja \(\displaystyle{ f}\) jest różnowartościowa. A zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \left\{ A\subset X\Bigl| \ \ \left\{ \right\} \neq A \neq X \right\} \right| =2 ^{|X|}-2.}\) Zauważmy, że \(\displaystyle{ 2^X\sim P(X)\supset \left\{ \left\{ x\right\} \Bigl| \ x\in X\right\}\sim X}\). Ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, ponieważ zbiór równoliczny ze zbiorem nieskończonym jest nieskończony, ponieważ nadzbiór zbioru nieskończonego jest nieskończony, to zbiór \(\displaystyle{ 2^X}\) jest nieskończony.
Ponieważ \(\displaystyle{ 2^X}\) jest zbiorem nieskończonym, to \(\displaystyle{ 2 ^{|X|}-2=2^{\left| X\right| }}\), a zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| X\right| } .}\)
Aby uzyskać nierówność mocy zbiorów w drugą stronę użyjemy twierdzenia Hessenberga.
Ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, to zbiór \(\displaystyle{ P(X)}\) jako zbiór większej mocy jest nieskończony, gdyż zbiór większej lub równej mocy niż pewien zbiór nieskończony jest nieskończony.
Dowód tego faktu:
Uogólnijmy na pokrycie przez \(\displaystyle{ n}\) zbiorów.
Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym. Niech \(\displaystyle{ n}\) będzie liczbą naturalną, taką, że \(\displaystyle{ n \ge 2}\). Będziemy rozważać układy (\(\displaystyle{ n}\)-ki) takich \(\displaystyle{ n}\) istotnych podzbiorów zbioru \(\displaystyle{ X}\), których suma daje cały zbiór \(\displaystyle{ X}\), tzn. rozważamy rodzinę \(\displaystyle{ \mathbb{B}}\), tym razem zdefiniowaną jako:
\(\displaystyle{ \mathbb{B}=\left\{ \left( X_1,X_2,\ldots,X_n\right) \in \underbrace{\left( \left( P(X) \times P(X)\right) \times P(X)\right) \times \ldots \times P(X)}_{n} \Bigl| \ \ \bigcup\limits_{i=1}^{n} X_i=X, \hbox{ i } \left( X_i \neq X, \hbox{ dla każdego
} i=1,2, \ldots,n\right) \right\}.
}\)
I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}}\). Wykażemy, że ta moc to również \(\displaystyle{ 2 ^{\left| X\right| }.
}\)
Niech \(\displaystyle{ \left\{ \right\} \neq A\subsetneq X}\). Zdefiniujmy \(\displaystyle{ n}\) podzbiorów zbioru \(\displaystyle{ X:}\)
\(\displaystyle{ X_1=A}\) ,
\(\displaystyle{ X_2=A'=X \setminus A}\),
\(\displaystyle{ X_3=X_4=\ldots=X_n=\emptyset.
}\)
Wtedy \(\displaystyle{ X_i \neq X}\), dla \(\displaystyle{ i=1,2,\ldots ,n}\) (dla \(\displaystyle{ i=2}\), mamy \(\displaystyle{ X_2 \neq X}\), bo \(\displaystyle{ A \neq \emptyset}\)), i wtedy:
\(\displaystyle{ \bigcup_{i=1}^{n} X_i = \left( \bigcup_{i=1}^{2} X_i \right) \cup \left( \bigcup_{i=3}^{n} X_i\right)= X_1 \cup X_2 \cup \left( \bigcup_{i=3}^{n} \emptyset\right)=\left( A \cup A' \right) \cup \emptyset= X.}\)
A zatem możemy wnioskować, że: \(\displaystyle{ (X_1, X_2,\ldots,X_n)\in\mathbb{B}. }\)
Rozważmy teraz funkcję \(\displaystyle{ f}\) działającą jako:
\(\displaystyle{ \left\{ \right\} \neq A\subsetneq X \rightarrow \left( X_{1,A}; X_{2,A}; \ldots ,X_{n,A}\right) \in \mathbb{B} .}\)
Łatwo sprawdzić, że taka funkcja jest różnowartościowa, a zatem \(\displaystyle{ \left|\mathbb{B}\right| \ge \left| P(X) \setminus \left\{ \emptyset, X\right\} \right|. }\)
Ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, to zbiór \(\displaystyle{ P(X)}\), jako zbiór większej mocy, jest nieskończony, a zatem \(\displaystyle{ \left( P(X) \setminus \left\{ \emptyset,X \right\}\right) \sim P(X)\sim 2^X.}\) A zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| X\right| }}\). Wykażemy teraz prosty lemat, wynikający przez indukcję z twierdzenia Hessenberga:
Lemat. Jeśli zbiór \(\displaystyle{ Y}\) jest nieskończony, a \(\displaystyle{ n}\) liczbą naturalną i \(\displaystyle{ n \ge 1}\), to \(\displaystyle{ Y^n:=\underbrace{\left( \left( Y \times Y\right) \times Y\right) \times \ldots\ \times Y}_{n}}\) taki zbiór \(\displaystyle{ Y^n}\) jest równoliczny ze zbiorem \(\displaystyle{ Y .}\)
PROSTY DOWÓD: