Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Jakub Gurak »

Od co najmniej półtora tygodnia zastanawiał mnie ten ciekawy problem, tzn.:

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?? :o

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:    
Wobec czego u nas zbiór \(\displaystyle{ P(X)}\) jest nieskończony, a zatem z twierdzenia Hessenberga: \(\displaystyle{ P(X) \times P(X)\sim P(X)\sim 2^X.}\) Ponieważ, z definicji rodziny \(\displaystyle{ \mathbb{B},}\) mamy \(\displaystyle{ \mathbb{B} \subset P(X) \times P(X)\sim 2^{X}}\), więc \(\displaystyle{ \left| \mathbb{B} \right| \le 2 ^{\left| X\right| } }\) . Mamy \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| X \right| } }\) , a zatem z twierdzenia Cantora-Bernsteina otrzymujemy:\(\displaystyle{ \left| \mathbb{B}\right| =2 ^{\left| X\right| }.\square}\) :lol:


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:    
Mamy \(\displaystyle{ \mathbb{B}\subset (P(X))^n}\)- z definicji rodziny \(\displaystyle{ \mathbb{B}}\). Ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, to zbiór \(\displaystyle{ P(X)}\) jest nieskończony, więc na mocy lematu powyżej \(\displaystyle{ (P(X))^n\sim P(X)\sim 2^X}\), ponieważ \(\displaystyle{ \mathbb{B}\subset (P(X))^n\sim 2^X}\), więc \(\displaystyle{ \left| \mathbb{B}\right| \le 2 ^{\left| X\right| }.}\) Udowodniliśmy wcześniej, że \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| X\right| }}\) , zatem na podstawie twierdzenia Cantora-Bernsteina: \(\displaystyle{ \left| \mathbb{B} \right|=2 ^{\left| X\right| } .\square}\) :D :lol:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Jakub Gurak »

Udało się wczoraj ukończyć badania nad pewnym ciekawym podobnym problemem. Tzn. jeśli mamy zbiór oraz jego podzbiór, to można pytać na ile sposobów ten podzbiór można przedstawić w postaci przekroju dwóch podzbiorów całego zbioru. Udało się to wczoraj zbadać (choć nie najlepiej, odpowiedź zależy od mocy dopełnienia tego podzbioru). Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy zbiór \(\displaystyle{ X}\), oraz podzbiór \(\displaystyle{ A\subset X}\). I rozważmy rodzinę wszystkich par podzbiorów zbioru \(\displaystyle{ X}\), których przekrój daje podzbiór \(\displaystyle{ A}\), czyli jest to rodzina wszystkich przedstawień podzbioru \(\displaystyle{ A}\) w postaci przekroju dwóch podzbiorów całego zbioru, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \left( B_1,B_2\right) \in P(X) \times P(X)\Bigl| \ \ B_1 \cap B_2=A \right\}}\),

i pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)


Podajmy najpierw trzy lematy.

Lemat 1.

Rozważmy (zachowując oznaczenia) zbiór \(\displaystyle{ A'= X \setminus A}\), tzn. dopełnienie zbioru \(\displaystyle{ A}\); i rozważmy rodzinę
\(\displaystyle{ \mathbb{A} }\) wszystkich par podzbiorów tego dopełnienia- rodzinę wszystkich par podzbiorów rozłącznych, tzn.

\(\displaystyle{ \mathbb{A}=\left\{ \left( B_1, B_2\right) \in P(A') \times P(A') \Bigl| \ \ B_1 \cap B_2=\left\{ \right\} \right\} . }\)


Wykażemy, że \(\displaystyle{ \mathbb{A}\sim \mathbb{B}}\). (No bo skoro przekrój tych dwóch podzbiorów musi dawać podzbiór \(\displaystyle{ A}\), to te dwa zbiory muszą zawierać ten zbiór \(\displaystyle{ A}\), istotne są zatem kawałki tych zbiorów leżące w dopełnieniu zbioru \(\displaystyle{ A}\), a te kawałki nie mogą się przecinać, bo wtedy przekrój tych dwóch zbiorów byłby za duży, poza tym to mogą być dowolne te kawałki, ale musimy to udowodnić.

DOWÓD:

Rozważmy funkcję \(\displaystyle{ \alpha :\mathbb{A} \rightarrow \mathbb{B}}\) , daną jako:

\(\displaystyle{ \alpha \left( B_1, B_2\right)=\left( B_1 \cup A, B_2 \cup A\right),}\)

Ponieważ \(\displaystyle{ B_1,B_2\subset A'\subset X}\), więc \(\displaystyle{ B_1,B_2\subset X, }\) i \(\displaystyle{ A\subset X}\), więc \(\displaystyle{ B_1 \cup A\subset X}\) i \(\displaystyle{ B_2 \cup A\subset X}\). I mamy

\(\displaystyle{ \left( B_1 \cup A\right) \cap \left( B_2 \cup A\right)=\underbrace {\left( B_1 \cap B_2\right)}_{=\emptyset} \cup A=A. }\)

Tak więc \(\displaystyle{ \left( B_1 \cup A, B_2 \cup A\right)\in\mathbb{B}}\) , i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. W tym celu weźmy dwie pary zbiorów \(\displaystyle{ \left( B_1,B_2\right);\left( C_1,C_2\right)}\) takie, że \(\displaystyle{ \alpha \left( B_1, B_2\right)= \alpha \left( C_1, C_2\right) }\). Z definicji funkcji \(\displaystyle{ \alpha}\) oznacza to, że:

\(\displaystyle{ \left( B_1 \cup A, B_2 \cup A\right) =\left( C_1 \cup A, C_2 \cup A\right)}\), a więc

\(\displaystyle{ B_1 \cup A=C_1 \cup A}\) i \(\displaystyle{ B_2 \cup A=C_2 \cup A}\).

Rozważmy najpierw tylko pierwszy przypadek koniunkcji.

Jeśli \(\displaystyle{ B_1 \cup A=C_1 \cup A}\), to \(\displaystyle{ \left( B_1 \cup A\right) \setminus A=\left( C_1 \cup A\right) \setminus A}\), i ponieważ \(\displaystyle{ B_1, C_1\subset A'}\), więc zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A}\) są rozłączne; oraz zbiory \(\displaystyle{ C_1}\) i \(\displaystyle{ A}\) są rozłączne, a zatem \(\displaystyle{ B_1=\left( B_1 \cup A\right) \setminus A=\left( C_1 \cup A\right) \setminus A=C_1}\),

czyli \(\displaystyle{ B_1=C_1.}\)

Przypadek \(\displaystyle{ B_2 \cup A= C_2 \cup A,}\) w sposób symetryczny daje równość: \(\displaystyle{ B_2=C_2.}\)

A zatem \(\displaystyle{ \left( B_1, B_2\right) = \left( C_1, C_2\right)}\). A zatem funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


Wykażemy teraz, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.

Niech \(\displaystyle{ \left( B_1, B_2\right)\in\mathbb{B}. }\)

Wtedy \(\displaystyle{ B_1, B_2\subset X}\) i \(\displaystyle{ B_1 \cap B_2=A}\). A zatem \(\displaystyle{ A\subset B_1}\) i \(\displaystyle{ A\subset B_2}\). Rozważmy zbiory:

\(\displaystyle{ C_1:=B_1 \setminus A\subset X \setminus A=A'}\),
i \(\displaystyle{ C_2:=B_2 \setminus A\subset A'}\).

Wtedy \(\displaystyle{ C_1 \cap C_2=\left( B_1 \setminus A\right) \cap \left( B_2 \setminus A\right)=\left( B_1 \cap B_2\right) \setminus A=A \setminus A=\emptyset}\), a zatem \(\displaystyle{ C_1 \cap C_2=\emptyset}\), i zbiory \(\displaystyle{ C_1}\), \(\displaystyle{ C_2}\) są rozłaczne. A zatem \(\displaystyle{ \left( C_1,C_2\right)\in\ \mathbb{A}}\), i wtedy

\(\displaystyle{ \alpha \left( C_1,C_2\right)=\left( C_1 \cup A, C_2 \cup A\right) = \left( \left( B_1 \setminus A\right) \cup A , \left( B_2 \setminus A\right) \cup A \right) \stackrel{A\subset B_1} {\mathop {=}_{A\subset B_2} } \left( B_1, B_2\right) }\),

czyli \(\displaystyle{ \alpha \left( C_1, C_2\right)=\left( B_1, B_2\right)}\),

a więc para zbiorów \(\displaystyle{ \left( B_1, B_2\right)}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiej pary otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.

A zatem \(\displaystyle{ \alpha}\) jest bijekcją, i \(\displaystyle{ \mathbb{A}\sim \mathbb{B}.}\)


Wykażemy teraz jeszcze jeden lemat:

Lemat 2.

Niech \(\displaystyle{ X}\) będzie zbiorem. Rozważmy rodzinę \(\displaystyle{ \mathbb{D}}\) wszystkich par podzbiorów zbioru \(\displaystyle{ X}\), wszystkich par podzbiorów rozłącznych.

Wykażemy, że \(\displaystyle{ \mathbb{D}\sim 3^X:=\left\{ 1,2,3\right\} ^X.}\)


DOWÓD TEGO FAKTU:

Rozważmy funkcję \(\displaystyle{ \alpha :3^X \rightarrow \mathbb{D}}\), określoną następująco:

Dla dowolnej ustalonej funkcji \(\displaystyle{ f:X \rightarrow \left\{ 1,2,3\right\}}\), definiujemy parę zbiorów jako:

\(\displaystyle{ \alpha \left( f\right) = \left(\underbrace { \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\} }_{ \subset X}, \underbrace{ \stackrel { \rightarrow } {f ^{-1} } \left\{ 2\right\} } _{\subset X}\right).}\)

Wtedy te przeciwobrazy są zbiorami rozłącznymi, gdyż:

\(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\} \cap \stackrel{ \rightarrow }{f ^{-1} } \left\{ 2\right\}= \stackrel{ \rightarrow }{f ^{-1} } \left( \left\{ 1\right\} \cap \left\{ 2\right\} \right) = \stackrel{ \rightarrow }{f ^{-1} } \left( \emptyset\right)=\emptyset}\),

a więc przeciwobrazy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\}}\) i \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ 2\right\}}\) są zbiorami rozłącznymi.

A zatem \(\displaystyle{ \alpha (f)= \left( \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\} , \stackrel{ \rightarrow }{f ^{-1} } \left\{ 2\right\} \right) \in \mathbb{D}}\), i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.


Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

W tym celu weźmy dwie dowolne funkcję \(\displaystyle{ f_1, f_2\in 3^X=\left\{ 1,2,3\right\} ^{X}}\) takie, że \(\displaystyle{ \alpha \left( f_1\right)= \alpha \left( f_2\right).}\) Z definicji funkcji \(\displaystyle{ \alpha}\) oznacza to, że \(\displaystyle{ \left( \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 1\right\} , \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 2\right\} \right)= \left( \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} , \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\} \right)}\), a zatem \(\displaystyle{ \stackrel{ \rightarrow }{f _1^{-1} } \left\{ 1\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\}}\), oraz \(\displaystyle{ \stackrel{ \rightarrow }{f _1^{-1} } \left\{ 2\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\}}\), i co za tym idzie, ponieważ przeciwobraz dopełnienia zbioru, do całej przeciwdziedziny, jest dopełnieniem, do dziedziny funkcji, jest dopełnieniem przeciwobrazu, więc:

\(\displaystyle{ \stackrel{ \rightarrow }{f _2^{-1} } \left\{ 3\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left( \left\{ 1,2\right\} ^{\prime} \right) = X \setminus \stackrel{ \rightarrow }{f _2^{-1} } \left\{ 1,2\right\} =X \setminus \left[ \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} \cup \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\}\right] = X \setminus \left[\stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 1\right\} \cup \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 2\right\} \right]= X \setminus \left[ \stackrel{ \rightarrow }{f_1 ^{-1} } \left( \left\{ 1\right\} \cup \left\{ 2\right\}= \left\{ 1,2\right\} \right) \right] = \\ =\stackrel{ \rightarrow }{f_1 ^{-1} } \left( \left\{ 1,2\right\} ^{\prime} \right) = \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 3\right\} . }\)

Czyli \(\displaystyle{ \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 3\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 3\right\}.}\) Mamy również: \(\displaystyle{ \stackrel{ \rightarrow }{f _1^{-1} } \left\{ 1\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\}}\), oraz \(\displaystyle{ \stackrel{ \rightarrow }{f _1^{-1} } \left\{ 2\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\}.}\)

Łatwo więc teraz będzie pokazać, że \(\displaystyle{ f_1=f_2}\).

Mamy \(\displaystyle{ f_1, f _2: X \rightarrow \left\{ 1,2,3\right\}}\) , więc aby pokazać, że te funkcję są równe, to weźmy dowolny argument \(\displaystyle{ x\in X,}\) i pokażmy, że funkcję \(\displaystyle{ f_1, f_2}\) na tym argumencie przyjmują te same wartości. Ponieważ przeciwdziedzina tych funkcji ma tylko trzy elementy, więc rozważmy przypadki:

\(\displaystyle{ 1^{\circ}: f_1(x)= 1}\), wtedy \(\displaystyle{ x \in \stackrel{ \rightarrow }{f _1^{-1} } \left\{ 1\right\} = \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\}}\), a zatem, z zasady równości zbiorów: \(\displaystyle{ x\in \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 1\right\}}\), skąd, z definicji przeciwobrazu, otrzymujemy, że: \(\displaystyle{ f_2(x) \in \left\{ 1\right\} }\), skąd \(\displaystyle{ f_2(x)= 1= f_1(x).}\)

\(\displaystyle{ 2 ^{\circ}:}\) Jeśli \(\displaystyle{ f_1(x)=2}\), wtedy \(\displaystyle{ x \in \stackrel{ \rightarrow }{f_1 ^{-1} } \left\{ 2\right\}=\stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\}}\), a więc \(\displaystyle{ x\in \stackrel{ \rightarrow }{f_2 ^{-1} } \left\{ 2\right\}}\), a więc, z definicji przeciwobrazu: \(\displaystyle{ f_2 (x) \in \left\{ 2\right\}}\) , a więc \(\displaystyle{ f_2(x)= 2= f_1(x).}\)

\(\displaystyle{ 3 ^{\circ}:}\) A jeśli \(\displaystyle{ f_1(x)= 3}\), to podobnie uzasadniamy, że \(\displaystyle{ f_2(x)=3}\).

Otrzymujemy zatem, że funkcje \(\displaystyle{ f_1, f_2}\) na każdym argumencie \(\displaystyle{ x\in X}\) przyjmują te same wartości, skąd:\(\displaystyle{ f_1= f_2}\).

A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


Wykażemy teraz, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.

Niech \(\displaystyle{ B_1,B_2\in\mathbb{D}.}\) Wtedy \(\displaystyle{ B_1, B_2\subset X,}\) i zbiory \(\displaystyle{ B_1, B_2}\) są rozłączne. Zdefiniujmy funkcję \(\displaystyle{ f:X \rightarrow \left\{ 1,2,3\right\} }\), jako:

\(\displaystyle{ f(x)=\begin{cases} 1, \hbox{ jesli } x\in B_1, \\ 2, \hbox{ jeśli } x\in B_2, \\ 3, \hbox{ jeśli } x\not\in B_1 \hbox{ i } x\not\in B_2. \end{cases}}\)

Ponieważ zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\) są rozłączne, więc nie może element \(\displaystyle{ x}\) należeć jednocześnie do zbioru \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\), a więc funkcja \(\displaystyle{ f}\) jest dobrze określona, a więc \(\displaystyle{ f:X \rightarrow \left\{ 1,2,3\right\}}\), i \(\displaystyle{ f\in 3^X}\). I mamy:

\(\displaystyle{ \alpha \left( f\right)= \left(\mathop { \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\} }_{ \subset X}, \mathop{ \stackrel { \rightarrow } {f ^{-1} } \left\{ 2\right\} } _{\subset X}\right)= \left( B_1, B_2\right).}\) Czyli para zbiorów \(\displaystyle{ \left( B_1, B_2\right)}\) jest wartością funkcji \(\displaystyle{ \alpha }\). Z dowolności wyboru takiej pary otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.

A więc \(\displaystyle{ \alpha}\) jest bijekcją, i \(\displaystyle{ 3^X\sim \mathbb{D}. \square}\)


I ostatni lemat:

Lemat 3.

Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ 3^X:=\left\{ 1,2,3\right\} ^{X}\sim 2^X.}\)
DOWÓD TEGO FAKTU::    

Łatwo teraz będzie rozwiązać nasze zadanie, tzn. przypomnę: jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ A\subset X}\) jego podzbiorem, to pytamy o moc rodziny \(\displaystyle{ \mathbb{B}}\) wszystkich par podzbiorów zbioru \(\displaystyle{ X}\), których przekrój daje podzbiór \(\displaystyle{ A}\).

Rozwiązanie:

Niech \(\displaystyle{ \mathbb{A}}\) będzie rozważaną powyżej rodzina wszystkich par podzbiorów dopełnienia zbioru \(\displaystyle{ A}\) na zbiory rozłączne.

Na mocy Lematu 1: \(\displaystyle{ \left| \mathbb{B}\right| =\left| \mathbb{A}\right|}\), a na mocy Lematu 2 ta moc jest równa: \(\displaystyle{ 3 ^{\left| A'\right| }}\).

Jeśli zatem te dopełnienie \(\displaystyle{ A'}\) jest zbiorem skończonym, \(\displaystyle{ n}\)-elementowym, to \(\displaystyle{ \left| B\right|=3 ^n.}\)

Jeśli zaś dopełnienie \(\displaystyle{ A'}\) jest zbiorem nieskończonym, to \(\displaystyle{ \left| B\right|=3 ^{\left| A'\right| },}\) i na mocy Lematu 3 ta moc wynosi \(\displaystyle{ 2 ^{\left| A'\right| } .\square}\) :D :lol:


Lepiej by było, gdybyśmy naszą moc wyrazili w stosunku do mocy zbioru \(\displaystyle{ X}\) lub do mocy podzbioru \(\displaystyle{ A}\), a nie odnośnie do mocy dopełnienia zbioru \(\displaystyle{ A}\). W niektórych przypadkach uda się to zrobić.

Jeśli \(\displaystyle{ X}\) jest zbiorem skończonym \(\displaystyle{ n}\)-elementowym, a \(\displaystyle{ A\subset X}\) zbiorem \(\displaystyle{ m}\)-elementowym, gdzie \(\displaystyle{ m \le n}\), to \(\displaystyle{ \left| A'\right|=n-m}\), a zatem \(\displaystyle{ \left| \mathbb{B}\right|=3 ^{n-m}.}\)

W przypadku, gdy zbiór \(\displaystyle{ X}\) jest przeliczalny- nic nie poradzę, bo moc dopełnienia zbioru \(\displaystyle{ A}\) może być dowolna (oczywiście, co najwyżej przeliczalna).

Jeśli \(\displaystyle{ X}\) jest zbiorem nieprzeliczalnym, a \(\displaystyle{ A\subset X}\) zbiorem co najwyżej przeliczalnym, to ponieważ zbiory nieprzeliczalne są odporne na ujmowanie zbiorów co najwyżej przeliczalnych (udowodniłem kiedyś taki fakt), więc \(\displaystyle{ A'=X \setminus A \sim X}\), a więc \(\displaystyle{ \left|\mathbb{B}\right|= 2 ^{\left| A'\right| }= 2 ^{\left| X\right| } . \square}\) :D


Ciekawi mnie też taki problem, że jeśli mamy zbiór oraz podzbiór, to na ile sposobów ten podzbiór można przedstawić w postaci różnicy dwóch podzbiorów całego zbioru- myślałem, że na tyle samo sposobów na ile można przedstawić w postaci przekroju dwóch podzbiorów, gdyż przekrój wyznacza różnicę, a różnica wyznacza przekrój- to prawda, ale to chyba zły pomysł, bo podzbiór mamy ustalony, więc nie możemy nim manewrować, będzie można ten ciekawy problem z różnicą badać... 8-)
Awatar użytkownika
Flype
Użytkownik
Użytkownik
Posty: 14
Rejestracja: 21 sty 2022, o 23:04
Płeć: Mężczyzna
wiek: 27
Podziękował: 9 razy
Pomógł: 6 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Flype »

Kod: Zaznacz cały

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind


Na przykład \(\displaystyle{ S(n, k) = 7}\) dla \(\displaystyle{ n = 4, k=2}\), bo zbiór \(\displaystyle{ abcd}\) można podzielić na:
\(\displaystyle{ - ab + cd, ac + bd, ad + bc\\
- abc + d, abd + c, acd + b, bcd + a
}\)


Całość możesz przemnożyć przez \(\displaystyle{ k!}\) jeżeli kolejność zbiorów ma znaczenie.
Ostatnio zmieniony 9 mar 2022, o 14:25 przez Jan Kraszewski, łącznie zmieniany 1 raz.
Powód: Poprawa wiadomości.
Awatar użytkownika
arek1357
Użytkownik
Użytkownik
Posty: 5703
Rejestracja: 6 gru 2006, o 09:18
Płeć: Mężczyzna
Lokalizacja: blisko
Podziękował: 129 razy
Pomógł: 524 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: arek1357 »

Szczerze to nie bardzo rozumiem tych intencji,...

Jeżeli mamy zbiór:

\(\displaystyle{ X=\left\{ 1,2,3,...,n\right\} }\)

Podzbiór:

\(\displaystyle{ A=\left\{ x_{1},x_{2},...,x_{a}\right\} }\)

Podzbiór ten co ma być częścią wspólną dwóch podzbiorów, jego liczebność to: \(\displaystyle{ a}\)

I teraz produkujemy pary zbiorów:

\(\displaystyle{ M, N \subset X \setminus A, M \cap N=\emptyset, M \cup N=R, \emptyset \le R \le X \setminus A}\)

A par takich będzie:

\(\displaystyle{ {n-a \choose 0} +{n-a \choose 1} +...+{n-a \choose n-a} + \sum_{i=2}^{n-a} {n-a \choose i}S(i,2)=2^{n-a}+\sum_{i=2}^{n-a} {n-a \choose i}S(i,2) }\)

Weźmy przykład:

\(\displaystyle{ X=\left\{ 1,2,3,4\right\} }\)

\(\displaystyle{ A=\left\{ 4\right\} }\)

\(\displaystyle{ X \setminus A=\left\{ 1,2,3\right\} }\)

Mamy takie pary:

\(\displaystyle{ (M,N)=\left( \emptyset, \emptyset\right) ; \left( \left\{ 1\right\} , \emptyset \right); \left( \left\{ 2\right\} , \emptyset \right); \left( \left\{ 3\right\} , \emptyset \right); \left( \left\{ 1,2\right\} , \emptyset \right); \left( \left\{ 1,3\right\} , \emptyset \right); \left( \left\{ 2,3\right\} , \emptyset \right); \left( \left\{ 1,2,3\right\} , \emptyset \right); \left( \left\{ 1\right\} , \left\{ 2\right\} \right); \left( \left\{ 1\right\} , \left\{ 3\right\} \right);\left( \left\{ 2\right\} , \left\{ 3\right\} \right);\left( \left\{ 1,2\right\} , \left\{ 3\right\} \right);\left( \left\{ 1,3\right\} , \left\{ 2\right\} \right); \left( \left\{ 2,3\right\} , \left\{ 1\right\} \right)}\)

Co daje razem:

\(\displaystyle{ 14}\) możliwości

Teraz ze wzoru:

\(\displaystyle{ n=4, a=1, n-a=3}\)

Mamy:

\(\displaystyle{ 2^3+ \sum_{i=2}^{3} {3 \choose i}S(i,2)=8+ {3 \choose 2} S(2,2)+ {3 \choose 3} S(3,2)=8+3 \cdot 1+1 \cdot 3=8+3+3=14 }\)

\(\displaystyle{ S(2,2)=1, S(3,2)=3}\)

Oczywiście nie ma sensu już zliczać na odwrót czyli: \(\displaystyle{ (N,M)}\)

Dodano po 3 minutach 30 sekundach:
Problem z różnicą można analogicznie...

Oczywiście dla nieskończonych wychodzą też i nieprzeliczalne...

Dodano po 1 dniu 13 godzinach 52 minutach 19 sekundach:
ps:

Po skróceniu uproszczeniu wszystko się zwinie do:


\(\displaystyle{ \frac{1}{2}\left( 3^{n-a}+1\right) }\)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Jakub Gurak »

Jakub Gurak pisze: 7 mar 2022, o 21:27Ciekawi mnie też taki problem, że jeśli mamy zbiór oraz podzbiór, to na ile sposobów ten podzbiór można przedstawić w postaci różnicy dwóch podzbiorów całego zbioru.
Udało się dokładnie zbadać ten problem i wczoraj udało się go ukończyć. Przedstawię teraz rozwiązania tego ciekawego zadania.


Rozważmy zbiór \(\displaystyle{ X}\), oraz podzbiór \(\displaystyle{ A\subset X}\). Będziemy chcieli odpowiedzieć na pytanie, na ile sposobów podzbiór \(\displaystyle{ A}\) można przedstawić w postaci różnicy dwóch podzbiorów całego zbioru \(\displaystyle{ X}\), tzn. rozważamy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \left( B_1, B_2\right)\in P(X) \times P(X)\Bigl| \ \ B_1 \setminus B_2=A \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)


Podajmy najpierw dwa lematy:

LEMAT 1. Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{D}}\) rodzina wszystkich par podzbiorów zbioru \(\displaystyle{ X}\) na zbiory rozłączne, tzn.
\(\displaystyle{ }\)
\(\displaystyle{ \mathbb{D}=\left\{ \left( B_1,B_2\right)\in P(X) \times P(X)\Bigl| \ \ B_1 \cap B_2=\left\{ \right\} \right\}}\),

to \(\displaystyle{ \mathbb{D}\sim 3^X:= \left\{ 1,2,3\right\}^X.}\)

Dowód znajduje się w poprzednim moim poście- jest to tam Lemat 2.

I jeszcze jeden lemat:

LEMAT 2. Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to \(\displaystyle{ 3^X:=\left\{ 1,2,3\right\} ^X\sim 2^X}\).

Dowód znajduje się w poprzednim moim poście- jest to tam Lemat 3.


Przejdźmy do naszego zadania.

ROZWIĄZANIE:

Niech \(\displaystyle{ A'= X \setminus A}\).

Rozważmy rodzinę \(\displaystyle{ \mathbb{A}}\)- rodzinę wszystkich par podzbiorów tego dopełnienia \(\displaystyle{ A'}\) na zbiory rozłączne, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{A}}\), daną jako:

\(\displaystyle{ \mathbb{A}=\left\{ \left( B_1,B_2\right) \in P(A' ) \times P(A')\Bigl| \ \ B_1 \cap B_2=\left\{ \right\} \right\} .}\)

I pokażemy, że rodzina \(\displaystyle{ \mathbb{A}}\) jest równoliczna z naszą rodziną \(\displaystyle{ \mathbb{B}}\) (no bo skoro różnica tych dwóch podzbiorów ma dawać podzbiór \(\displaystyle{ A}\), to pierwszy zbiór musi zawierać zbiór \(\displaystyle{ A}\), istotna zatem jest jego część leżąca w dopełnieniu \(\displaystyle{ A'}\), a jeśli chodzi o drugi zbiór- po odjęciu niego od pierwszego zbioru, musi on wyrzucić tą część, a nie może nic wyrzucić ze zbioru \(\displaystyle{ A}\), bo wtedy taka różnica byłaby mniejsza od zbioru \(\displaystyle{ A}\), więc ten zbiór tez musi być rozłączny ze zbiorem \(\displaystyle{ A}\), i ponieważ trzeba wyrzucić część pierwszego zbioru, leżącą poza zbiorem \(\displaystyle{ A,}\) przez odjęcie drugiego zbioru, więc istotne są tylko takie 'kawałki rozłączne' ).


Wykażemy zatem, że \(\displaystyle{ \mathbb{A}\sim \mathbb{B}.}\)

W tym celu definiujemy funkcję:

\(\displaystyle{ \alpha : \mathbb{A} \rightarrow \mathbb{B}}\), daną jako:

\(\displaystyle{ \alpha \left( \left( B_1,B_2\right) \right)=\left( B_1 \cup A, B_1 \cup B_2\right).}\)

Jeśli \(\displaystyle{ \left( B_1, B_2\right) \in \mathbb{A}}\), to \(\displaystyle{ B_1, B_2 \subset A'}\), i zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\) są rozłączne.

Mamy \(\displaystyle{ B_1\subset A'\subset X}\), a wiec \(\displaystyle{ B_1\subset X}\), i mamy \(\displaystyle{ A\subset X}\), więc również \(\displaystyle{ B_1 \cup A\subset X.}\)

Mamy \(\displaystyle{ B_2\subset A'\subset X}\), a więc zarówno \(\displaystyle{ B_1, B_2\subset X}\), więc również suma \(\displaystyle{ B_1 \cup B_2\subset X.}\)

Wykażemy teraz, że:

\(\displaystyle{ \left( B_1 \cup A\right) \setminus \left( B_1 \cup B_2\right)=A.}\)

Mamy:

\(\displaystyle{ \left( B_1 \cup A\right) \setminus \left( B_1 \cup B_2\right)=\left[ \left( B_1 \cup A\right) \setminus B_1 \right] \cap \left[ \left( B_1 \cup A\right) \setminus B_2 \right] =\left[ \left( A \cup B_1\right) \setminus B_1 \right] \cap \left[ \left( B_1 \setminus B_2\right) \cup \left( A \setminus B_2\right) \right]= }\)

i ponieważ \(\displaystyle{ B_1\subset A'}\), wiec zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A}\) są rozłączne, a więc ta pierwsza część w nawiasie jest równa \(\displaystyle{ A}\), a więc to jest równe:

\(\displaystyle{ =A \cap \left[ \left( B_1 \setminus B_2\right) \cup \left( A \setminus B_2\right) \right] \stackrel{ C_1 \setminus C_2= C_1 \setminus \left( C_1 \cap C_2\right) }{=} A \cap \left[ \left( B_1 \setminus \left( B_1 \cap B_2\right) \right) \cup A \setminus \left( A \cap B _{2} \right) \right] =}\),

i ponieważ zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\) są rozłączne, tak więc \(\displaystyle{ B_1 \cap B_2=\emptyset}\), wiec to jest równe:

\(\displaystyle{ =A \cap \left[ \left( B_1 \setminus \emptyset\right) \cup \left( A \setminus \left( A \cap B_2\right) \right) \right]=}\)

i ponieważ \(\displaystyle{ B_2\subset A'}\), a więc zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B_2}\) są rozłączne, a więc \(\displaystyle{ A \cap B_2=\emptyset}\), więc to jest równe:

\(\displaystyle{ =A \cap \left[ \left( B_1 \setminus \emptyset\right) \cup \left( A \setminus \emptyset\right) \right] =A \cap \left( B_1 \cup A\right) =\left( A \cap B_1\right) \cup \left( A \cap A\right)=}\),

i ponieważ zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A}\) są rozłączne, tak więc \(\displaystyle{ A \cap B_1=\emptyset}\), więc to jest równe:

\(\displaystyle{ =\emptyset \cup A=A.}\)

Wykazaliśmy zatem , że:

\(\displaystyle{ \left( B_1 \cup A\right) \setminus \left( B_1 \cup B_2\right)=A.}\)

A zatem \(\displaystyle{ \alpha \left( B_1,B_2\right) =\left( B_1 \cup A, B_1 \cup B_2\right) \in \mathbb{B}}\), i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.


Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest róznowartościowa.

Jeśli (dla dowolnych par zbiorów \(\displaystyle{ \left( B_1,B_2\right); \left( C_1,C_2\right)\in \mathbb{A}}\)) mamy:

\(\displaystyle{ \alpha \left( B_1,B_2\right) = \alpha \left( C_1,C_2\right) }\), to z definicji funkcji \(\displaystyle{ \alpha}\) otrzymujemy:

\(\displaystyle{ \left( B_1 \cup A, B_1 \cup B_2\right)=\left( C_1 \cup A, C_1 \cup C_2\right)}\), skąd

\(\displaystyle{ B_1 \cup A= C_1 \cup A}\) i \(\displaystyle{ B_1 \cup B_2=C_1 \cup C_2. }\)

Rozważmy najpierw jedynie pierwszy składnik koniunkcji.

Wtedy, ponieważ para zbiorów \(\displaystyle{ (B_1,B_2)\in \mathbb{A}}\), więc \(\displaystyle{ B_1\subset A'}\), a więc zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A}\) są rozłączne, a zatem:

\(\displaystyle{ B_1=\left( B_1 \cup A\right) \setminus A=\left( C_1 \cup A\right) \setminus A}\),

i ponieważ para zbiorów \(\displaystyle{ \left( C_1,C_2\right) \in \mathbb{A}}\), a więc \(\displaystyle{ C_1\subset A'}\) , więc zbiory \(\displaystyle{ C_1}\) i \(\displaystyle{ A}\) są rozłączne, wobec czego \(\displaystyle{ \left( C_1 \cup A \right) \setminus A=C_1}\), a zatem \(\displaystyle{ C_1=B_1}\).

A ponieważ drugi składnik koniunkcji daje nam \(\displaystyle{ B_1 \cup B_2 =C_1 \cup C_2}\), to inaczej mówiąc daje: \(\displaystyle{ B_2 \cup B_1 =C_2 \cup C_1}\), i ponieważ zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\) są rozłączne, a zatem:

\(\displaystyle{ B_2=\left( B_2 \cup B_1\right) \setminus B_1=\left( C_2 \cup C_1\right) \setminus B_1\stackrel{B_1=C_1}{=} \left( C_2 \cup C_1\right) \setminus C_1= }\)

i ponieważ zbiory \(\displaystyle{ C_1}\) i \(\displaystyle{ C_2}\) są rozłączne, a więc to jest równe:

\(\displaystyle{ =C_2}\).

Wykazaliśmy zatem, że \(\displaystyle{ C_2=B_2}\).

Mamy również \(\displaystyle{ C_1=B_1}\), a zatem \(\displaystyle{ \left( B_1,B_2\right) =\left( C_1,C_2\right)}\), i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


Wykażemy teraz, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.

Niech \(\displaystyle{ \left( B_1,B_2\right) \in \mathbb{B}}\), wtedy \(\displaystyle{ B_1\subset X, B_2\subset X}\) i \(\displaystyle{ B_1 \setminus B_2=A}\).

Rozważmy parę zbiorów: \(\displaystyle{ \left( B_1 \setminus A, B_2 \setminus B_1 \right).}\) Wtedy \(\displaystyle{ B_1 \setminus A\subset B_1\subset X}\) i \(\displaystyle{ B_1 \setminus A\subset A'.}\)

Pokażemy, że również \(\displaystyle{ B_2 \setminus B_1\subset A'.}\)

Niech \(\displaystyle{ x\in B_2 \setminus B_1}\). Przypuśćmy dla dowodu nie wprost, że \(\displaystyle{ x\not\in A'=X \setminus A}\). Ale \(\displaystyle{ x\in B_2\subset X}\), wobec czego \(\displaystyle{ x\in X}\), wobec czego, na podstawie definicji różnicy zbiorów, musi być: \(\displaystyle{ x\in A=B_1 \setminus B_2}\), a więc \(\displaystyle{ x\in B_1}\), a mamy \(\displaystyle{ x \in B_2 \setminus B_1}\)-sprzeczność. Wobec czego musi być: \(\displaystyle{ x\in A'}\), i \(\displaystyle{ B_2 \setminus B_1\subset A'.}\)

Mamy również \(\displaystyle{ B_1 \setminus A\subset A'.}\)

Wykażemy teraz, że zbiory \(\displaystyle{ B_2 \setminus B_1}\) i \(\displaystyle{ B_1 \setminus A}\) są zbiorami rozłącznymi.
Przypuśćmy nie wprost, że tak nie jest, że \(\displaystyle{ \left( B_2 \setminus B_1\right) \cap \left( B_1 \setminus A\right) \neq \left\{ \right\}.}\) Istnieje wtedy element \(\displaystyle{ x \in\left( B_2 \setminus B_1\right) \cap \left( B_1 \setminus A\right)}\), wtedy \(\displaystyle{ x \in B_2 \setminus B_1}\), skąd \(\displaystyle{ x\not\in B_1;}\) i \(\displaystyle{ x \in B_1 \setminus A}\), skąd \(\displaystyle{ x\in B_1}\)- otrzymujemy więc sprzeczność.

A zatem zbiory \(\displaystyle{ B_2 \setminus B_1}\) i \(\displaystyle{ B_1 \setminus A}\) są zbiorami rozłącznymi.

A zatem para zbiorów \(\displaystyle{ \left( B_1 \setminus A, B_2 \setminus B_1\right)\in \mathbb{A}}\), i otrzymujemy:
\(\displaystyle{ }\)
\(\displaystyle{ \alpha \left( \left( B_1 \setminus A, B_2 \setminus B_1\right) \right)= \left(\left( B_1 \setminus A\right) \cup A, \left( B_1 \setminus A\right) \cup \left( B_2 \setminus B_1\right) \right)=}\),

i ponieważ \(\displaystyle{ B_1 \setminus B_2=A}\), a więc \(\displaystyle{ A=B_1 \setminus B_2\subset B_1}\), a więc pierwszy zbiór pary musi być równy zbiorowi \(\displaystyle{ B_1}\), a zatem ta para zbiorów jest równa:

\(\displaystyle{ =\left( B_1, \ \left( B_1 \setminus \left( B_1 \setminus B_2\right)\right) \cup \left( B_2 \setminus B_1 \ \right) \right)\stackrel{C_1 \setminus \left( C_1 \setminus C_2\right)=C_1 \cap C_2 }{=} \left( B_1, \ \left( B_1 \cap B_2\right) \cup \left( B_2 \setminus B_1\right) \ \right)=\left( B_1, B_2\right)}\), czyli


\(\displaystyle{ (B_1,B_2)= \alpha \left( \left( B_1 \setminus A\right) , B_2 \setminus B_1\right)}\),

czyli para zbiorów \(\displaystyle{ \left( B_1,B_2\right)}\) jest wartością funkcji \(\displaystyle{ \alpha}\) . Z dowolności wyboru takiej pary zbiorów otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.


A zatem funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

A zatem \(\displaystyle{ \mathbb{A}\sim \mathbb{B}}\). A na mocy Lematu 1 otrzymujemy \(\displaystyle{ \mathbb{A}\sim 3 ^{A'}=\left\{ 1,2,3 \right\} ^{A'}}\), czyli \(\displaystyle{ \mathbb{B}\sim 3 ^{A'}. }\)


Jeśli zatem zbiór \(\displaystyle{ A'}\) jest zbiorem skończonym \(\displaystyle{ n}\)-elementowym, to \(\displaystyle{ \left| \mathbb{B}\right| = 3 ^{n}.}\)

Jeśli zaś zbiór \(\displaystyle{ A'}\) jest zbiorem nieskończonym, to na mocy Lematu 2 otrzymujemy \(\displaystyle{ 3 ^{A'}\sim 2 ^{A'}}\), a zatem \(\displaystyle{ \left| \mathbb{B}\right|=2 ^{\left| A'\right| } .\square}\)


Podobnie jak w poprzednim problemie, tu również lepiej by było, gdybyśmy naszą poszukiwaną moc wyrazili w stosunku do mocy zbioru \(\displaystyle{ X}\) lub w stosunku do mocy podzbioru \(\displaystyle{ A}\), a nie w stosunku do mocy dopełnienia zbioru \(\displaystyle{ A}\). W wielu przypadkach uda się to zrobić.

Jeśli \(\displaystyle{ X}\) jest zbiorem skończonym \(\displaystyle{ n}\)-elementowym, a \(\displaystyle{ A\subset X}\) zbiorem \(\displaystyle{ m}\)-elementowym, gdzie \(\displaystyle{ m \le n}\), to \(\displaystyle{ \left| A'\right|=n-m}\), a zatem \(\displaystyle{ \left| \mathbb{B}\right|= 3 ^{n-m}.}\)

Jeśli zaś \(\displaystyle{ X}\) jest zbiorem nieskończonym, a \(\displaystyle{ A\subset X}\) podzbiorem mocy silnie mniejszej od mocy zbioru \(\displaystyle{ X}\). To dopełnienie \(\displaystyle{ A'}\) jest zbiorem nieskończonym.
DOWÓD TEGO FAKTU::    
Wobec czego zbiór \(\displaystyle{ A'}\) jest zbiorem nieskończonym, a wiec \(\displaystyle{ \left|\mathbb{B}\right|=2 ^{\left| A'\right| }.}\) Ale \(\displaystyle{ A'=X \setminus A}\), i \(\displaystyle{ \left| A\right|<\left| X\right|}\), i zbiór \(\displaystyle{ X}\) jest nieskończony, ponieważ zbiory nieskończone są odporne na ujmowanie od nich zbiorów mocy silnie mniejszej, co ostatnio udowodniłem TUTAJ, W OSTATNIM POŚCIE , więc \(\displaystyle{ A'=X \setminus A\sim X}\), a więc \(\displaystyle{ \left| \mathbb{B}\right|= 2 ^{\left| X\right| }.\square}\) :lol: 8-)

Można będzie jeszcze zbadać taki problem, gdy mamy zbiór, oraz podzbiór, to na ile sposobów ten podzbiór można przedstawić w postaci różnicy symetrycznej dwóch podzbiorów całego zbioru, ale ten problem już mnie tak bardzo nie ciekawi, zostawię go sobie na przyszłość. 8-)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Jakub Gurak »

Wczoraj zbadałem również i ten problem (ten powyższy).
Przedstawię teraz rezultaty tych dokonań:

Rozważmy zbiór \(\displaystyle{ X}\);
oraz rozważmy podzbiór \(\displaystyle{ A \subset X}\).
Zbadamy, na ile sposobów ten podzbiór można przedstawić w postaci różnicy symetrycznej dwóch podzbiorów całego zbioru.

Tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) daną jako:

\(\displaystyle{ \mathbb{B}= \left\{ \left( X_1, X_2\right) \in P\left( X\right) \times P\left( X\right)\Bigl| \ \ X_1\oplus X_2=A \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)

Wykażemy, że:

\(\displaystyle{ \left| \mathbb{B}\right| = 2 ^{\left| X\right| }.}\)

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ A'= X \setminus A.}\)

Wykażemy, że:

\(\displaystyle{ \mathbb{B}\sim P\left( A\right) \times P\left( A'\right).}\)

W tym celu definiujemy funkcję:

\(\displaystyle{ \alpha: P\left( A\right) \times P\left( A'\right) \rightarrow \mathbb{B}}\),

w następujący sposób:

Jeśli mamy parę zbiorów \(\displaystyle{ \left( B,C\right)}\), gdzie \(\displaystyle{ B \subset A, C \subset A',}\) to definiujemy zbiory :

\(\displaystyle{ B_1=B, B_2= A \setminus B,}\)

a następnie definiujemy zbiory:

\(\displaystyle{ X_1= B_1 \cup C,}\)
\(\displaystyle{ X_2= B_2 \cup C.}\)

Ponieważ \(\displaystyle{ B_1 \subset A \subset X}\) i \(\displaystyle{ C \subset X}\), więc \(\displaystyle{ X_1 \subset X}\),
i w podobny sposób otrzymujemy, że: \(\displaystyle{ X_2 \subset X}\), a zatem \(\displaystyle{ \left( X_1, X_2\right) \in P(X) \times P(X)}\).

Wykażemy, że różnica symetryczna tych dwóch zbiorów daje nasz podzbiór \(\displaystyle{ A}\).
DOWÓD TEGO 'OCZYWISTEGO' FAKTU::    
A zatem:

\(\displaystyle{ \left( X_1, X_2\right) \in \mathbb{B}}\), i funkcja:

\(\displaystyle{ \alpha: P\left( A\right) \times P\left( A' \right) \rightarrow \mathbb{B},}\)

jest dobrze określona.


Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

Wykażemy, że jest to funkcja różnowartościowa.

W tym celu weźmy dwie różne pary zbiorów \(\displaystyle{ \left( B', C' \right)}\) i \(\displaystyle{ \left( B'', C''\right)}\), gdzie \(\displaystyle{ B' , B'' \subset A}\) i \(\displaystyle{ C', C'' \subset A'}\), i pokażmy, że przypisane im pary zbiorów \(\displaystyle{ \left( X'_1, X'_2\right)}\) i \(\displaystyle{ \left( X''_1, X''_2\right)}\) są różne.

Jeśli \(\displaystyle{ C' \neq C''}\), to ponieważ \(\displaystyle{ C',C'' \subset A'}\), a \(\displaystyle{ B', B'' \subset A}\), więc \(\displaystyle{ X'_1= B' \cup C' \neq B'' \cup C''= X''_1}\), a więc \(\displaystyle{ \left( X'_1, X'_2\right) \neq \left( X''_1, X''_2\right)}\), co należało pokazać.

Jeśli \(\displaystyle{ C'=C''}\), oznaczmy ten zbiór jako \(\displaystyle{ C}\), wtedy musi być \(\displaystyle{ B' \neq B''.}\)

A wtedy:

\(\displaystyle{ X'_1= B'_1 \cup C'= B' \cup C}\), a
\(\displaystyle{ X''_1=B'' \cup C,}\)

więc ponieważ \(\displaystyle{ B', B'' \subset A, C \subset A'}\), i \(\displaystyle{ B' \neq B''}\), więc również \(\displaystyle{ X'_1 \neq X''_1}\), co należało pokazać.

A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.

Niech \(\displaystyle{ \left( X_1, X_2\right) \in \mathbb{B}.}\)
Wtedy \(\displaystyle{ X_1, X_2 \subset X}\) i \(\displaystyle{ X_1\oplus X_2=A.}\)

Zdefiniujmy zbiory:

\(\displaystyle{ B= X_1 \setminus X_2 \subset \left( X_1 \setminus X_2\right) \cup \left( X_2 \setminus X_1\right) = X_1\oplus X_2=A}\),i
\(\displaystyle{ C=X_1 \cap X_2.}\)

Ponieważ:

\(\displaystyle{ A= X_1\oplus X_2= \left( X_1 \cup X_2\right) \setminus \left( X_1 \cap X_2\right)}\), to:

\(\displaystyle{ C= X_1 \cap X_2 \subset A' =X \setminus A.}\)

I wtedy:

\(\displaystyle{ \alpha \left( B,C\right) =\left( B \cup C, \left( A \setminus B\right) \cup C \right).}\)

Wtedy:

\(\displaystyle{ B \cup C= \left( X_1 \setminus X_2\right) \cup \left( X_1 \cap X_2\right)= X_1,}\) a:

\(\displaystyle{ \left( A \setminus B\right) \cup C= \left[ A \setminus \left( X_1 \setminus X_2\right) \cup \left( X_1 \cap X_2\right) \right] \stackrel{X_1\oplus X_2=A}{=} \left[ \left( X_1\oplus X_2\right) \setminus \left( X_1 \setminus X_2\right) \right] \cup \left( X_1 \cap X_2\right) = \\=\left[ \left( \left( X_2 \setminus X_1\right) \cup \left( X_1 \setminus X_2\right) \right) \setminus \left( X_1 \setminus X_2\right) \right] \cup \left( X_1 \cap X_2\right) =}\)

więc ponieważ zbiory \(\displaystyle{ X_2 \setminus X_1}\) i \(\displaystyle{ X_1 \setminus X_2}\) są rozłączne, więc to jest równe:

\(\displaystyle{ = \left( X_2 \setminus X_1\right) \cup \left( X_1 \cap X_2\right)= \left( X_2 \setminus X_1\right) \cup \left( X_2 \cap X_1\right) =X_2.}\)

A zatem:

\(\displaystyle{ \alpha \left( B,C\right)= \left( X_1, X_2\right),}\)

a więc para zbiorów \(\displaystyle{ \left( X_1, X_2\right)}\) jest wartością funkcji \(\displaystyle{ \alpha}\).
Z dowolności wyboru takiej pary, otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.


A zatem:

\(\displaystyle{ P\left( A\right) \times P\left( A'\right) \sim \mathbb{B}.}\)

Jeśli zatem zbiór \(\displaystyle{ X}\) jest skończony, i ma \(\displaystyle{ n}\) elementów, a jego podzbiór \(\displaystyle{ A}\) ma
\(\displaystyle{ m}\)-elementów, gdzie \(\displaystyle{ m \le n}\), to:

\(\displaystyle{ \left| \mathbb{B}\right|= 2 ^{m} \cdot 2 ^{n-m}= 2 ^{n}.}\)

A jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to ponieważ \(\displaystyle{ A' \subset X}\), więc rozważmy dwa przypadki:

Jeśli \(\displaystyle{ \left| A'\right|= \left| X\right|}\).

Wtedy \(\displaystyle{ \left| P\left( A'\right) \right|= 2 ^{\left| X\right| }.}\)

A zatem:

\(\displaystyle{ \left| \mathbb{B}\right|= 2 ^{\left| X\right| }.}\)

W przeciwnym przypadku mamy silną nierówność mocy zbiorów: \(\displaystyle{ \left| A'\right|< \left| X\right|}\).

A wtedy:

\(\displaystyle{ A= X \setminus \left( A'\right)}\) , i ponieważ zbiór \(\displaystyle{ X}\) jest nieskończony, więc jest odporny na ujmowanie zbiorów mocy silnie mniejszej od niego, więc \(\displaystyle{ A=X \setminus A' \sim X}\), czyli \(\displaystyle{ \left| A\right|= \left| X\right|}\), a zatem: \(\displaystyle{ \left| P\left( A\right) \right| = 2 ^{\left| X\right| }}\), i moc naszej rodziny jest równa \(\displaystyle{ \left| \mathbb{B}\right| = 2 ^{\left| X\right| } }\), i to w każdym przypadku, również w przypadku, gdy zbiór \(\displaystyle{ X}\) jest skończony.\(\displaystyle{ \square}\)

Czyli jeśli mamy zbiór \(\displaystyle{ X}\), oraz mamy podzbiór tego zbioru, to ten podzbiór można przedstawić w postaci różnicy symetrycznej dwóch podzbiorów całego zbioru na \(\displaystyle{ 2 ^{\left| X\right| }}\) sposobów.\(\displaystyle{ \square}\) 8-)


Pasuje jeszcze zastanowić się nad takim problemem, że jeśli mamy zbiór \(\displaystyle{ X}\), oraz mamy podzbiór \(\displaystyle{ A \subset X}\), to na ile sposobów podzbiór \(\displaystyle{ A}\) można przedstawić w postaci dopełnienia pewnego podzbioru \(\displaystyle{ B \subset X}\), tzn. tak aby \(\displaystyle{ A= B' =X \setminus B}\) :?:

To jednak jest proste, można to zawsze zrobić na dokładnie jeden sposób:

Bierzemy zbiór \(\displaystyle{ B=A' \subset X}\),

i wtedy:

\(\displaystyle{ B' = \left( A'\right) '=A}\),

a więc udało nam się przedstawić zbiór \(\displaystyle{ A}\) w powyższy sposób.

I jest to tylko jeden sposób:

Bo jeśli \(\displaystyle{ A= B'_1= B'_2}\), gdzie \(\displaystyle{ B_1 \subset X, B_2 \subset X}\), to:

\(\displaystyle{ B_1=\left( B'_1\right) '= A'= \left( B'_2\right) '= B_2,}\)

czyli zawsze podzbiór \(\displaystyle{ A}\) można przedstawić w postaci dopełnienia w co najwyżej jeden sposób, i zawsze można to zrobić w dokładnie jeden sposób. \(\displaystyle{ \square}\) :lol:
Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 10211
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 40 razy
Pomógł: 2359 razy

Re: Ilość przedstawień zbioru w postaci sumy dwóch podzbiorów

Post autor: Dasio11 »

Jakub Gurak pisze: 10 wrz 2023, o 21:04Tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) daną jako:

\(\displaystyle{ \mathbb{B}= \left\{ \left( X_1, X_2\right) \in P\left( X\right) \times P\left( X\right)\Bigl| \ \ X_1\oplus X_2=A \right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)
\(\displaystyle{ (P(X), \oplus)}\) jest grupą, więc dla każdego \(\displaystyle{ X_1 \in P(X)}\) istnieje dokładnie jeden \(\displaystyle{ X_2 \in P(X)}\), taki że \(\displaystyle{ X_1 \oplus X_2 = A}\). Stąd rzut na pierwszą współrzędną \(\displaystyle{ \pi : \mathbb{B} \to P(X)}\) jest bijekcją, czyli \(\displaystyle{ |\mathbb{B}| = 2^{|X|}}\).
ODPOWIEDZ