Rozkłady zbioró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

Rozkłady zbiorów

Post autor: Jakub Gurak »

Wczoraj wieczorem udowodniłem, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a rodzina \(\displaystyle{ \mathbb{B}}\) rozkładem zbioru \(\displaystyle{ X}\), a \(\displaystyle{ Y}\) niepustym podzbiorem zbioru \(\displaystyle{ X}\), to rodzina niepustych podzbiorów zbioru \(\displaystyle{ Y}\), które są postaci przekrojów zbiorów z rozkładu \(\displaystyle{ \mathbb{B}}\) przekrojonych do zbioru \(\displaystyle{ Y}\), taka rodzina jest rozkładem zbioru \(\displaystyle{ Y}\). Przedstawię teraz dowód tego faktu.

DOWÓD:

Niech

\(\displaystyle{ \mathbb{B}_Y=\left\{ \ \ \left\{ \right\} \neq A\subset Y: A=B\cap Y, B\in\mathbb{B} \right\}.}\)

Niewątpliwie jest to rodzina podzbiorów zbioru \(\displaystyle{ Y}\) . Aby wykazać, że jest rozkładem musimy w pierwszym punkcie wykazać, że \(\displaystyle{ \bigcup \mathbb{B}_Y=Y}\). Niewątpliwie mamy:

\(\displaystyle{ \bigcup\mathbb{B}_Y= \bigcup_{A\in\mathbb{B}_Y } A= \bigcup_{B\in\mathbb{B}}\left( B\cap Y\right) =\left( \bigcup_{B\in\mathbb{B}} B \right)\cap Y= \bigcup\mathbb{B}\cap Y=X\cap Y=Y}\), gdzie przedostatnia równość wynika stąd, że rodzina \(\displaystyle{ \mathbb{B}}\) jest rozkładem zbioru \(\displaystyle{ X}\), tak więc \(\displaystyle{ \bigcup\mathbb{B}=X}\), a ostatnia stąd, że \(\displaystyle{ Y\subset X.}\) Otrzymujemy zatem \(\displaystyle{ \bigcup\mathbb{B}_Y=Y.}\)

Należy teraz pokazać, że każde dwa różne zbiory z rodziny \(\displaystyle{ \mathbb{B}_Y}\) są rozłączne. Niech zatem \(\displaystyle{ A_1,A_2\in \mathbb{B}_Y}\), będą różnymi zbiorami- \(\displaystyle{ A_1 \neq A_2}\). Wtedy \(\displaystyle{ A_1,A_2}\) są niepustymi podzbiorami zbioru \(\displaystyle{ Y}\), i \(\displaystyle{ A_1=B_1\cap Y}\), gdzie \(\displaystyle{ B_1\in\mathbb{B}}\), i \(\displaystyle{ A_2=B_2\cap Y}\), gdzie \(\displaystyle{ B_2\in\mathbb{B}}\). Aby wykazać, że zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne wyznaczmy przekrój \(\displaystyle{ A_1\cap A_2}\):

\(\displaystyle{ A_1\cap A_2=(B_1\cap Y)\cap (B_2\cap Y)=(B_1\cap B_2)\cap (Y\cap Y)=B_1\cap B_2\cap Y=}\) teraz ponieważ \(\displaystyle{ B_1,B_2\in\mathbb{B},}\) więc jeśli \(\displaystyle{ B_1 \neq B_2}\), to zbiory \(\displaystyle{ B_1,B_2}\) jako różne zbiory rozkładu \(\displaystyle{ \mathbb{B} }\) są rozłączne, a zatem\(\displaystyle{ B_1\cap B_2=\emptyset}\), i w efekcie (kontynuujemy równości), więc to jest równe \(\displaystyle{ =\emptyset\cap Y=\emptyset.}\) Tak więc \(\displaystyle{ A_1\cap A_2=\emptyset}\), i zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne. Pozostaje do rozważenia przypadek \(\displaystyle{ B_1=B_2}\), ale on łatwo prowadzi do sprzeczności, gdyż jeśli oznaczymy \(\displaystyle{ B_1=B_2=B}\), to \(\displaystyle{ A_1=B\cap Y, A_2=B\cap Y}\), tak więc \(\displaystyle{ A_1=A_2}\)- sprzeczność z założeniem. Zatem ten przypadek jest niemożliwy, i zbiory \(\displaystyle{ A_1,A_2}\) muszą być rozłączne.

Pozostaje wykazać, ze każdy zbiór z rodziny \(\displaystyle{ \mathbb{B}_Y}\) jest niepusty; wynika to od razu z określenia rodziny \(\displaystyle{ \mathbb{B}_Y.}\) Tak więc rodzina \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem zbioru \(\displaystyle{ Y.\square}\) :D

Zachodzi też ciekawy fakt, że suma dwóch rozkładów na zbiorach rozłącznych jest rozkładem w sumie tych dwóch zbiorów na których są określone te dwa rozkłady, co udowodniłem TUTAJ, W DRUGIM POŚCIE. Mamy też ciekawy fakt, że każdy rozkład, gdy popatrzymy na jego moc , to jest ona co najwyżej taka jak moc zbioru na którym jest określony ten rozkład (wystarczy zbiorowi rozkładu przypisać jego jeden element, niestety, w ogólności, chyba potrzeba tu aksjomatu wyboru).
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: Rozkłady zbiorów

Post autor: Jakub Gurak »

W podanym powyżej linku, w poście poniżej, jest udowodniony też taki ciekawy fakt, że jeśli mamy rodzinę rozkładów na podzbiorach zbioru \(\displaystyle{ X}\), taką, że dla dowolnych dwóch rozkładów tej rodziny jeden się zawiera w drugim, to suma tych rozkładów jest rozkładem w sumie zbiorów na których są określone te rozkłady. Ten ciekawy fakt jest tam udowodniony, polecam.

Wczoraj na dobranoc sobie udowodniłem, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a rodzina \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem w \(\displaystyle{ X}\), \(\displaystyle{ Y}\) jest niepustym zbiorem, a rodzina \(\displaystyle{ \mathbb{B}_Y}\) rozkładem w \(\displaystyle{ Y}\), to rodzina zbiorów postaci \(\displaystyle{ A\times B}\), gdzie \(\displaystyle{ A}\) jest zbiorem z pierwszego rozkładu, a \(\displaystyle{ B}\) jest zbiorem z drugiego rozkładu, rodzina takich prostokątów kartezjańskich tworzy rozkład w \(\displaystyle{ X\times Y}\), co przedstawia ilustracja Myślę, że to bardzo ciekawe. Udowodniłem też, że moc takiego rozkładu jest równa mocy pierwszego rozkładu razy moc drugiego rozkładu, ściślej rzecz biorąc, taka rodzina, oznaczmy ją \(\displaystyle{ \mathbb{S}}\), jest równoliczna z \(\displaystyle{ \mathbb{B}_X\times\mathbb{B}_Y}\). Przedstawię teraz dowody tych ciekawych faktów.

Przypominam, dla dowolnych czterech zbiorów \(\displaystyle{ A,B,C,D,}\) mamy: \(\displaystyle{ (A \times B) \cap (C \times D)=\left( A \cap C\right) \times \left( B \cap D\right) }\)- przekrój dwóch iloczynów kartezjańskich jest iloczynem kartezjańskim,i to postaci- przekrój pierwszych składowych iloczynu kartezjańskiego razy przekrój drugich składowych, to można łatwo udowodnić.

Przypominam, jeśli \(\displaystyle{ \mathbb{B} }\) jest rodziną zbiorów, a \(\displaystyle{ A}\) jest zbiorem, to mamy prawo:

\(\displaystyle{ \left( \bigcup\mathbb{B}\right) \times A= \bigcup_{B\in\mathbb{B}} (B \times A)}\), oraz mamy prawo:

\(\displaystyle{ A \times \left( \bigcup\mathbb{B}\right) = \bigcup_{B\in\mathbb{B} } (A \times B).}\)

Te fakty można (w miarę prosto) udowodnić. Przejdźmy zatem do naszych dowodów:

Dowód:

Niech:

\(\displaystyle{ \mathbb{S}=\left\{ A \times B\Bigl| \ \ A\in\mathbb{B}_X, B\in\mathbb{B}_Y \right\}.}\)

Wykażemy, że rodzina \(\displaystyle{ \mathbb{S}}\) tworzy rozkład w \(\displaystyle{ X \times Y.}\)

Zauważmy najpierw, że \(\displaystyle{ \mathbb{S}}\) jest rodziną podzbiorów \(\displaystyle{ X \times Y}\), gdyż jeśli \(\displaystyle{ C\in \mathbb{S}}\), to \(\displaystyle{ C=A \times B}\), gdzie \(\displaystyle{ A\in \mathbb{B}_X, B\in\mathbb{B}_Y.}\) Ponieważ \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem zbioru \(\displaystyle{ X}\), a więc rodziną podzbiorów \(\displaystyle{ X}\), więc \(\displaystyle{ A\subset X}\), podobnie ponieważ \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem \(\displaystyle{ Y}\), to \(\displaystyle{ B\subset Y}\), a zatem \(\displaystyle{ C=A \times B\subset X \times Y}\). A zatem \(\displaystyle{ \mathbb{S}}\) jest rodziną podzbiorów \(\displaystyle{ X \times Y.}\)


Aby wykazać, że rodzina \(\displaystyle{ \mathbb{S}}\) jest rozkładem w \(\displaystyle{ X \times Y}\), należy po pierwsze wykazać, że \(\displaystyle{ \bigcup\mathbb{S}=X \times Y}\). A zatem, otrzymujemy:
\(\displaystyle{ \bigcup\mathbb{S}=\bigcup_{A\in \mathbb{B}_X, B\in\mathbb{B}_Y } \left( A \times B\right) = \bigcup_{A\in\mathbb{B}_X}\left( \bigcup_{B\in\mathbb{B}_Y} \left( A \times B\right) \right)= \bigcup_{B\in\mathbb{B}_Y} \left( \bigcup_{A\in\mathbb{B}_X} (A \times B)\right)= \bigcup_{B\in\mathbb{B}_Y} \left( \left( \bigcup_{A\in\mathbb{B}_X} A \right) \times B \right) =}\)
(skorzystaliśmy z przytoczonego prawa odnośnie tego czym jest suma rodziny zbiorów razy dany zbiór), i dalej, otrzymujemy, że to jest równe:

\(\displaystyle{ = \bigcup_{B\in\mathbb{B}_Y} \left( \left( \bigcup \mathbb{B}_X\right) \times B \right)= }\) i ponieważ rodzina \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem w zbiorze \(\displaystyle{ X}\), więc \(\displaystyle{ \bigcup\mathbb{B}_X=X}\), a zatem to jest równe

\(\displaystyle{ = \bigcup_{B\in\mathbb{B}_Y} (X \times B)=X \times \left( \bigcup_{B\in\mathbb{B}_Y} B \right) =X \times \left( \bigcup \mathbb{B}_Y \right)=}\) i ponieważ rodzina \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem w \(\displaystyle{ Y}\), więc \(\displaystyle{ \bigcup\mathbb{B}_Y=Y}\), a więc to jest równe \(\displaystyle{ X \times Y}\), tak więc \(\displaystyle{ \bigcup\mathbb{S}=X \times Y.}\)

Należy teraz pokazać, że każde dwa różne zbiory z \(\displaystyle{ \mathbb{S}}\) są rozłączne. Niech zatem \(\displaystyle{ C_1,C_2\in \mathbb{S}, C_1 \neq C_2}\). Wtedy \(\displaystyle{ C_1=A_1 \times B_1}\), gdzie \(\displaystyle{ A_1\in\mathbb{B}_X, B_1\in\mathbb{B}_Y}\), \(\displaystyle{ C_2=A_2 \times B_2}\), gdzie \(\displaystyle{ A_2\in\mathbb{B}_X, B_2\in\mathbb{B}_Y.}\) Ponieważ \(\displaystyle{ C_1 \neq C_2}\), to te dwa iloczyny kartezjańskie są różne, więc \(\displaystyle{ A_1 \neq A_2}\) lub \(\displaystyle{ B_1 \neq B_2}\), (gdyż dla dwóch zbiorów istnieje dokładnie jeden ich iloczyn kartezjański). Aby wykazać, że zbiory \(\displaystyle{ C_1, C_2}\) są rozłączne, wyznaczmy przekrój \(\displaystyle{ C_1 \cap C_2.}\) Mamy

\(\displaystyle{ C_1 \cap C_2=\left( A_1 \times B_1\right) \cap \left( A_2\times B_2\right) =\left( A_1 \cap A_2\right) \times \left( B_1 \cap B_2\right). }\) Wiemy, że \(\displaystyle{ A_1 \neq A_2 }\) lub \(\displaystyle{ B_1 \neq B_2}\). Rozważmy zatem przypadek \(\displaystyle{ A_1 \neq A_2}\), wtedy ponieważ \(\displaystyle{ A_1,A_2\in\mathbb{B}_X}\), a \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem, oraz \(\displaystyle{ A_1 \neq A_2}\), więc zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne, a zatem \(\displaystyle{ A_1 \cap A_2=\emptyset}\), a zatem \(\displaystyle{ C_1 \cap C_2=\left( A_1 \cap A_2\right) \times \left( B_1 \cap B_2\right)=\emptyset \times \left( B_1 \cap B_2\right)=\emptyset}\), a zatem zbiory \(\displaystyle{ C_1,C_2}\) są rozłączne. Jeśli \(\displaystyle{ B_1 \neq B_2}\) to rozumujemy analogicznie, zatem każde dwa różne zbiory z \(\displaystyle{ \mathbb{S}}\) są rozłączne.

Pozostaje pokazać, że każdy zbiór z \(\displaystyle{ \mathbb{S}}\) jest niepusty. W tym celu niech \(\displaystyle{ C\in\mathbb{S}.}\) Wtedy \(\displaystyle{ C=A \times B}\), gdzie \(\displaystyle{ A\in\mathbb{B}_X, B\in\mathbb{B}_Y.}\) Ponieważ \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem, więc zbiór \(\displaystyle{ A\in\mathbb{B}_X}\) jest niepusty, istnieje więc \(\displaystyle{ a\in A}\). Ponieważ \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem, więc zbiór \(\displaystyle{ B\in\mathbb{B}_Y}\) jest niepusty, istnieje więc \(\displaystyle{ b\in B}\), wtedy \(\displaystyle{ (a,b)\in A\times B=C}\), a więc zbiór \(\displaystyle{ C}\) jest niepusty, i otrzymujemy, że każdy zbiór z \(\displaystyle{ \mathbb{S}}\) jest niepusty.

Zatem rodzina \(\displaystyle{ \mathbb{S}}\) jest rozkładem w \(\displaystyle{ X \times Y}\).


Wykażemy teraz, że rozkład \(\displaystyle{ \mathbb{S}}\) jest równoliczny z iloczynem kartezjańskim rozkładu \(\displaystyle{ \mathbb{B}_X}\) i rozkładu \(\displaystyle{ \mathbb{B}_Y}\)- \(\displaystyle{ \mathbb{S}\sim\mathbb{B}_X \times \mathbb{B}_Y.}\)

Dowód:

Zdefiniujmy funkcję \(\displaystyle{ f:\mathbb{B}_X \times \mathbb{B}_Y \rightarrow \mathbb{S}}\), jako:

\(\displaystyle{ f(A,B)=A \times B.}\)

Oczywiście funkcja \(\displaystyle{ f}\) jest dobrze określona.

Aby pokazać, że funkcja \(\displaystyle{ f}\) jest różnowartościowa, to niech \(\displaystyle{ (A_1,B_1);(A_2,B_2)\in \mathbb{B}_X \times \mathbb{B}_Y}\), będą różnymi parami zbiorów- \(\displaystyle{ \left( A_1,B_1\right) \neq \left( A_2,B_2\right).}\) A zatem \(\displaystyle{ A_1 \neq A_2}\) lub \(\displaystyle{ B_1 \neq B_2. }\) Zauważmy, że

\(\displaystyle{ f(A_1,B_1) \cap f(A_2, B_2)=\left( A_1 \times B_1\right) \cap \left( A_2 \times B_2\right)=\left( A_1 \cap A_2\right) \times \left( B_1 \cap B_2\right),}\)

teraz, wiemy, że \(\displaystyle{ A_1 \neq A_2}\) lub \(\displaystyle{ B_1 \neq B_2}\), więc jeśli \(\displaystyle{ A_1 \neq A_2}\), to ponieważ \(\displaystyle{ A_1,A_2\in\mathbb{B}_X }\), a \(\displaystyle{ \mathbb{B}_X }\) jest rozkładem, oraz \(\displaystyle{ A_1 \neq A_2}\), wiec zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne, a zatem \(\displaystyle{ A_1 \cap A_2=\emptyset}\), a zatem \(\displaystyle{ f(A_1,B_1) \cap f(A_2,B_2)= \left( A_1 \cap A_2\right) \times \left( B_1 \cap B_2\right)=\emptyset \times (B_1 \cap B_2)=\emptyset, }\)

zatem zbiory \(\displaystyle{ f(A_1,B_1); f(A_2,B_2)}\) są rozłączne, niepuste (jako zbiory z rozkładu \(\displaystyle{ \mathbb{S}}\)) zatem różne , czyli \(\displaystyle{ f(A_1,B_1) \neq f(A_2,B_2).}\)
Jeśli \(\displaystyle{ B_1 \neq B_2,}\) to rozumujemy analogicznie.

A zatem funkcja \(\displaystyle{ f}\) jest różnowartościowa. Oczywiście, łatwo sprawdzić, że jest 'na', zatem \(\displaystyle{ f}\) jest bijekcją. A zatem \(\displaystyle{ \mathbb{S}\sim \mathbb{B}_X \times \mathbb{B}_Y.\square }\):lol: 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: Rozkłady zbiorów

Post autor: Jakub Gurak »

Udowodniłem ostatnio fakt, potwierdzający intuicję, że gdy mamy niepusty zbiór \(\displaystyle{ X}\), i rodzinę rozkładów w \(\displaystyle{ X}\), to gdyby narysować te wszystkie rozkłady na jednym rysunku, to utworzone najmniejsze przekroje (najmniejsze kawałki) utworzą rozkład zbioru \(\displaystyle{ X}\). Dla mnie jest to strasznie ciekawe. :D Udowodniłem też w ostatni poniedziałek, że jeśli \(\displaystyle{ X}\) jest zbiorem , \(\displaystyle{ \mathbb{S}}\) jest rodziną rozkładów w \(\displaystyle{ X}\),a \(\displaystyle{ \mathcal R\in\mathbb{S} }\) jest rozkładem tej rodziny, a \(\displaystyle{ A\in\mathcal R}\) jest zbiorem tego rozkładu, to zbiór \(\displaystyle{ A}\) można dalej rozłożyć na zbiory z rozkładu \(\displaystyle{ \mathbb{B}_0}\)( tego rozkładu powyżej na najdrobniejsze przekroje mnogościowe). Udowodniłem też, że jeśli \(\displaystyle{ X}\) jest zbiorem niepustym, a \(\displaystyle{ \mathbb{B}_1, \mathbb{B}_2}\) są rozkładami w \(\displaystyle{ X}\), to rodzina niepustych zbiorów postaci \(\displaystyle{ A \cap B}\), gdzie \(\displaystyle{ A}\) są zbiorami z pierwszego rozkładu \(\displaystyle{ \mathbb{B}_1}\), a \(\displaystyle{ B}\) są zbiorami z drugiego rozkładu- to rodzina takich niepustych przekrojów mnogościowych tworzy rozkład w \(\displaystyle{ X}\). Uogólniłem na sytuację dwóch prawie dowolnych zbiorów, tzn. takich które się przecinają, czyli gdy te dwa zbiory nie są rozłączne, i gdy w pierwszym zbiorze mamy jeden rozkład, w drugim zbiorze mamy drugi rozkład, to w podobny sposób w przekroju \(\displaystyle{ X \cap Y}\) można zadać rozkład. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X \neq \left\{ \right\}}\) będzie niepustym zbiorem, a rodziny \(\displaystyle{ \mathbb{B}_1, \mathbb{B}_2}\) rozkładami zbioru \(\displaystyle{ X.}\) Wykażemy, że rodzina:

\(\displaystyle{ \mathbb{B}=\left\{ A \cap B\Bigl| \ \ A\in\mathbb{B}_1, B\in\mathbb{B}_2 \right\} \setminus \left\{ \emptyset\right\} }\),

jest rozkładem w \(\displaystyle{ X}\).

(Jakby to zilustrować, to te dwa dane rozkłady rysujemy jeden na drugim, i otrzymane najmniejsze przekroje (najmniejsze kawałki) tworzą ten właśnie rozkład). Przedstawię teraz dowód tego ciekawego faktu:

Zauważmy najpierw, że rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), gdyż jeśli mamy zbiór \(\displaystyle{ A\in\mathbb{B}_1}\), i gdy mamy zbiór \(\displaystyle{ B\in\mathbb{B}_2}\), ponieważ \(\displaystyle{ \mathbb{B}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\) (więc jest rodziną podzbiorów zbioru \(\displaystyle{ X}\)), więc \(\displaystyle{ A\subset X}\), ponieważ \(\displaystyle{ A \cap B\subset A\subset X}\), więc \(\displaystyle{ A \cap B\subset X}\), i rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X.}\)

Wykażemy teraz, że rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów rozłącznych.

Niech \(\displaystyle{ C_1,C_2\in\mathbb{B}}\) będą takimi zbiorami, że \(\displaystyle{ C_1 \cap C_2 \neq \left\{ \right\}}\), których przekrój jest niepusty, które się przecinają. Pokażemy, że \(\displaystyle{ C_1=C_2}\). Z definicji rodziny \(\displaystyle{ \mathbb{B}}\) otrzymujemy: \(\displaystyle{ C_1=A_1 \cap A_2}\), gdzie \(\displaystyle{ A_1\in\mathbb{B}_1, A_2\in\mathbb{B}_2}\), i podobnie \(\displaystyle{ C_2=B_1 \cap B_2}\), gdzie \(\displaystyle{ B_1 \in \mathbb{B}_1, B_2\in\mathbb{B}_2. }\) Ponieważ \(\displaystyle{ C_1 \cap C_2 \neq \left\{ \right\}}\) , więc istnieje element \(\displaystyle{ x\in C_1 \cap C_2. }\) Wtedy \(\displaystyle{ x\in C_1}\), \(\displaystyle{ x\in C_2}\), zatem \(\displaystyle{ x\in A_1,A_2}\), i \(\displaystyle{ x\in B_1,B_2}\), a zatem \(\displaystyle{ x\in A_1 \cap B_1}\), a \(\displaystyle{ A_1,B_1\in \mathbb{B}_1}\), i rodzina \(\displaystyle{ \mathbb{B}_1}\) jest rozkładem, więc (z warunku rozłączności zbiorów) otrzymujemy: \(\displaystyle{ A_1=B_1.}\) W podobny sposób uzasadniamy, że \(\displaystyle{ A_2=B_2.}\) A zatem \(\displaystyle{ C_1=A_1 \cap A_2=B_1 \cap B_2=C_2}\), czyli \(\displaystyle{ C_1=C_2}\). A zatem rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów rozłącznych.

Wykażemy teraz, że \(\displaystyle{ \bigcup\mathbb{B}=X}\). Niewątpliwie, mamy:

\(\displaystyle{ \bigcup\mathbb{B}= \bigcup_{A\in\mathbb{B}_1, B\in\mathbb{B}_2} \left( A \cap B\right) = \bigcup_{A\in\mathbb{B}_1} \left[ \bigcup_{B\in\mathbb{B}_{2}} \left( A \cap B\right) \right] = \bigcup_{A\in \mathbb{B}_1} \left[ \bigcup_{B\in\mathbb{B}_2} \left( B \cap A\right) \right] = \bigcup_{A\in\mathbb{B}_1} \left[ \left( \bigcup_{B\in\mathbb{B}_2} B\right) \cap A\right]= \bigcup_{A\in\mathbb{B}_1}\left( \bigcup\mathbb{B}_2 \cap A\right) =}\) i ponieważ rodzina \(\displaystyle{ \mathbb{B}_2}\) jest rozkładem zbioru \(\displaystyle{ X}\), tak więc \(\displaystyle{ \bigcup\mathbb{B}_2=X}\), więc to jest równe: \(\displaystyle{ \bigcup_{A\in\mathbb{B}_1} \left( X \cap A\right) }\), i teraz zauważmy, że jeśli \(\displaystyle{ A\in \mathbb{B}_1}\), ponieważ rodzina \(\displaystyle{ \mathbb{B}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\), więc jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), więc \(\displaystyle{ A\subset X}\), więc \(\displaystyle{ X \cap A=A}\), a więc, kontynuując równości, otrzymujemy, że to jest równe: \(\displaystyle{ = \bigcup_{A\in \mathbb{B}_1} A= \bigcup \mathbb{B}_1=}\) i ponieważ rodzina \(\displaystyle{ \mathbb{B}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\), więc to jest równe zbiorowi \(\displaystyle{ X}\). Wykazaliśmy zatem, że \(\displaystyle{ \bigcup\mathbb{B}=X.}\)

Pozostaje wykazać, że rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów niepustych- wynika to od razu z definicji tej rodziny( i faktu, że zbiór pusty jest tylko jeden). A więc \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów niepustych.

A więc rodzina \(\displaystyle{ \mathbb{B}}\) jest rozkładem zbioru \(\displaystyle{ X.\square}\)


Uogólnijmy powyższy fakt na dwa rozkłady w dwóch (prawie) dowolnych zbiorach, tzn.:

Niech \(\displaystyle{ X,Y}\) będą zbiorami niepustymi, których przekrój jest niepusty (będziemy chcieli zadać rozkład w \(\displaystyle{ X \cap Y}\), a gdyby ten przekrój byłby pusty, to byłby problem, gdyż nie ma sensu mówić o rozkładzie w zbiorze pustym). Niech rodzina \(\displaystyle{ \mathbb{B}_X}\) będzie rozkładem w \(\displaystyle{ X}\), a rodzina \(\displaystyle{ \mathbb{B}_Y}\) rozkładem w \(\displaystyle{ Y}\). Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\), zdefiniowana jako:

\(\displaystyle{ \mathbb{B}=\left\{ A \cap B\Bigl| \ \ A\in\mathbb{B}_X, B\in\mathbb{B}_Y\right\} \setminus \left\{ \emptyset\right\}, }\)

jest rozkładem w \(\displaystyle{ X \cap Y.}\)

Dowód:

Uzasadnijmy najpierw, że \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X \cap Y.}\)

Jeśli \(\displaystyle{ C\in\mathbb{B}}\), to \(\displaystyle{ C=A \cap B}\), gdzie \(\displaystyle{ A\in\mathbb{B}_X, B\in\mathbb{B}_Y,}\) ponieważ rodzina \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem w \(\displaystyle{ X}\), (więc jest rodziną podzbiorów zbioru \(\displaystyle{ X}\)), więc \(\displaystyle{ A\subset X}\), podobnie ponieważ rodzina \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem w \(\displaystyle{ Y}\), więc \(\displaystyle{ B\subset Y}\), mamy \(\displaystyle{ A\subset X}\), więc \(\displaystyle{ C=A \cap B\subset X \cap Y}\), czyli \(\displaystyle{ C\subset X \cap Y}\), i rodzina \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów \(\displaystyle{ X \cap Y.}\)

Do dalszego dowodu wykorzystamy fakt z pierwszego postu tego wątku oraz fakt udowodniony powyżej.

Mamy \(\displaystyle{ X \neq \left\{ \right\}}\), rodzina \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem zbioru \(\displaystyle{ X}\). Mamy \(\displaystyle{ \left\{ \right\} \neq X \cap Y\subset X.}\) Stosując zatem twierdzenie z pierwszego postu tego wątku otrzymujemy, że rodzina:

\(\displaystyle{ \mathbb{B}_{X \cap Y}=\left\{ A \cap \left( X \cap Y\right)\Bigl| \ A\in\mathbb{B}_X \right\} \setminus \left\{ \emptyset \right\}}\),

jest rozkładem w \(\displaystyle{ X \cap Y.}\)

Zauważmy, że jeśli \(\displaystyle{ A\in\mathbb{B}_X}\), ponieważ \(\displaystyle{ \mathbb{B}_X}\) jest rozkładem w \(\displaystyle{ X}\), a wiec rodziną podzbiorów \(\displaystyle{ X}\), więc \(\displaystyle{ A\subset X}\), zatem \(\displaystyle{ A \cap X=A}\), zatem \(\displaystyle{ A \cap \left( X \cap Y\right) =\left( A \cap X\right) \cap Y=A \cap Y.}\) Możemy zatem tą rodzinę zbiorów zapisać jeszcze prościej:

\(\displaystyle{ \mathbb{B}_{X \cap Y}=\left\{ A \cap Y\Bigl| \ A\in\mathbb{B}_X\right\} \setminus \left\{ \emptyset\right\} .}\)

Zastosujemy to samo twierdzenie o zawężeniu rozkładu do podzbioru, dla rozkładu \(\displaystyle{ \mathbb{B}_Y}\) w \(\displaystyle{ Y.}\)

Mamy \(\displaystyle{ Y \neq \left\{ \right\}}\) , rodzina \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem w \(\displaystyle{ Y}\), mamy \(\displaystyle{ \left\{ \right\} \neq X \cap Y\subset Y.}\) Stosując zatem to twierdzenie z pierwszego postu tego wątku otrzymujemy, że rodzina \(\displaystyle{ \mathbb{D}_{X \cap Y}}\), określona jako:

\(\displaystyle{ \mathbb{D}_{X \cap Y} =\left\{ B \cap \left( X \cap Y\right)\Bigl| \ B\in\mathbb{B}_Y \right\} \setminus \left\{ \emptyset\right\} }\),

jest rozkładem w \(\displaystyle{ X \cap Y}\).

Zauważmy, że jeśli \(\displaystyle{ B\in\mathbb{B}_Y}\), to ponieważ rodzina \(\displaystyle{ \mathbb{B}_Y}\) jest rozkładem w \(\displaystyle{ Y}\)( a więc rodziną podzbiorów zbioru \(\displaystyle{ Y}\)), więc \(\displaystyle{ B\subset Y}\), więc \(\displaystyle{ B \cap Y=B}\), a zatem \(\displaystyle{ B \cap \left( X \cap Y\right) =B \cap \left( Y \cap X\right)=\left( B \cap Y\right) \cap X=B \cap X.}\)

Tak więc: \(\displaystyle{ \mathbb{D}_{X \cap Y}=\left\{ B \cap X\Bigl| \ B\in\mathbb{B}_Y \right\} \setminus \left\{ \emptyset\right\} .}\)

Ponieważ zbiór \(\displaystyle{ X \cap Y}\) jest niepusty, i mamy dwa rozkłady w nim (\(\displaystyle{ \mathbb{B}_{X \cap Y}}\) oraz \(\displaystyle{ \mathbb{D}_{X \cap Y}}\) ), więc na mocy twierdzenia udowodnionego przed chwilą rodzina:

\(\displaystyle{ \mathbb{A}=\left\{ C \cap D\Bigl| C\in\mathbb{B}_{X \cap Y}, D\in \mathbb{D} _{X \cap Y} \right\} \setminus \left\{ \emptyset\right\}}\),

jest rozkładem w \(\displaystyle{ X \cap Y.}\)

Rozpiszmy definicję tej rodziny. Mamy:

\(\displaystyle{ \mathbb{A}= \left\{ \left( A \cap Y\right) \cap D\Bigl| \ A\in\mathbb{B}_X, D\in\mathbb{D}_{X \cap Y} \right\} \setminus \left\{ \emptyset\right\} = \left\{ \left( A \cap Y\right) \cap \left( B \cap X\right)\Bigl| \ A\in\mathbb{B}_X , B\in\mathbb{B}_Y \right\} \setminus \left\{ \emptyset\right\} = \\ =\left\{ \left( A \cap B\right) \cap X \cap Y\Bigl| \ \ A\in\mathbb{B}_X, B\in\mathbb{B}_Y \right\} \setminus \left\{ \emptyset\right\}.}\)

Wykażemy teraz, że nasza rodzina \(\displaystyle{ \mathbb{B}}\), której dotyczy teza tego twierdzenia, jest równa rodzinie \(\displaystyle{ \mathbb{A}}\).
Dowód tego faktu::    
Zatem \(\displaystyle{ \mathbb{B}=\mathbb{A}}\). Ponieważ rodzina \(\displaystyle{ \mathbb{A}}\) jest rozkładem w \(\displaystyle{ X \cap Y}\), więc rodzina \(\displaystyle{ \mathbb{B}}\), jako ta sama rodzina podzbiorów \(\displaystyle{ X \cap Y,}\) jest rozkładem w \(\displaystyle{ X \cap Y.\square}\) :lol:


Uściślimy teraz, te intuicyjne 'przekrajanie rozkładów'.

Niech \(\displaystyle{ X}\) będzie niepustym zbiorem, a \(\displaystyle{ \mathbb{S}}\) dowolną niepustą rodziną rozkładów w \(\displaystyle{ X}\). Rozważmy zbiór \(\displaystyle{ \mathbb{A}= \bigcup\mathbb{S}}\) (elementami takiej sumy są wszystkie zbiory wszystkich rozkładów z \(\displaystyle{ \mathbb{S}}\), a więc \(\displaystyle{ \mathbb{A}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\)).

Rozważmy rodzinę niepustych przekrojów mnogościowych:

\(\displaystyle{ \mathbb{D}=\left\{ \bigcap\mathbb{B} \Bigl| \ \ \mathbb{B}\subset \mathbb{A}\right\} \setminus \left\{ \emptyset\right\} }\),

jest to rodzina niepustych (gdyż zbiór pusty jest tylko jeden) przekrojów mnogościowych rodzin zbiorów spośród tych zbiorów wszystkich rozkładów (prościej- z każdego rozkładu wybieramy do rodziny zbiorów tak naprawdę co najwyżej jeden zbiór- nie możemy z pewnego rozkładu wybrać dwóch różnych zbiorów, gdyż wtedy, takie dwa zbiory, jako dwa różne zbiory rozkładu byłyby rozłączne, więc cały przekrój mnogościowy byłby pusty, a my rozważamy przekroje mnogościowe niepuste- sprzeczność, czyli tak w danym punkcie danego zbioru \(\displaystyle{ X}\), kroimy te zbiory kolejnych rozxkładów, i tak po całej 'płaszczyźnie' zbioru \(\displaystyle{ X}\), i będziemy rozważać najmniejsze takie 'kawałki').

Rodzina \(\displaystyle{ \mathbb{D},}\) jak każda rodzina zbiorów, jest uporządkowana przez inkluzję, zatem \(\displaystyle{ (\mathbb{D},\subset)}\) jest zbiorem uporządkowanym. Wybierzmy z niego zbiory minimalne, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}_0,}\) zdefiniowaną jako :

\(\displaystyle{ \mathbb{B}_0=\left\{ A\in\mathbb{D}: A \hbox{ jest zbiorem minimalnym w } \mathbb{D}\right\} .}\)

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem zbioru \(\displaystyle{ X.}\)


Jednak podejdziemy do tego zagadnienia od innej strony.

Zacznijmy od bardzo prostej obserwacji, że jeśli \(\displaystyle{ x\in X }\) jest punktem zbioru \(\displaystyle{ X}\), a \(\displaystyle{ \mathcal{R}}\) rozkładem tej rodziny, to istnieje dokładnie jeden zbiór\(\displaystyle{ A\in\mathcal{R}}\) tego rozkładu zawierający punkt \(\displaystyle{ x}\), tzn. taki, że \(\displaystyle{ x\in A.}\)

Aby to uzasadnić, to ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ X}\), więc \(\displaystyle{ \bigcup\mathcal{R}=X}\), a więc \(\displaystyle{ x \in \bigcup\mathcal{R}}\), a więc \(\displaystyle{ x\in A}\), gdzie \(\displaystyle{ A\in\mathcal{R}}\), a zatem zbiór \(\displaystyle{ A}\) jest zbiorem rozkładu \(\displaystyle{ \mathcal{R}}\) zawierającym element \(\displaystyle{ x.}\)

Aby wykazać, że taki zbiór jest jedyny, to weźmy zbiory \(\displaystyle{ A,B\in \mathcal{R}}\), takie, że \(\displaystyle{ x\in A, x\in B}\), i pokażmy, że \(\displaystyle{ A=B.}\) Wtedy \(\displaystyle{ x\in A\cap B}\), a zbiory \(\displaystyle{ A,B\in\mathcal{R}}\), a \(\displaystyle{ \mathcal{R}}\) jest rozkładem, i zbiory \(\displaystyle{ A,B}\) tego rozkładu się przecinają, zatem z warunku rozłączności zbiorów rozkładu wnioskujemy, że \(\displaystyle{ A=B.}\)

Wobec czego taki zbiór istnieje dokładnie jeden. Dla punktu \(\displaystyle{ x\in X}\), dla rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S},}\) ten zbiór będziemy oznaczać jako \(\displaystyle{ \left[ x\right] _{\mathcal{R}}}\). Zauważmy, że zawsze \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset X.}\)

Dla punktu \(\displaystyle{ x\in X,}\) będziemy rozważać przekroje mnogościowe \(\displaystyle{ \bigcap_{\mathcal{R} \in\mathbb{S}} \left[ x\right] _{\mathcal{R}} }\)- przekroje wszystkich zbiorów kolejnych rozkładów zawierających element \(\displaystyle{ x.}\)

Rozważmy rodzinę \(\displaystyle{ \mathbb{D}_0}\), daną jako:

\(\displaystyle{ \mathbb{D}_0=\left\{ \bigcap_{\mathcal{R} \in\mathbb{S}} \left[ x\right] _{\mathcal{R}} \Bigl| \ \ x\in X \right\}.}\)

Zauważmy, że jest to rodzina podzbiorów zbioru \(\displaystyle{ X}\).


Wykażemy, że rodzina \(\displaystyle{ \mathbb{D}_0}\) jest rozkładem zbioru \(\displaystyle{ X}\), i że jest równa rodzinie \(\displaystyle{ \mathbb{B}_0}\) (wcześniej zdefiniowanej rodzinie minimalnych przekrojów mnogościowych).

Dowód:

Niewątpliwie \(\displaystyle{ \bigcup\mathbb{D}_0\subset X}\)( suma podzbiorów zbioru \(\displaystyle{ X}\)). Odwrotnie: jeśli \(\displaystyle{ x\in X}\), \(\displaystyle{ \mathcal {R}\in\mathbb{S}}\), to \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}} }\), a zatem \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}} }\) , dla każdego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S}}\), i (ponieważ rodzina \(\displaystyle{ \mathbb{S}}\) jest niepusta), więc \(\displaystyle{ x\in \bigcap_{\mathcal{R} \in\mathbb{S}} [x] _{\mathcal{R}} .}\) A zatem \(\displaystyle{ x\in \bigcup_{x\in X}\left( \bigcap_{\mathcal{R} \in\mathbb{S}} [x] _{\mathcal{R}} \right) = \bigcup\mathbb{D}_0}\). A zatem \(\displaystyle{ \bigcup\mathbb{D}_0=X.}\)

Wykażemy teraz, że rodzina \(\displaystyle{ \mathbb{D}_0}\) jest rodziną zbiorów rozłącznych. W tym celu weźmy dwa zbiory postaci: \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S}} \left[ x_1\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ x_1\in X}\); oraz weźmy zbiór postaci: \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S}} \left[ x_2\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ x_2\in X}\). I weźmy element \(\displaystyle{ y}\) z przekroju tych dwóch zbiorów (tzn. przypuśćmy, że te dwa zbiory mają wspólny element). Wtedy \(\displaystyle{ y\in \left[ x_1\right] _{\mathcal{R} }}\), dla każdego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S};}\) oraz \(\displaystyle{ y\in\left[ x_2\right] _{\mathcal{R}}}\), dla każdego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S}. }\) Niech \(\displaystyle{ \mathcal{R}\in\mathbb{S}.}\) Wtedy \(\displaystyle{ y\in \left[ x_1\right] _{\mathcal{R} } , y\in \left[ x_2\right] _{\mathcal{R} },}\) zatem \(\displaystyle{ y\in \left[ x_1\right] _{\mathcal{R} } \cap\left[ x_2\right] _{\mathcal{R} }.}\) Ponieważ \(\displaystyle{ [x_1] _{\mathcal{R}}\in\mathcal{R}}\) i \(\displaystyle{ [x_2] _{\mathcal{R}}\in\mathcal{R}}\) (z definicji tych zbiorów), a \(\displaystyle{ \mathcal{R}}\) jest rozkładem, więc z warunku rozłączności otrzymujemy, że: \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}=\left[ x_2\right] _{\mathcal{R}}.}\) Otrzymujemy zatem (z dowolności \(\displaystyle{ \mathcal{R}\in\mathbb{S}}\) ), że dla każdego \(\displaystyle{ \mathcal{R}\in\mathbb{S}}\): \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}=\left[ x_2\right] _{\mathcal{R}}}\), a zatem \(\displaystyle{ \left\{ \left[ x_1\right] _{\mathcal{R}}: \ \mathcal{R}\in\mathbb{S} \right\}= \left\{\left[ x_2\right] _{\mathcal{R}}: \ \mathcal{R}\in\mathbb{S} \right\}}\), a więc również (gdyż dla tej samej rodziny zbiorów jej przekrój jest jedyny ), więc: \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S}}\left[ x_1\right] _{\mathcal{R}} = \bigcap_{\mathcal{R}\in\mathbb{S}}\left[ x_2\right] _{\mathcal{R}}.}\) Pokazaliśmy zatem, że jeśli dwa zbiory z \(\displaystyle{ \mathbb{D}_0}\) się przecinają, to są równe. Wynika stąd, że jeśli dwa zbiory z \(\displaystyle{ \mathbb{D}_0}\) są różne, to nie mają wspólnych elementów, bo gdyby miały wspólny element to, zgodnie z powyższym, musiałyby być równe, wbrew założeniu. Zatem, każde dwa różne zbiory z \(\displaystyle{ \mathbb{D}_0}\) nie mają wspólnych elementów, a więc są rozłączne.

Pozostaje pokazać, w tej części dowodu, że jest to rodzina zbiorów niepustych. Rozważmy zbiór postaci \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S} } \left[ x\right] _{\mathcal{R}} }\), gdzie \(\displaystyle{ x\in X}\). Zauważmy, że jeśli \(\displaystyle{ \mathcal{R}\in\mathbb{S} }\), to \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}}.}\) A zatem \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}}}\) , dla każdego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S} }\), a zatem (i ponieważ rodzina \(\displaystyle{ \mathbb{S} }\) jest niepusta), więc \(\displaystyle{ x\in \bigcap_{\mathcal{R}\in\mathbb{S} } \left[ x\right] _{\mathcal{R}}}\), a więc zbiór \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S} } \left[ x\right] _{\mathcal{R}}}\) jest niepusty, i \(\displaystyle{ \mathbb{D} _0}\) jest rodziną zbiorów niepustych.

Zatem rodzina \(\displaystyle{ \mathbb{D}_0}\) jest rozkładem zbioru \(\displaystyle{ X. \square}\) :lol:


Wykażemy teraz, że \(\displaystyle{ \mathbb{B}_0=\mathbb{D}_0.}\)

Zauważmy najpierw, że rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), łatwo to można sprawdzić ( i oczywiście rodzina \(\displaystyle{ \mathbb{D}_0,}\) jako rozkład w \(\displaystyle{ X}\), jest rodziną podzbiorów zbioru \(\displaystyle{ X}\)).

Jeśli \(\displaystyle{ A\in\mathbb{B}_0}\), to \(\displaystyle{ A\in \mathbb{D}}\), zatem \(\displaystyle{ A= \bigcap\mathbb{B}}\), gdzie \(\displaystyle{ \mathbb{B}\subset \mathbb{A}}\), i ten przekrój \(\displaystyle{ A \neq \left\{ \right\}}\) jest niepusty, i również zbiór \(\displaystyle{ A}\) jest zbiorem minimalnym w \(\displaystyle{ \mathbb{D}=\left\{ \bigcap\mathbb{B}\Bigl| \ \mathbb{B}\subset \mathbb{A}\right\} \setminus \left\{ \emptyset\right\} }\). Niech \(\displaystyle{ x\in \bigcap\mathbb{B}=A \neq \left\{ \right\}}\). Wtedy \(\displaystyle{ x\in B}\), dla każdego zbioru \(\displaystyle{ B\in\mathbb{B}}\). Wykażemy, że \(\displaystyle{ A= \bigcap_{\mathcal{R}\in\mathbb{S}} \left[ x\right] _{\mathcal{R}}.}\) Zauważmy, że rodzina \(\displaystyle{ \mathbb{B}}\) musi być niepusta, (gdyż \(\displaystyle{ \bigcap \emptyset=\emptyset }\), a \(\displaystyle{ \emptyset\neq A= \bigcap \mathbb{B}}\)). Wobec czego również rodzina \(\displaystyle{ \mathbb{B} \neq \left\{ \right\}}\) musi być niepusta.

Wykażemy teraz, że: \(\displaystyle{ \left\{ \left[ x\right] _{\mathcal {R}}\Bigl | \ \ \mathcal{R} \in\mathbb{S}\ \right\} \supset \mathbb{B}.}\)

Niech \(\displaystyle{ B\in\mathbb{B}}\). Wtedy \(\displaystyle{ x\in B}\)( bo \(\displaystyle{ x\in B}\), dla każdego zbioru \(\displaystyle{ B\in\mathbb{B}}\)). Mamy \(\displaystyle{ B\in\mathbb{A}= \bigcup\mathbb{S}}\). A zatem, z definicji sumy mnogościowej: \(\displaystyle{ B\in\mathcal {R}}\), dla pewnego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S}.}\) Poniewaz \(\displaystyle{ x\in B, B\in\mathcal R,}\) i ponieważ istnieje tylko jeden zbiór \(\displaystyle{ B\in\mathcal {R}}\), taki, że \(\displaystyle{ x\in B}\), więc musi być \(\displaystyle{ B=\left[ x\right] _{\mathcal{R}}}\) , gdzie \(\displaystyle{ \mathcal R\in\mathbb{S}.}\) A zatem \(\displaystyle{ B\in \left\{ \left[ x\right] _{\mathcal{R} }\Bigl| \ \mathcal R\in\mathbb{S} \right\} .}\) A zatem \(\displaystyle{ \mathbb{ B}\subset \left\{ \left[ x\right] _{\mathcal{R}}: \ \mathcal{R}\in\mathbb{S} \right\}.}\)

Ponieważ wiemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, ponieważ przecięcie większej rodziny zbiorów jest mniejsze, o ile mniejsza rodzina nie jest pusta (a przecież rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta), więc: \(\displaystyle{ \bigcap_{\mathcal{R} \in\mathbb{S}} \left[ x\right] _{\mathcal R} \subset \bigcap\mathbb{B}=A.}\) Łatwo sprawdzić, że \(\displaystyle{ \left\{ \left[ x\right] _{\mathcal{R}}\Bigl| \ \mathcal R\in\mathbb{S} \right\} \subset \mathbb{A},}\) i przekrój \(\displaystyle{ \bigcap_{\mathcal R \in\mathbb{S} } \left[ x\right] _{\mathcal R}}\) jest niepusty (jako zbiór z rozkładu \(\displaystyle{ \mathbb{D}_0}\)), więc możemy wnioskować, że \(\displaystyle{ \left( \bigcap_{\mathcal R\in\mathbb{S} } \left[ x\right] _{\mathcal{R}} \right) \in \mathbb{D}}\), a ponieważ zbiór \(\displaystyle{ A}\) jest zbiorem minimalnym w \(\displaystyle{ \mathbb{D}}\) (a ten przekrój jest jego podzbiorem, czyli jest mniejszy lub równy względem inkluzji), więc \(\displaystyle{ \bigcap_{\mathcal{R}\in\mathbb{S} } \left[ x\right] _{\mathcal{R}}=A}\), i \(\displaystyle{ A\in\mathbb{D}_0. }\)

Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ A\in\mathbb{D}_0.}\) Wtedy \(\displaystyle{ A= \bigcap_{\mathcal R\in\mathbb{S}} \left[ x\right] _{\mathcal R}}\), gdzie \(\displaystyle{ x\in X}\). Łatwo można pokazać, że \(\displaystyle{ \left\{ \left[ x\right] _{\mathcal R}\Bigl| \ \mathcal R\in\mathbb{S} \right\}\subset \mathbb{A}= \bigcup\mathbb{S}.}\) I ponieważ \(\displaystyle{ A\in\mathbb{D}_0}\), a rodzina \(\displaystyle{ \mathbb{D}_0}\) jest rozkładem zbioru \(\displaystyle{ X}\), więc zbiór \(\displaystyle{ A}\) musi być niepusty, skąd możemy wnioskować, że: \(\displaystyle{ \bigcap_{\mathcal R\in\mathbb{S}} \left[ x\right] _{\mathcal R}=A\in\mathbb{D}. }\)

Wykażemy teraz, że zbiór \(\displaystyle{ A}\) jest zbiorem minimalnym w \(\displaystyle{ \mathbb{D}.}\)

Weźmy zbiór \(\displaystyle{ B\in \mathbb{D}}\), taki, że \(\displaystyle{ B \subseteq A}\), i pokażmy, że \(\displaystyle{ B=A.}\) Przypuśćmy, że tak nie jest . Wtedy \(\displaystyle{ B\subsetneq A}\). Ponieważ \(\displaystyle{ B\in\mathbb{D}}\), to \(\displaystyle{ B= \bigcap\mathbb{B}}\), gdzie \(\displaystyle{ \mathbb{B}\subset\mathbb{A}}\), a \(\displaystyle{ \mathbb{A}= \bigcup\mathbb{S}}\). Mamy \(\displaystyle{ A= \bigcap_{\mathcal R\in\mathbb{S}} \left[ x\right] _{\mathcal R}. }\)

Pokażemy, że \(\displaystyle{ \mathbb{B}\subset \left\{ \left[ x\right] _{\mathcal R}\Bigl| \ \mathcal R\in \mathbb{S} \right\}.}\)

Niech \(\displaystyle{ C\in\mathbb{B}}\). Wtedy \(\displaystyle{ C\in \bigcup\mathbb{S}}\). zatem \(\displaystyle{ C\in\mathcal{R}}\), gdzie \(\displaystyle{ \mathcal{R}\in\mathbb{S}}\). Ponieważ \(\displaystyle{ C\in\mathcal R}\), a a \(\displaystyle{ \mathcal R}\) jest rozkładem, więc zbiór \(\displaystyle{ C}\) musi być niepusty. Istnieje więc \(\displaystyle{ x\in C}\). Ponieważ mamy \(\displaystyle{ x\in X}\), a \(\displaystyle{ \mathcal R\in\mathbb{S}}\), i ponieważ istnieje tylko jeden zbiór \(\displaystyle{ \left[ x\right] _{\mathcal R}}\), tzn. taki zbiór rozkładu \(\displaystyle{ \mathcal R}\) zawierający element \(\displaystyle{ x}\), więc \(\displaystyle{ C=\left[ x\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ \mathcal R\in\mathbb{S}}\) , a zatem \(\displaystyle{ C\in\left\{ \left[ x\right] _{\mathcal R}\Bigl| \ \mathcal R\in\mathbb{S} \right\}}\) , co kończy dowód tej inkluzji.

Mamy \(\displaystyle{ \mathbb{B} \neq \left\{ \right\}}\), zatem ponieważ wtedy przecięcie większej rodziny zbiorów, od rodziny \(\displaystyle{ \mathbb{B}}\), jest mniejsze, więc \(\displaystyle{ B= \bigcap\mathbb{B}\supset \bigcap_{\mathcal{R}\in\mathbb{S} }\left[ x\right] _{\mathcal{R}}=A}\), czyli \(\displaystyle{ B\supset A}\), a mamy \(\displaystyle{ B \subsetneq A}\), skąd \(\displaystyle{ B=A}\), a \(\displaystyle{ B\subsetneq A}\)- sprzeczność.

Wobec czego zbiór \(\displaystyle{ A}\) jest zbiorem minimalnym.


Mamy \(\displaystyle{ A\in\mathbb{D}}\), zatem \(\displaystyle{ A\in\mathbb{B}_0}\). Wobec czego \(\displaystyle{ \mathbb{D}_0=\mathbb{B}_0}\).

I ponieważ rodzina \(\displaystyle{ \mathbb{D}_0}\) jest rozkładem zbioru \(\displaystyle{ X}\), więc rodzina \(\displaystyle{ \mathbb{B}_0}\), jako ta sama rodzina podzbiorów zbioru \(\displaystyle{ X}\), jest rozkładem zbioru \(\displaystyle{ X.\square}\)


Wykażemy na koniec (zachowując oznaczenia), że jeśli \(\displaystyle{ \mathcal{R}}\) jest rozkładem, a \(\displaystyle{ A\in\mathcal R}\) zbiorem tego rozkładu, to zbiór \(\displaystyle{ A}\) można rozłożyć (i to w sposób jednoznaczny) na zbiory z \(\displaystyle{ \mathbb{B}_0}\) (tego rozkładu na minimalne przekroje mnogościowe). Tzn. wykażemy, że istnieje jedyna rodzina zbiorów \(\displaystyle{ \mathbb{A}_0\subset \mathbb{B}_0}\) będąca rozkładem zbioru \(\displaystyle{ A.}\)

Podajmy najpierw ważny dla nas lemat.

Lemat. Jeśli \(\displaystyle{ x\in X}\), to to istnieje dokładnie jeden zbiór \(\displaystyle{ B\in\mathbb{B}_0}\), taki, że: \(\displaystyle{ x\in B}\). Łatwo to można udowodnić, gdyż rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem zbioru \(\displaystyle{ X}\), łatwo to można udowodnić- w sposób podobny jak wcześniej. Dla dowolnego \(\displaystyle{ x\in X}\), zbiór ten będziemy oznaczać jako \(\displaystyle{ \left[ x\right] _{ \bigcap\mathbb{S}}.}\)

Przejdźmy do naszego dowodu:

Dowód:

Zdefiniujmy rodzinę \(\displaystyle{ \mathbb{A}_0}\) jako:

\(\displaystyle{ \mathbb{A}_0:=\left\{ \left[ x\right] _{ \bigcap\mathbb{S}} \Bigl| \ \ x\in A \right\}\subset \mathbb{B}_0.}\)

Musimy najpierw pokazać, że jest to rodzina podzbiorów zbioru \(\displaystyle{ A.}\)

Niech \(\displaystyle{ x\in A}\). Wtedy rozważany przez nas zbiór \(\displaystyle{ \left[ x\right] _{ \bigcap \mathbb{S}} \in\mathbb{B}_0=\mathbb{D}_0=\left\{ \bigcap_{\mathcal {R}_0\in\mathbb{S}} \left[ x\right] _{\mathcal R_0} \Bigl| \ x\in X \right\} }\). Niech \(\displaystyle{ \left[ x\right] _{ \bigcap\mathbb{S}}= \bigcap_{\mathcal {R}_0\in \mathbb{S}} \left[ y\right] _{\mathcal {R}_0}}\), gdzie \(\displaystyle{ y\in X}\). Wtedy ponieważ \(\displaystyle{ x\in\left[ x\right] _{ \bigcap\mathbb{S}}}\), to \(\displaystyle{ x \in \bigcap_{\mathcal {R}_0\in \mathbb{S}} \left[ y\right] _{\mathcal {R}_0}\subset \left[ y\right] _{\mathcal {R}}}\). Zatem \(\displaystyle{ x\in \left[ y\right] _{\mathcal {R}}.}\) Mamy \(\displaystyle{ x\in A, A\in \mathcal{R},}\) ponieważ istnieje tylko jeden zbiór rozkładu \(\displaystyle{ \mathcal{R}}\), zawierający element \(\displaystyle{ x}\), więc \(\displaystyle{ \left[ y\right] _{\mathcal {R}}=A}\). Zatem \(\displaystyle{ \left[ x\right] _{ \bigcap \mathbb{S}} \subset \left[ y\right] _{\mathcal{R}}=A}\), i (z dowolności zbiorów takich postaci, gdzie zmienna \(\displaystyle{ x}\) przebiega \(\displaystyle{ x\in A}\) zbiór \(\displaystyle{ A}\) ), więc otrzymujemy, że rodzina \(\displaystyle{ \mathbb{A}_0}\) jest rodziną podzbiorów zbioru \(\displaystyle{ A.}\)


Dowód, że rodzina \(\displaystyle{ \mathbb{A}_0}\) jest rozkładem zbioru \(\displaystyle{ A}\) jest dość prosty.

Musimy pokazać, że \(\displaystyle{ \bigcup\mathbb{A}_0=A}\). Niewątpliwie \(\displaystyle{ \bigcup\mathbb{A}_0\subset A}\) (suma podzbiorów zbioru \(\displaystyle{ A}\)). Odwrotnie: jeśli \(\displaystyle{ a\in A}\), to \(\displaystyle{ a\in \left[ a\right] _{ \bigcap \mathbb{S} } \in\mathbb{A}_0}\), a więc \(\displaystyle{ a\in \bigcup \mathbb{A}_0}\). A więc \(\displaystyle{ \bigcup\mathbb{A}_0=A.}\)\(\displaystyle{ }\)

Musimy wykazać teraz, że każde dwa różne zbiory z \(\displaystyle{ \mathbb{A}_0}\) są rozłączne. Niech \(\displaystyle{ A_1,A_2\in\mathbb{A}_0}\) będą różnymi zbiorami. Wtedy \(\displaystyle{ A_1= \left[ x_1\right] _{ \bigcap \mathbb{S}}}\), gdzie \(\displaystyle{ x_1\in A}\), i \(\displaystyle{ A_2= \left[ x_2\right] _{ \bigcap \mathbb{S}}}\), gdzie \(\displaystyle{ x_2\in A}\). Wtedy \(\displaystyle{ A_1,A_2\in\mathbb{B}_0}\), oraz \(\displaystyle{ A_1 \neq A_2 }\), a rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem, więc zbiory \(\displaystyle{ A_1,A_2}\) są rozłączne.

Pozostaje pokazać, że rodzina \(\displaystyle{ \mathbb{A}_0}\) jest rodziną zbiorów niepustych.

Jeśli \(\displaystyle{ B\in\mathbb{A}_0}\), to \(\displaystyle{ B=\left[ x\right] _{ \bigcap\mathbb{S}}}\), gdzie \(\displaystyle{ x\in A}\). Wtedy, z definicji tych zbiorów, mamy: \(\displaystyle{ x\in\left[ x\right] _{ \bigcap\mathbb{S}}=B}\), a więc zbiór \(\displaystyle{ B}\) jest niepusty, i \(\displaystyle{ \mathbb{A}_0}\) jest rodziną zbiorów niepustych.

A więc rodzina \(\displaystyle{ \mathbb{A}_0}\) jest rozkładem zbioru \(\displaystyle{ A.}\)


Pozostaje pokazać, że taki rozkład jest tylko jeden.

Przypuśćmy nie wprost, że \(\displaystyle{ \mathbb{A}_1, \mathbb{A}_2\subset \mathbb{B}_0}\) są dwoma różnymi rozkładami zbioru \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ \mathbb{A}_1 \neq \mathbb{A}_2}\), więc \(\displaystyle{ \mathbb{A}_1\not\subset \mathbb{A}_2}\) lub \(\displaystyle{ \mathbb{A}_2\not\subset \mathbb{A}_1}\).
Jeśli \(\displaystyle{ \mathbb{A}_1 \not\subset \mathbb{A}_2}\), to ponieważ mamy \(\displaystyle{ \mathbb{A}_1 \neq \left\{ \right\}}\), i nie każdy zbiór z \(\displaystyle{ \mathbb{A}_1}\) należy do \(\displaystyle{ \mathbb{A}_2}\), więc otrzymujemy, że istnieje zbiór \(\displaystyle{ B\in\mathbb{A}_1}\), taki, że \(\displaystyle{ B\not\in \mathbb{A}_2.}\) Wtedy \(\displaystyle{ B\in \mathbb{B}_0}\), ponieważ \(\displaystyle{ \mathbb{B}_0}\)- jest to rozkład, więc zbiór \(\displaystyle{ B}\) jest niepusty. Niech \(\displaystyle{ x\in B \neq \left\{ \right\}}\) . Ponieważ \(\displaystyle{ B\in\mathbb{A}_1}\), a \(\displaystyle{ \mathbb{A}_1}\) jest rozkładem zbioru \(\displaystyle{ A}\), wiec \(\displaystyle{ \mathbb{A}_1}\) jest rodziną podzbiorów zbioru \(\displaystyle{ A}\), więc \(\displaystyle{ B\subset A}\), zatem \(\displaystyle{ x\in A}\). Niech \(\displaystyle{ C\in\mathbb{A}_2}\) będzie takim zbiorem, że \(\displaystyle{ x\in C}\) (taki zbiór jest dokładnie jeden, bo \(\displaystyle{ \mathbb{A}_2}\) jest rozkładem zbioru \(\displaystyle{ A}\)). Wtedy \(\displaystyle{ C \neq B}\), bo \(\displaystyle{ C\in\mathbb{A}_2}\), a \(\displaystyle{ B\not\in\mathbb{A}_2}\). Mamy \(\displaystyle{ C\in\mathbb{B}_0}\), \(\displaystyle{ B\in\mathbb{B}_0}\), i \(\displaystyle{ C \neq B}\), a rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem, wiec zbiory \(\displaystyle{ B,C}\) muszą być rozłączne, a \(\displaystyle{ x\in B }\) i \(\displaystyle{ x\in C}\)- sprzeczność.

Jeśli \(\displaystyle{ \mathbb{A}_2\not\subset \mathbb{A}_1}\), to ponieważ mamy \(\displaystyle{ \mathbb{A}_2 \neq\left\{ \right\}}\) , więc zaprzeczając definicji inkluzji otrzymujemy, że istnieje zbiór \(\displaystyle{ B\in \mathbb{A}_2}\) taki, że \(\displaystyle{ B\not\in \mathbb{A}_1}\), i analogicznie otrzymujemy sprzeczność, co kończy dowód\(\displaystyle{ .\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: Rozkłady zbiorów

Post autor: Jakub Gurak »

W ostatni wtorek, udało się ukończyć, po kilku miesiącach przerwy, pewien trudniejszy, jak dla mnie, problem matematyczny, związany z rozkładami zbioru.

Tzn. rozważmy niepusty zbiór \(\displaystyle{ X,}\) i rozważmy rodzinę \(\displaystyle{ \mathbb{S}}\) wszystkich rozkładów zbioru \(\displaystyle{ X}\), i rozważmy relację porządku pomiędzy dwoma rozkładami, taką, że rozkład jest większy od danego rozkładu, gdy jest rozkładem na zbiory większe- wtedy zbiór większy, większego rozkładu, grupuje zbiory mniejsze, mniejszego rozkładu, zawarte w nim. Później uściślę znaczenie tej relacji porządku. Wykazałem, że jest to istotnie relacja porządku, oraz, że jeśli weźmiemy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D}\subset \mathbb{S}}\), to łańcuch \(\displaystyle{ \mathbb{D}}\) ma supremum.

Intuicyjnie, wyobrażam to sobie tak, że zlepiamy zbiory w większe grupy (w sytuacji, gdy mamy większy rozkład od danego), następnie w jeszcze większe grupy, itd., wielokrotnie, i wyobrażam to sobie tak, że na koniec cały zbiór jest podzielony na kilka dużych zbiorów, grupujących zbiory mniejsze zawarte w nich. Przy czym proces grupowania jest stopniowy, delikatny (delikatnie zbiory się kurczą), bo ten proces grupowania jest wielokrotny, ten proces grupowania może być nawet nieskończony. Ciężko jest dobrze to sobie wyobrazić, fajnie by było zobaczyć animację pokazującą jak wygląda stopniowo to 'zlepianie' zbiorów. Udało się ostatnio ukończyć to zadanie. Przedstawię teraz dowód tego niezwykłego ( :!: i niełatwego) faktu.


Rozważmy niepusty zbiór \(\displaystyle{ X}\),

i rozważmy rodzinę \(\displaystyle{ \mathbb{S}}\) wszystkich rozkładów zbioru \(\displaystyle{ X}\).

I rozważmy relację porządku \(\displaystyle{ \sqsubseteq}\) pomiędzy dwoma dowolnymi ustalonymi rozkładami, daną jako:

\(\displaystyle{ \mathcal{R}_1 \sqsubseteq\mathcal{R}_2 \Longleftrightarrow \left( A\in\mathcal{R}_1, B\in \mathcal{R}_2 \hbox{ i } A \cap B \neq \left\{ \right\} \rightarrow A\subset B\right) .}\)

Tzn. jeden rozkład jest większy od danego rozkładu, gdy jest rozkładem na zbiory większe, wtedy taki zbiór większy, większego rozkładu, grupuje zbiory mniejsze, mniejszego rozkładu, zawarte w nim, czyli ma być spełniony warunek: że jeśli weźmiemy zbiór \(\displaystyle{ A}\) mniejszego rozkładu, i zbiór \(\displaystyle{ B}\) większego rozkładu, takie, że te zbiory się przecinają, to zbiór \(\displaystyle{ A}\) zawiera się w zbiorze \(\displaystyle{ B}\)- nie jest to żadne prawo, tylko sytuacja, która nas interesuje, tak definiuje tą relację- czyli rozkład jest większy od danego, gdy jest rozkładem na zbiory większe.

Wykażemy, że jest to relacja porządku, a następnie, że jeśli weźmiemy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D}\subset \mathbb{S}}\), to łańcuch \(\displaystyle{ \mathbb{D}}\) ma supremum.


DOWÓD TEGO NIEZWYKŁEGO FAKTU:

Łatwo jest pokazać, że ta relacja jest zwrotna.

Niech \(\displaystyle{ \mathcal{R}\in \mathbb{S}}\). Aby pokazać, że \(\displaystyle{ \mathcal{R}\sqsubseteq \mathcal{R}}\), to weźmy zbiór \(\displaystyle{ A\in\mathcal{R},}\) oraz weźmy zbiór \(\displaystyle{ B\in \mathcal{R},}\) zbiory takie, że \(\displaystyle{ A \cap B \neq \left\{ \right\} }\),czyli takie, że te zbiory się przecinają, i pokażmy, że \(\displaystyle{ A\subset B}\). Ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkładem, a zbiory \(\displaystyle{ A,B\in\mathcal{R},}\) i zbiory \(\displaystyle{ A,B}\) się przecinają, więc z warunku rozłączności otrzymujemy, że: \(\displaystyle{ A=B}\), a więc w szczególności: \(\displaystyle{ A\subset B}\). A więc mamy relację: \(\displaystyle{ \mathcal{R}\sqsubseteq \mathcal{R}}\), i z dowolności wyboru rozkładu \(\displaystyle{ \mathcal{R}}\), otrzymujemy, że relacja \(\displaystyle{ \sqsubseteq}\) jest zwrotna.

Aby pokazać antysymetrię to załóżmy, że dla dwóch rozkładów \(\displaystyle{ \mathcal{R}_1}\) i \(\displaystyle{ \mathcal{R}_2}\) mamy: \(\displaystyle{ \mathcal{R}_1\sqsubseteq \mathcal{R}_2}\) i \(\displaystyle{ \mathcal{R}_2\sqsubseteq\mathcal{R}_1}\), i pokażmy, że \(\displaystyle{ \mathcal{R}_1=\mathcal{R}_2}\).

Jeśli \(\displaystyle{ A\in \mathcal{R}_1}\), ponieważ \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem, to zbiór \(\displaystyle{ A}\) tego rozkładu musi być niepusty. Istnieje więc element \(\displaystyle{ x\in A}\) (wtedy \(\displaystyle{ x\in X}\)). Niech \(\displaystyle{ B\in\mathcal{R}_2}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}_2}\) zawierającym element \(\displaystyle{ x }\)(tzn. takim, że \(\displaystyle{ x\in B}\)). Ponieważ \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem, więc taki zbiór jest dokładnie jeden. Wtedy \(\displaystyle{ x\in A \cap B}\), mamy \(\displaystyle{ A\in\mathcal{R}_1}\), \(\displaystyle{ B\in \mathcal{R}_2}\) i zbiór \(\displaystyle{ A \cap B}\) jest niepusty, i mamy \(\displaystyle{ \mathcal{R}_1\sqsubseteq \mathcal{R}_2}\), korzystając więc, z definicji relacji \(\displaystyle{ \sqsubseteq}\), widzimy, że założenia implikacji są spełnione, w związku z czym, wnioskujemy, że \(\displaystyle{ A\subset B. }\)
Mamy \(\displaystyle{ \mathcal{R}_2\sqsubseteq \mathcal{R}_1}\), i mamy \(\displaystyle{ B\in\mathcal{R}_2}\), \(\displaystyle{ A\in \mathcal{R}_1}\) i \(\displaystyle{ x\in B \cap A}\), a więc zbiór \(\displaystyle{ B \cap A}\) jest niepusty. Korzystając więc, z definicji relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ B\subset A}\). Mamy \(\displaystyle{ A\subset B}\), wobec czego \(\displaystyle{ A=B\in \mathcal{R}_2}\), czyli \(\displaystyle{ A\in \mathcal{R}_2.}\)

Jeśli \(\displaystyle{ A\in\mathcal{R}_2,}\) to w sposób symetryczny uzasadniamy, że \(\displaystyle{ A\in\mathcal{R}_1. }\)
Wobec czego \(\displaystyle{ \mathcal{R}_1=\mathcal{R}_2}\), i relacja \(\displaystyle{ \sqsubseteq}\) jest antysymetryczna.

Aby pokazać przechodniość załóżmy, że dla trzech rozkładów \(\displaystyle{ \mathcal{R}_1, \mathcal{R}_2, \mathcal{R}_3}\), mamy: \(\displaystyle{ \mathcal{R}_1 \sqsubseteq\mathcal{R}_2\sqsubseteq\mathcal{R}_3}\), i pokażmy, że \(\displaystyle{ \mathcal{R}_1\sqsubseteq \mathcal{R}_3}\).

W tym celu weźmy zbiory \(\displaystyle{ A\in \mathcal{R}_1}\), \(\displaystyle{ C\in\mathcal{R}_3}\), takie, że \(\displaystyle{ A \cap C \neq \left\{ \right\}}\), i pokażmy, że \(\displaystyle{ A\subset C.}\)

Zbiór \(\displaystyle{ A \cap C}\) jest niepusty, istnieje więc element \(\displaystyle{ x\in A \cap C}\). Wtedy \(\displaystyle{ x\in A}\) i \(\displaystyle{ x\in C}\). Wtedy \(\displaystyle{ x\in X}\). Niech \(\displaystyle{ B\in\mathcal{R}_2}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}_2}\) zawierającym element \(\displaystyle{ x}\) (ponieważ \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem, więc taki zbiór jest dokładnie jeden ). Wtedy \(\displaystyle{ x\in B \cap A}\). Mamy \(\displaystyle{ \mathcal{R}_1\sqsubseteq\mathcal{R}_2}\), i \(\displaystyle{ A\in\mathcal{R}_1}\), \(\displaystyle{ B\in\mathcal{R}_2}\) i \(\displaystyle{ x\in A \cap B}\), korzystając więc, z definicji relacji \(\displaystyle{ \sqsubseteq,}\) wnioskujemy, że \(\displaystyle{ A\subset B.}\)
Mamy \(\displaystyle{ \mathcal{R}_2\sqsubseteq \mathcal{R}_3}\), i mamy \(\displaystyle{ B\in\mathcal{R}_2}\), \(\displaystyle{ C\in\mathcal{R}_3}\) i \(\displaystyle{ x\in B \cap C}\), a więc zbiór \(\displaystyle{ B \cap C}\) jest niepusty. Korzystając z definicji relacji \(\displaystyle{ \sqsubseteq,}\) otrzymujemy: \(\displaystyle{ B\subset C}\). Mamy \(\displaystyle{ A\subset B,}\) a zatem \(\displaystyle{ A\subset C}\), co należało pokazać. Wobec czego \(\displaystyle{ \mathcal{R}_1 \sqsubseteq\mathcal{R}_3,}\) i relacja \(\displaystyle{ \sqsubseteq}\) jest przechodnia.

Wobec czego relacja \(\displaystyle{ \sqsubseteq}\) jest relacją porządku, i para \(\displaystyle{ \left( \mathbb{S},\sqsubseteq\right) }\) jest zbiorem uporządkowanym.


Ustalmy teraz dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{S}}\), i pokażmy, że ten łańcuch ma supremum.

Dla dowolnego ustalonego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{S}}\), dla dowolnego elementu \(\displaystyle{ x\in X}\) , ponieważ \(\displaystyle{ \mathcal{R} }\) jest rozkładem zbioru \(\displaystyle{ X,}\) więc istnieje dokładnie jeden zbiór \(\displaystyle{ A\in\mathcal{R}}\) tego rozkładu zawierający element \(\displaystyle{ x}\)- będziemy ten zbiór oznaczać jako \(\displaystyle{ \left[ x\right] _{\mathcal {R}}.}\)

Jako supremum tego łańcucha zdefiniujmy:

\(\displaystyle{ \mathbb{B}_0=\left\{ \bigcup_{\mathcal{R} \in\mathbb{D}} \left[ x\right] _{\mathcal{R} } \Bigl| \ \ x\in X\right\} }\),

rodzinę, dla dowolnego \(\displaystyle{ x\in X}\) , sum mnogościowych zbiorów zawierających element \(\displaystyle{ x}\) po kolejnych rozkładach z łańcucha \(\displaystyle{ \mathbb{D}}\), i tak po całej płaszczyźnie zbioru \(\displaystyle{ X}\).

Wtedy \(\displaystyle{ \mathbb{B}_0}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), gdyż zawsze \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset X}\), więc również \(\displaystyle{ \bigcup_{\mathcal{R} \in\mathbb{D}}\left[ x\right] _{\mathcal{R}} \subset X}\), i tak dla dowolnego \(\displaystyle{ x\in X}\), a więc rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\).


Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem zbioru \(\displaystyle{ X}\).

Mamy \(\displaystyle{ \bigcup\mathbb{B}_0 \subset X}\) (suma podzbiorów zbioru \(\displaystyle{ X}\)).

Aby pokazać inkluzję w drugą stronę, to weźmy element \(\displaystyle{ x\in X}\), i ustalmy rozkład \(\displaystyle{ \mathcal{R}\in\mathbb{D} \neq \left\{ \right\}}\). Wtedy \(\displaystyle{ x\in \left[ x\right] _{\mathcal{R}}}\), a więc tym bardziej \(\displaystyle{ x\in \bigcup_{\mathcal{R} \in \mathbb{D}} \left[ x\right] _{\mathcal{R}}}\), i dalej \(\displaystyle{ x \in \bigcup_{x\in X} \left( \bigcup_{\mathcal{R} \in \mathbb{D}} \left[ x\right] _{\mathcal {R}} \right) = \bigcup \mathbb{B}_0}\), a więc \(\displaystyle{ x\in \bigcup\mathbb{B}_0}\), i \(\displaystyle{ \bigcup\mathbb{B}_0=X.}\)


Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}_0}\) będzie rodziną zbiorów rozłącznych- nie będzie to łatwe.

W tym celu weźmy dwa zbiory z rodziny \(\displaystyle{ \mathbb{B}_0}\), które się przecinają, i pokażmy, że są równe. Tzn. weźmy zbiory postaci: \(\displaystyle{ \bigcup_{ \mathcal{R}\in\mathbb{D}} \left[ x_1\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ x_1\in X,}\) oraz weźmy zbiór postaci \(\displaystyle{ \bigcup_{\mathcal{R} \in \mathbb{D}} \left[ x_2\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ x_2\in X,}\) zbiory takie, że te zbiory się przecinają, tzn. niech \(\displaystyle{ z}\) będzie wspólnym elementem tych dwóch sum. Wtedy \(\displaystyle{ z \in \left[ x_1\right] _{\mathcal{R}_1}}\), gdzie \(\displaystyle{ \mathcal{R}_1\in\mathbb{D},}\) i \(\displaystyle{ z\in \left[ x_2\right] _{\mathcal{R}_2}}\), gdzie \(\displaystyle{ \mathcal{R}_2\in\mathbb{D}}\). Ponieważ \(\displaystyle{ \mathcal{R}_1, \mathcal{R}_2\in\mathbb{D}}\), a rodzina \(\displaystyle{ \mathbb{D}}\) jest łańcuchem, więc \(\displaystyle{ \mathcal{R}_1\sqsubseteq \mathcal{R}_2}\) lub \(\displaystyle{ \mathcal{R}_2 \sqsubseteq \mathcal{R}_1. }\)


Jeśli \(\displaystyle{ \mathcal{R}_1\sqsubseteq\mathcal{R}_2}\), ponieważ \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}_1} \in \mathcal{R}_1,}\) i \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \in \mathcal{R}_2}\) (z definicji tych, że zbiorów), oraz \(\displaystyle{ z\in \left[ x_1\right] _{\mathcal{R}_1} \cap \left[ x_2\right] _{\mathcal{R}_2}}\), więc korzystając z definicji relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}_1}\subset \left[ x_2\right] _{\mathcal{R}_2}.}\)

Wykażemy teraz, że dla dowolnego rozkładu \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\), takiego, że \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}} \supset \left[ x_2\right] _{\mathcal{R}_2}}\), mamy: \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}}=\left[ x_1\right] _{\mathcal{R}}. }\)

Niech \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\) będzie rozkładem tego łańcucha, takim, że:\(\displaystyle{ \left[ x_1\right] _{\mathcal{R}} \supset \left[ x_2\right] _{\mathcal{R}_2}.}\) Mamy \(\displaystyle{ x_2 \in \left[ x_2\right] _{\mathcal{R}_2} \subset \left[ x_1\right] _{\mathcal{R}}}\), a więc \(\displaystyle{ x_2\in \left[ x_1\right] _{\mathcal{R}} \in \mathcal{R}.}\) I mamy: \(\displaystyle{ x_2 \in \left[ x_2\right] _{\mathcal{R}} \in\mathcal{R}}\), a więc ponieważ istnieje dokładnie jeden, a więc co najwyżej jeden, zbiór rozkładu \(\displaystyle{ \mathcal{R}}\) zawierający element \(\displaystyle{ x_2}\), więc: \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}= \left[ x_2\right] _{\mathcal{R}}.}\)

Podzielmy teraz rodzinę \(\displaystyle{ \mathbb{D}}\) na dwie podrodziny, dane jako:

\(\displaystyle{ \mathbb{D}_1=\left\{ \mathcal{R}\in\mathbb{D}: \ \ \left[ x_1\right] _{\mathcal {R}} \supset \left[ x_2\right] _{\mathcal{R}_2} \right\}}\), oraz
\(\displaystyle{ \mathbb{D}_2=\mathbb{D} \setminus \mathbb{D}_1=\left\{ \mathcal{R}\in\mathbb{D}: \ \left[ x_1\right] _{\mathcal{R}} \not\supset \left[ x_2\right] _{\mathcal {R}_2} \right\}.}\)

Wtedy \(\displaystyle{ \mathbb{D}=\mathbb{D}_1 \cup \mathbb{D}_2.}\)

Na mocy faktu udowodnionego powyżej, łatwo jest pokazać, że:

\(\displaystyle{ \left\{ \left[ x_1\right] _{\mathcal{R}}: \ \mathcal{R}\in \mathbb{D}_1 \right\}=\left\{ \left[ x_2\right] _{\mathcal{R}}: \ \mathcal{R}\in \mathbb{D}_1 \right\}}\),

gdyż jeśli \(\displaystyle{ A}\) jest zbiorem z rodziny po lewej stronie równości, to \(\displaystyle{ A=\left[ x_1\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ \mathcal{R}\in\mathbb{D}_1}\), wtedy, z definicji rodziny \(\displaystyle{ \mathbb{D}_1}\), mamy: \(\displaystyle{ \mathcal{R}\in \mathbb{D}}\) i \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}\supset \left[ x_2\right] _{\mathcal{R}_2}}\), a więc na mocy faktu udowodnionego powyżej otrzymujemy: \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}}=\left[ x_1\right] _{\mathcal{R}}=A\in \left\{ \left[ x_2\right] _{\mathcal{R}}: \ \mathcal{R}\in \mathbb{D}_1 \right\}}\), co dowodzi inkluzji w prawo. Podobnie prosto dowodzimy inkluzję w lewo, a więc te dwie rodziny zbiorów są równe. Ponieważ dla dowolnej ustalonej rodziny zbiorów istnieje tylko jedna suma tej rodziny, więc: \(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}_1} \left[ x_1\right] _{\mathcal{R}}= \bigcup_{\mathcal{R} \in \mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}}.}\)

Mamy:

\(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}} \left[ x_1\right] _{\mathcal{R}}= \bigcup_{\mathcal{R}\in \mathbb{D}_1 \cup \mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}}=\left( \bigcup_{\mathcal{R}\in \mathbb{D}_1} \left[ x_1\right] _{\mathcal{R}} \right) \cup \left( \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}} \right) = \left( \bigcup_{\mathcal{R}\in \mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}} \right) \cup \left( \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}} \right).}\)

Wykażemy teraz, że: \(\displaystyle{ \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_2\right] _{\mathcal{R}}\subset \left[ x_2\right] _{\mathcal{R}_2}.}\)

Niech \(\displaystyle{ \mathcal{R}\in \mathbb{D}_2}\). Wtedy \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\) i \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}\not\supset \left[ x_2\right] _{\mathcal{R}_2}}\). Wtedy \(\displaystyle{ \mathcal{R}, \mathcal{R}_2\in\mathbb{D}}\), a rodzina \(\displaystyle{ \mathbb{D}}\) jest łańcuchem, więc \(\displaystyle{ \mathcal{R} \sqsubseteq \mathcal{R}_2}\) lub \(\displaystyle{ \mathcal{R}_2 \sqsubseteq\mathcal{R}}\). Przypuśćmy na moment, że \(\displaystyle{ \mathcal{R}_2 \sqsubseteq \mathcal{R}}\). Wtedy \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \in \mathcal{R}_2}\), i \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}} \in \mathcal{R}}\), i \(\displaystyle{ x_1 \in \left[ x_1\right] _{\mathcal{R}}}\) i \(\displaystyle{ x_1 \in \left[ x_2\right] _{\mathcal{R}_2}}\), stosując zatem definicję relacji \(\displaystyle{ \sqsubseteq}\), wnioskujemy, że \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2}\subset \left[ x_1\right] _{\mathcal{R}}}\) , a z definicji rodziny \(\displaystyle{ \mathbb{D}_2 }\) mamy, że tak nie jest- sprzeczność.
Wobec czego musi zajść relacja w drugą stronę, czyli: \(\displaystyle{ \mathcal{R} \sqsubseteq\mathcal{R}_2}\), wtedy \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}}\in \mathcal{R}}\), i \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2}\in\mathcal{R}_2}\) i oczywiście \(\displaystyle{ x_2 \in \left[ x_2\right] _{\mathcal{R}} \cap \left[ x_2\right] _{\mathcal{R}_2}}\), a więc, z definicji relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}}\subset \left[ x_2\right] _{\mathcal{R}_2}}\). Z dowolności wyboru rozkładu \(\displaystyle{ \mathcal{R} \in \mathbb{D}_2}\), otrzymujemy, że dla dowolnego rozkładu \(\displaystyle{ \mathcal{R} \in \mathbb{D}_2}\): \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}}\subset \left[ x_2\right] _{\mathcal{R}_2}}\), więc również: \(\displaystyle{ \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_2\right] _{\mathcal{R}}\subset \left[ x_2\right] _{\mathcal{R}_2}.}\)

Wykażemy teraz, że: \(\displaystyle{ \mathcal{R}_2\in \mathbb{D}_1.}\)

Mamy \(\displaystyle{ \mathcal{R}_2\in\mathbb{D}}\). Pozostaje pokazać, że \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}_2} \supset \left[ x_2\right] _{\mathcal{R}_2}}\). Mamy \(\displaystyle{ x_1 \in \left[ x_2\right] _{\mathcal{R}_2} \in\mathcal{R}_2}\), i mamy: \(\displaystyle{ x_1 \in \left[ x_1\right] _{\mathcal{R}_2}\in\mathcal{R}_2}\), a więc \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}_2}= \left[ x_2\right] _{\mathcal{R}_2} }\), na podstawie jedyności zbioru \(\displaystyle{ \left[ x\right] _{\mathcal{R}_2}}\), a więc w szczególności mamy inkluzję w lewo, i \(\displaystyle{ \mathcal{R}_2\in \mathbb{D}_1}\). A zatem \(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}_1}\left[ x_2\right] _{\mathcal{R}} \supset \left[ x_2\right] _{\mathcal{R}_2}.}\)

Wykażemy teraz, że: \(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}} \subset \left[ x_2\right] _{\mathcal{R}_2}.}\)
Niech \(\displaystyle{ \mathcal{R}\in \mathbb{D}_2}\). Wtedy \(\displaystyle{ \mathcal{R}\in \mathbb{D}}\) i \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}\not\supset \left[ x_2\right] _{\mathcal{R}_2}.}\) Mamy \(\displaystyle{ \mathcal{R}\in \mathbb{D}}\), i \(\displaystyle{ \mathcal{R}_2\in\mathbb{D}}\), a \(\displaystyle{ \mathbb{D}}\) jest łańcuchem, więc \(\displaystyle{ \mathcal{R} \sqsubseteq \mathcal{R}_2}\) lub \(\displaystyle{ \mathcal{R}_2\sqsubseteq \mathcal{R}.}\) Wtedy \(\displaystyle{ \mathcal{R}_2 \not\sqsubseteq\mathcal{R}}\). Przypuśćmy nie wprost na moment, że \(\displaystyle{ \mathcal{R}_2 \sqsubseteq\mathcal{R}}\). Wtedy \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \in \mathcal{R}_2}\), \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}\in\mathcal{R},}\) i \(\displaystyle{ x_1\in\left[ x_2\right] _{\mathcal{R}_2}}\) i oczywiście \(\displaystyle{ x_1 \in \left[ x_1\right] _{\mathcal{R}}}\), a więc zbiór \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \cap \left[ x_1\right] _{\mathcal{R}}}\) jest niepusty, stosując zatem definicję relacji \(\displaystyle{ \sqsubseteq}\), wnioskujemy, że \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \subset \left[ x_1\right] _{\mathcal{R}}}\)- a my mamy, że tak nie jest- sprzeczność.
Wobec czego \(\displaystyle{ \mathcal{R}_2 \not\sqsubseteq \mathcal{R}}\), zatem musi być \(\displaystyle{ \mathcal{R} \sqsubseteq \mathcal{R}_2}\). Mamy \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}} \in \mathcal{R}}\), \(\displaystyle{ \left[ x_2\right] _{\mathcal{R}_2} \in \mathcal{R}_2}\) i \(\displaystyle{ x_1 \in \left[ x_1\right] _{\mathcal{R}} \cap \left[ x_2\right] _{\mathcal{R}_2}}\), stosując zatem definicję relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x_1\right] _{\mathcal{R}}\subset \left[ x_2\right] _{\mathcal{R}_2}}\). Zatem, z dowolności wyboru \(\displaystyle{ \mathcal{R}\in\mathbb{D}_2}\), otrzymujemy, że dla dowolnego rozkładu \(\displaystyle{ \mathcal{R} \in\mathbb{D}_2}\), mamy: \(\displaystyle{ \left[ x_1\right] _{\mathcal{R} }\subset \left[ x_2\right] _{\mathcal{R} _2} }\), więc również \(\displaystyle{ \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}} \subset \left[ x_2\right] _{\mathcal{R}_2}.}\)

A zatem:

\(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}} \left[ x_1\right] _{\mathcal{R}}= \underbrace {\left( \bigcup_{\mathcal{R}\in\mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}} \right)}_{\supset \left[ x_2\right] _{\mathcal{R}_2} } \cup \underbrace {\left( \bigcup_{\mathcal{R}\in \mathbb{D}_2} \left[ x_1\right] _{\mathcal{R}} \right) }_{\subset \left[ x_2\right] _{\mathcal{R}_2} } = \bigcup_{\mathcal{R}\in \mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}}.}\)

Tymczasem:

\(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}} \left[ x_2\right] _{\mathcal{R}}= \bigcup_{\mathcal{R}\in \mathbb{D}_1 \cup \mathbb{D}_2} \left[ x_2\right] _{\mathcal{R}}= \underbrace{ \left( \bigcup_{\mathcal{R}\in\mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}} \right) }_{\supset \left[ x_2\right] _{\mathcal{R}_2} } \cup \underbrace{\left( \bigcup_{\mathcal{R}\in\mathbb{D}_2} \left[ x_2\right] _{\mathcal{R}} \right) }_{\subset \left[ x_2\right] _{\mathcal{R}_2} }= \bigcup_{\mathcal{R}\in \mathbb{D}_1} \left[ x_2\right] _{\mathcal{R}} .}\)

Łącząc te dwie równości, otrzymujemy:

\(\displaystyle{ \bigcup_{\mathcal{R}\in\mathbb{D}} \left[ x_1\right] _{\mathcal{R}}= \bigcup_{\mathcal{R}\in\mathbb{D}} \left[ x_2\right] _{\mathcal{R}},}\)

co należało pokazać.


Jeśli \(\displaystyle{ \mathcal{R}_2\sqsubseteq \mathcal{R}_1}\), to niestety musimy analogicznie powtórzyć dowód. I niestety nie widzę innego wyjścia. Może napiszę w skrócie, jest to symetryczne rozumowanie:
ANALOGICZNY DOWÓD TEGO FAKTU::    
Wobec czego rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rodziną zbiorów rozłącznych.


Pokażmy jeszcze, że \(\displaystyle{ \mathbb{B}_0}\) jest rodziną zbiorów niepustych.

Aby to pokazać, to weźmy \(\displaystyle{ x\in X}\). I ustalmy rozkład \(\displaystyle{ \mathcal{R}\in\mathbb{D} \neq \left\{ \right\} }\). Wtedy \(\displaystyle{ x\in \left[ x\right] _{\mathcal{R}}}\), a więc tym bardziej \(\displaystyle{ x \in \bigcup_{\mathcal{R}'\in\mathbb{D}} \left[ x\right] _{\mathcal{R}'}}\), a więc zbiór \(\displaystyle{ \bigcup_{\mathcal{R}'\in\mathbb{D}} \left[ x\right] _{\mathcal{R}'}}\) jest niepusty, i rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rodziną zbiorów niepustych.

A zatem rodzina \(\displaystyle{ \mathbb{B}_0}\) jest rozkładem, i \(\displaystyle{ \mathbb{B}_0\in \mathbb{S}.}\)


Wykażemy teraz, że \(\displaystyle{ \mathbb{B}_0= \bigvee \mathbb{D}.}\)


Wykażemy, że \(\displaystyle{ \mathbb{B}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\).

W tym celu weźmy rozkład \(\displaystyle{ \mathcal{R}_0\in\mathbb{D}}\), i pokażmy, że \(\displaystyle{ \mathcal{R}_0\sqsubseteq \mathbb{B}_0}\).

W tym celu weźmy zbiory \(\displaystyle{ A\in \mathcal{R}_0}\), \(\displaystyle{ B\in \mathbb{B}_0}\) takie, że \(\displaystyle{ A \cap B \neq \left\{ \right\}}\), czyli takie, że te dwa zbiory się przecinają, i pokażmy, że \(\displaystyle{ A\subset B}\).

Ponieważ \(\displaystyle{ B\in \mathbb{B}_0}\), to \(\displaystyle{ B= \bigcup_{\mathcal{R}\in \mathbb{D}} \left[ x\right] _{\mathcal{R}}}\), gdzie \(\displaystyle{ x\in X}\). Ponieważ zbiór \(\displaystyle{ A}\) przecina zbiór \(\displaystyle{ B}\), to zbiór \(\displaystyle{ A}\) przecina tą sumę, więc (i ponieważ łańcuch \(\displaystyle{ \mathbb{D}}\) jest niepusty ), więc zbiór \(\displaystyle{ A}\) przecina pewien zbiór tej rodziny, gdyż mamy prosty fakt, że jeśli zbiór jest rozłączny z każdym zbiorem pewnej rodziny, to ten zbiór jest rozłączny z sumą tej rodziny, a zbiór \(\displaystyle{ A}\) przecina sumę. Wobec czego, i ponieważ nasza rodzina jest niepusta, więc otrzymujemy, że zbiór \(\displaystyle{ A}\) przecina pewien zbiór tej rodziny, tzn. \(\displaystyle{ A \cap \left[ x\right] _{\mathcal{R}} \neq \left\{ \right\}}\) , gdzie \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\).

Ponieważ \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\), \(\displaystyle{ \mathcal{R}_0\in\mathbb{D}}\), a \(\displaystyle{ \mathbb{D}}\) jest to łańcuch, więc \(\displaystyle{ \mathcal{R}_0 \sqsubseteq \mathcal{R}}\) lub \(\displaystyle{ \mathcal{R}\sqsubseteq\mathcal{R}_0.}\)

Jeśli \(\displaystyle{ \mathcal{R}_0\sqsubseteq \mathcal{R}}\), ponieważ \(\displaystyle{ A\in \mathcal{R}_0}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in\mathcal{R}}\) i \(\displaystyle{ A \cap \left[ x\right] _{\mathcal{R}} \neq \left\{ \right\} }\), więc z definicji relacji \(\displaystyle{ \sqsubseteq}\), otrzymujemy:
\(\displaystyle{ A\subset \left[ x\right] _{\mathcal{R}}}\). Ponieważ \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\), więc \(\displaystyle{ A\subset \left[ x\right] _{\mathcal{R}} \subset \bigcup_{\mathcal{R}\in \mathbb{D}} \left[ x\right] _{\mathcal{R}}=B}\), czyli \(\displaystyle{ A\subset B}\), co należało pokazać.

A jeśli \(\displaystyle{ \mathcal{R}\sqsubseteq \mathcal{R}_0}\), ponieważ \(\displaystyle{ A\in\mathcal{R}_0}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in \mathcal{R}}\) i \(\displaystyle{ A \cap \left[ x\right] _{\mathcal{R}} \neq \left\{ \right\}}\) , więc na podstawie definicji relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset A}\). Mamy \(\displaystyle{ x\in \left[ x\right] _{\mathcal{R}}\subset A}\), a więc \(\displaystyle{ x\in A}\). Mamy \(\displaystyle{ A\in \mathcal{R}_0}\) i \(\displaystyle{ x\in \left[ x\right] _{\mathcal{R}_0} \in \mathcal{R}_0}\), więc z jedyności zbioru postaci \(\displaystyle{ \left[ a\right] _{\mathcal{R}_0}}\), więc: \(\displaystyle{ A=\left[ x\right] _{\mathcal{R}_0}}\). Mamy \(\displaystyle{ \mathcal{R}_0\in\mathbb{D}}\), a więc \(\displaystyle{ A=\left[ x\right] _{\mathcal{R}_0}\subset \bigcup_{\mathcal{R} \in \mathbb{D}} \left[ x\right] _{\mathcal{R}} =B}\), czyli \(\displaystyle{ A\subset B}\).

Wobec czego \(\displaystyle{ \mathcal{R}_0 \sqsubseteq \mathbb{B}_0}\), i \(\displaystyle{ \mathbb{B}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\).


Pozostaje pokazać, że jest to najmniejsze ograniczenie górne dla \(\displaystyle{ \mathbb{D}}\).

Udowodnijmy najpierw pewien lemat.

Jeśli \(\displaystyle{ x\in X}\), a \(\displaystyle{ \mathcal{R} \in \mathbb{D}}\) jest rozkładem tego łańcucha, a rozkład \(\displaystyle{ \mathcal{R}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), a \(\displaystyle{ B\in \mathcal{R}_0}\) jest zbiorem tego rozkładu i jeśli przekrój \(\displaystyle{ \left[ x\right] _{\mathcal{R} } \cap B}\) jest niepusty, to \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset B.}\)

PROSTY DOWÓD TEGO FAKTU:

\(\displaystyle{ \mathcal{R}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), a \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\), więc \(\displaystyle{ \mathcal{R}\sqsubseteq \mathcal{R}_0}\), a zatem ponieważ \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in\mathcal{R}}\), \(\displaystyle{ B\in\mathcal{R}_0 }\) i zbiór \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \cap B}\) jest niepusty, więc stosując definicję relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset B}\), co kończy dowód lematu.


Aby wykazać, że rozkład \(\displaystyle{ \mathbb{B}_0}\) jest supremum łańcucha \(\displaystyle{ \mathbb{D}}\), to niech \(\displaystyle{ \mathcal{R}_0\in \mathbb{S}}\) będzie ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\). Pokażemy, że \(\displaystyle{ \mathbb{B}_0 \sqsubseteq \mathcal{R}_0}\).

W tym celu weźmy zbiory \(\displaystyle{ A\in\mathbb{B}_0}\) oraz zbiór \(\displaystyle{ B\in \mathcal{R}_0}\), takie, że \(\displaystyle{ A \cap B \neq \left\{ \right\}}\) , czyli takie zbiory, które się przecinają, i pokażmy, że \(\displaystyle{ A\subset B.}\)

Ponieważ \(\displaystyle{ A\in\mathbb{B}_0}\), to \(\displaystyle{ A= \bigcup_{ \mathcal{R}\in\mathbb{D}} \left[ x\right] _{ \mathcal{R}}}\) , gdzie \(\displaystyle{ x\in X}\). Ponieważ zbiór \(\displaystyle{ B}\) przecina zbiór \(\displaystyle{ A}\), to zbiór \(\displaystyle{ B}\) przecina tą sumę, więc ( i ponieważ rodzina \(\displaystyle{ \left\{ \left[ x\right] _{ \mathcal{R}}: \ \ \mathcal{R}\in \mathbb{D} \right\}}\) jest niepusta, gdyż łańcuch \(\displaystyle{ \mathbb{D}}\) jest niepusty ) , więc zbiór \(\displaystyle{ B}\) przecina pewien zbiór tej rodziny, tzn. \(\displaystyle{ B \cap \left[ x\right] _{\mathcal{R}} \neq \left\{ \right\}}\), gdzie \(\displaystyle{ \mathcal{R}\in\mathbb{D}}\). Wtedy \(\displaystyle{ x\in X}\), \(\displaystyle{ \mathcal{R}\in \mathbb{D}}\), rozkład \(\displaystyle{ \mathcal{R}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), i zbiór \(\displaystyle{ B\in \mathcal{R}_0}\) jest zbiorem tego rozkładu, oraz przekrój \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \cap B}\) jest niepusty, stosując zatem lemat powyżej otrzymujemy, że: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset B.}\)

Niech teraz \(\displaystyle{ \mathcal{R} ^{\prime} \in \mathbb{D}.}\)

Ponieważ również \(\displaystyle{ \mathcal{R}\in \mathbb{D}}\), a \(\displaystyle{ \mathbb{D}}\) jest to łańcuch, więc \(\displaystyle{ \mathcal{R} ^{\prime} \sqsubseteq \mathcal{R}}\) lub \(\displaystyle{ \mathcal{R} \sqsubseteq \mathcal{R} ^{\prime}.}\)

Jeśli \(\displaystyle{ \mathcal{R}'\sqsubseteq \mathcal{R}}\), to ponieważ \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in \mathcal{R}}\), \(\displaystyle{ \left[ x \right] _{\mathcal{R}'}\in \mathcal{R}'}\) i oczywiście \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}} \cap \left[ x\right] _{\mathcal{R}'}}\), więc \(\displaystyle{ \left[ x\right] _{\mathcal{R}'}\subset \left[ x\right] _{\mathcal{R}}\subset B}\), a więc \(\displaystyle{ \left[ x\right] _{\mathcal{R}'}\subset B.}\)

W pozostałym przypadku \(\displaystyle{ \mathcal{R}\sqsubseteq \mathcal{R}'.}\)

Wtedy \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \in\mathcal{R}}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}'}\in\mathcal{R}'}\) i oczywiście \(\displaystyle{ x \in \left[ x\right] _{\mathcal{R}} \cap \left[ x\right] _{\mathcal{R}'}}\), stosując zatem definicję relacji \(\displaystyle{ \sqsubseteq}\) otrzymujemy: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\subset \left[ x\right] _{\mathcal{R}'}.}\) Mamy, że zbiór \(\displaystyle{ B}\) przecina zbiór \(\displaystyle{ \left[ x\right] _{\mathcal{R}}}\), tzn. przekrój \(\displaystyle{ B \cap \left[ x\right] _{\mathcal{R}}}\) jest niepusty. Istnieje więc element \(\displaystyle{ y \in B \cap \left[ x\right] _{\mathcal{R}} }\), wtedy \(\displaystyle{ y\in B}\) i \(\displaystyle{ y\in \left[ x\right] _{\mathcal{R}} \subset \left[ x\right] _{\mathcal{R}'}}\), a więc \(\displaystyle{ y \in B \cap \left[ x\right] _{\mathcal{R}'} }\), a więc również przekrój \(\displaystyle{ B \cap \left[ x\right] _{\mathcal{R}'}}\) jest niepusty. Ponieważ \(\displaystyle{ \mathcal{R}'\in\mathbb{D}}\), a \(\displaystyle{ \mathcal{R}_0}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), więc \(\displaystyle{ \mathcal{R}'\sqsubseteq \mathcal{R}_0.}\) Mamy \(\displaystyle{ B\in\mathcal{R}_0}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}'} \in \mathcal{R}'}\) i \(\displaystyle{ B \cap \left[ x\right] _{\mathcal{R}'} \neq \left\{ \right\}}\), stosując zatem definicję relacji \(\displaystyle{ \sqsubseteq}\), wnioskujemy, że: \(\displaystyle{ \left[ x\right] _{\mathcal{R}'}\subset B.}\)

Otrzymujemy zatem, że dla dowolnego rozkładu \(\displaystyle{ \mathcal{R}'\in\mathbb{D}}\): \(\displaystyle{ \left[ x\right] _{\mathcal{R}'}\subset B}\),

więc również: \(\displaystyle{ A= \bigcup_{\mathcal{R}'\in\mathbb{D}} \left[ x\right] _{\mathcal{R}'}\subset B}\), czyli \(\displaystyle{ A\subset B}\), co należało pokazać.

Wobec czego \(\displaystyle{ \mathbb{B}_0 \sqsubseteq \mathcal{R}_0}\), i otrzymujemy, że rozkład \(\displaystyle{ \mathbb{B}_0}\) jest najmniejszym ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\), a więc rozkład \(\displaystyle{ \mathbb{B}_0 }\) jest supremum dla \(\displaystyle{ \mathbb{D}}\), tzn. \(\displaystyle{ \mathbb{B}_0= \bigvee \mathbb{D}}\), i łańcuch \(\displaystyle{ \mathbb{D}}\) ma supremum.\(\displaystyle{ \square}\) :lol: 8-)
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: Rozkłady zbiorów

Post autor: Dasio11 »

Przy standardowym utożsamieniu rozkładów zbioru \(\displaystyle{ X}\) z relacjami równoważności na \(\displaystyle{ X}\) Twój porządek to zwykłe zawieranie między relacjami równoważności - oczywiste jest więc, że to częściowy porządek w którym każdy łańcuch ma supremum i infimum.
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: Rozkłady zbiorów

Post autor: Jakub Gurak »

Rozumiem, że suma niepustego łańcucha, względem inkluzji, relacji przechodnich w \(\displaystyle{ X}\), jest relacją przechodnią w \(\displaystyle{ X}\), tak :?:
Nie jestem przekonany, czy jest taki fakt, w związku z czym, suma niepustego łańcucha relacji równoważności jest relacją równoważności, tak :?:
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: Rozkłady zbiorów

Post autor: Dasio11 »

Tak.
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Rozkłady zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 14 mar 2022, o 18:59 Rozumiem, że suma niepustego łańcucha, względem inkluzji, relacji przechodnich w \(\displaystyle{ X}\), jest relacją przechodnią w \(\displaystyle{ X}\), tak :?:
Nie jestem przekonany, czy jest taki fakt,
A spróbowałeś udowodnić? Dowód jest szybki i standardowy.

JK
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: Rozkłady zbiorów

Post autor: Jakub Gurak »

Udowodniłem wczoraj, że jeśli mamy niepusty zbiór \(\displaystyle{ X}\), oraz rozkład \(\displaystyle{ \mathcal{R}}\) zbioru \(\displaystyle{ X}\), oraz podrodzinę \(\displaystyle{ \mathbb{A}\subset \mathcal{R}}\) (czyli zbiór złozony z niektórych zbiorów tego rozkładu), to jeśli wyrzucimy z tego rozkładu, zbiory tej podrodziny \(\displaystyle{ \mathbb{A}}\), jako elementy rozkładu, to otrzymamy rozkład zbioru \(\displaystyle{ X \setminus \bigcup \mathbb{A}}\). Udowodniłem też, że jeśli mamy dwa zbiory \(\displaystyle{ X,Y}\), oraz dowolną relację \(\displaystyle{ R}\) między nimi, to ta relacja ma domknięcie wśród funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) (oczywiście nie zawsze) , ale dokładnie wtedy, gdy ta relacja jest funkcją częściową. Przedstawię teraz dowody tych ciekawych faktów.


Dla rozkładów, udowodnijmy najpierw, pewien prostszy fakt.

Niech \(\displaystyle{ X}\) będzie niepustym zbiorem, a \(\displaystyle{ \mathcal{R}}\) rozkładem zbioru \(\displaystyle{ X}\), a \(\displaystyle{ A\in \mathcal{R}}\) zbiorem tego rozkładu. Wykazemy, że rodzina \(\displaystyle{ \mathcal{R} \setminus \left\{ A\right\} }\) jest rozkładem zbioru \(\displaystyle{ X \setminus A}\)( czyli po wyrzuceniu z rozkładu, jednego zbioru \(\displaystyle{ A}\), jako elementu, otrzymamy rozkład zbioru \(\displaystyle{ X \setminus A}\) ).

Przypomnijmy jeszcze taki prosty fakt, że jeśli \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów rozłącznych, a \(\displaystyle{ \mathbb{A}\subset\mathbb{B}}\) jej podrodziną, to suma uogólniona dopełnienia tej podrodziny (do zbioru \(\displaystyle{ \mathbb{B}}\)) jest dopełnieniem sumy uogólnionej (do zbioru \(\displaystyle{ \bigcup {\mathbb{B}}}\) ) - jest to w miarę prosty fakt.

Przejdźmy do dowodu poprzedniego faktu.
DOWÓD TEGO FAKTU::    
Przejdżmy do naszego głównego problemu.

Niech \(\displaystyle{ X}\) bedzie niepustym zbiorem, a \(\displaystyle{ \mathcal{R}}\) rozkładem zbioru \(\displaystyle{ X}\). Niech \(\displaystyle{ \mathbb{A}\subset \mathcal{R}}\)- czyli jest to rodziną złożona z niektórych zbioru tego rozkładu . Wykazemy, że jeśli z rozkładu \(\displaystyle{ \mathcal{R}}\) wyrzucimy, jako elementy, zbiory z podrodziny \(\displaystyle{ \mathbb{A}}\), to otrzymamy rozkład zbiioru \(\displaystyle{ X \setminus \bigcup\mathbb{A}}\), tzn. wykazemy, że rodzina \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rozkładem zbioru \(\displaystyle{ X \setminus \bigcup\mathbb{A}.}\)

DOWÓD TEGO CIEKAWEGO FAKTU:

Po pierwsze, musimy wykazać, że rodzina \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rodzina podzbiorów \(\displaystyle{ X \setminus \bigcup \mathbb{A}.}\)

W tym celu weźmy zbiór \(\displaystyle{ A\in \mathcal{R} \setminus \mathbb{A}}\) i pokazmy, że \(\displaystyle{ A\subset X \setminus \bigcup\mathbb{A}}\).

Ponieważ \(\displaystyle{ \mathcal{R} }\) jest rozkładem zbioru \(\displaystyle{ X}\), a więc rodziną podzbiorów zbioru \(\displaystyle{ X}\), więc \(\displaystyle{ A\subset X}\). Pokazemy, że \(\displaystyle{ A\subset X \setminus \bigcup \mathbb{A}.}\) Niech \(\displaystyle{ a\in A}\). Wtedy \(\displaystyle{ a\in X.}\) Przypuśćmy nie wprost, że \(\displaystyle{ a\in \bigcup \mathbb{A}}\). Wtedy \(\displaystyle{ a\in B}\), gdzie \(\displaystyle{ B\in \mathbb{A}}\). Również \(\displaystyle{ a\in A}\), gdzie \(\displaystyle{ A\in \mathcal{R}}\). Ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkladem, a \(\displaystyle{ B\in \mathbb{A} \subset \mathcal{R}}\), a więc \(\displaystyle{ A,B\in\mathcal{R}}\), i \(\displaystyle{ A \neq B}\), bo \(\displaystyle{ A\not\in\mathbb{A}}\), a \(\displaystyle{ B\in \mathbb{A}}\); a zatem \(\displaystyle{ A \neq B}\), a zatem te dwa rożne zbiory \(\displaystyle{ A,B}\) muszą być rozłączne, lecz \(\displaystyle{ a\in A \cap B-}\) sprzeczność.

Wobec czego \(\displaystyle{ a\not\in \bigcup\mathbb{A}}\), a zatem \(\displaystyle{ a\in X \setminus \bigcup\mathbb{A}}\), i \(\displaystyle{ A\subset X \setminus \bigcup\mathbb{A};}\) i rodzina \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X \setminus \bigcup\mathbb{A}.}\)

I mamy, ponieważ \(\displaystyle{ \mathcal{R},}\) jako rozklad, jest rodziną zbiorów rozłącznych, a \(\displaystyle{ \mathbb{A}\subset \mathcal{R}}\), więc:

\(\displaystyle{ \bigcup \left( \mathbb{A}'= \mathcal{R} \setminus \mathbb{A}\right)= X \setminus \bigcup \mathbb{A}.}\)

I ponieważ \(\displaystyle{ \mathcal{R}}\), jako rozkład, jest rodziną zbiorów rozłącznych, więc \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rodziną zbiorów rozłącznych.

I \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rodzianą zbiorów niepustych, gdyż rozkład \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów niepustych.

A zatem rodzina \(\displaystyle{ \mathcal{R} \setminus \mathbb{A}}\) jest rozkładem zbioru \(\displaystyle{ X \setminus \bigcup \mathbb{A}.}\)


Wykażemy jeszcze, zgodnie z zapowiedzią, że jesli mamy dwa zbiory \(\displaystyle{ X,Y,}\) oraz dowolną relację \(\displaystyle{ R}\) z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), to ta relacja \(\displaystyle{ R}\) ma domkniecie wśród funkcji częściowych (nie zawsze), lecz dokładnie wtedy, gdy ta relacja \(\displaystyle{ R}\) jest funkcją częściową (jeśli relacja \(\displaystyle{ R}\) jest funkcją częściową, to jej domknięcie jest jej równe, a jeśli nie jest- to w ogóle nie ma domknięcia).

DOWÓD TEGO FAKTU:

Jeśli relacja \(\displaystyle{ R}\) jest funkcją częściową, to \(\displaystyle{ S=R}\) jest domknięciem wśród funkcji częściowych , gdyż \(\displaystyle{ S\supset R}\), \(\displaystyle{ S}\) jest funkcją cześciową, i jeśli relacja \(\displaystyle{ T\supset R}\) jest funkcją częściową, to \(\displaystyle{ T\supset S=R.}\)

Wobec czego relacja \(\displaystyle{ S}\) jest domknięciem relacji \(\displaystyle{ R}\) wśród funkcji częściowych.


Jeśli relacja \(\displaystyle{ R}\) nie jest funkcją cześciową, to dla pewnych \(\displaystyle{ x\in X}\), \(\displaystyle{ y_1, y_2\in Y}\), mamy:

\(\displaystyle{ \neg \left[ \left( x,y_1\right) \in R \wedge \left( x,y _{2} \right) \in R \Longrightarrow y_1=y_2\right] }\) ,

skoro ta implikacja jest fałszywa, to wtedy \(\displaystyle{ \left( x,y_1\right) \in R,}\) i \(\displaystyle{ \left( x,y _{2} \right) \in R,}\) i \(\displaystyle{ y_1 \neq y_2.}\)

Przypuścmy, że istnieje domkn ięcie \(\displaystyle{ S}\) wśród funkcji częściowych.
Wtedy \(\displaystyle{ S\supset R \ni \left( x,y_1\right) ; \left( x,y_2\right)}\) , a zatem \(\displaystyle{ \left( x,y_2\right); (x,y_1) \in S}\) , gdzie \(\displaystyle{ y_1 \neq y_2}\), a więc relacja \(\displaystyle{ S}\) nie może być funkcją cześciową, a \(\displaystyle{ S}\) jest domknięciem wśród funkcji częściowych, więc powinno być funkcją częściową -sprzeczność.

Wobec czego nie istnieje domknięcie relacji \(\displaystyle{ R}\) wśród funkcji częściowych. \(\displaystyle{ \square}\)

:lol: 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: Rozkłady zbiorów

Post autor: Jakub Gurak »

Jakub Gurak pisze: 23 lip 2022, o 16:39Niech \(\displaystyle{ X}\) będzie niepustym zbiorem, a \(\displaystyle{ \mathcal{R}}\) rozkładem zbioru \(\displaystyle{ X}\), a \(\displaystyle{ A\in \mathcal{R}}\) zbiorem tego rozkładu. Wykazemy, że rodzina \(\displaystyle{ \mathcal{R} \setminus \left\{ A\right\} }\) jest rozkładem zbioru \(\displaystyle{ X \setminus A}\)( czyli po wyrzuceniu z rozkładu, jednego zbioru \(\displaystyle{ A}\), jako elementu, otrzymamy rozkład zbioru \(\displaystyle{ X \setminus A}\) ).
Udało się dzisiaj zastosować ten fakt.

Tzn. wczoraj, na dobranoc, udowodniłem sobie, że koło domknięte na płaszczyźnię można rozłożyć na okregi, a przed chwilą, udowodniłem, że koło otwarte można rozłożyć na okręgi. Jednak zrobiłem to w sposób nieanalogiczny, lecz stosując zacytowany fakt. Udowodniłem też ostatnio, że jeśli mamy funkcję określoną na przedziale \(\displaystyle{ A\subset \RR}\) (i o wartościach rzeczywistych), funkcję słabo rosnącą, to po odbiciu jej wykresu względem osi \(\displaystyle{ y}\)- otrzymamy funkcję słabo malejącą. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ \left( x_0,y_0\right) \in \RR^2,}\) i niech \(\displaystyle{ r\in \RR_+}\) (tzn. \(\displaystyle{ r>0}\)). Niech \(\displaystyle{ X}\) będzie kołem domkniętym o środku w \(\displaystyle{ \left( x_0,y_0\right)}\) i promieniu \(\displaystyle{ r}\), tzn. niech :

\(\displaystyle{ X:= K\left( \left( x_0,y_0\right);r \right) =\left\{ \left( x,y\right) \in \RR^2: \ \ \left( x-x_0\right) ^{2}+\left( y-y_0\right)^2 \le r ^{2} \right\}.}\)

Wykażemy, że koło \(\displaystyle{ X}\) można rozłożyć na okręgi, tzn. istnieje rodzina okręgów o środku w punkcie \(\displaystyle{ \left( x_0, y_0\right)}\) będąca rozkładem koła \(\displaystyle{ X}\).
DOWÓD TEGO FAKTU::    
Wykażemy teraz, że (dla \(\displaystyle{ \left( x_0,y_0\right) \in \RR^2}\), dla \(\displaystyle{ r >0}\)), koło otwarte \(\displaystyle{ Y}\), czyli zbiór:

\(\displaystyle{ Y:=\left\{ \left( x,y\right) \in \RR^2: \left( x-x_0 \right) ^{2}+ \left( y-y_0\right) ^{2} < r^2 \right\}}\),

wtedy to koło otwarte \(\displaystyle{ Y}\) można rozłozyć na okregi, tzn. istnieje rodzina okręgów o środku w \(\displaystyle{ \left( x_0, y_0\right)}\) będąca rozkładem koła otwartego \(\displaystyle{ Y}\).

DOWÓD TEGO FAKTU ( :!: NIE ANALOGIICZNY) :

Rozważmy koło domknięte:

\(\displaystyle{ X= K\left( \left( x_0,y_0\right) ; r\right) }\);

o środku w punkcie \(\displaystyle{ \left( x_0,y_0\right)}\) i promieniu \(\displaystyle{ r.}\)

Na mocy dowodu powyżej istnieje rodzina \(\displaystyle{ \mathcal{R}}\), rodzina okręgów o środku w punkcie \(\displaystyle{ \left( x_0,y_0\right)}\) będąca rozkładem koła \(\displaystyle{ X.}\)

Rozważmy okrąg:

\(\displaystyle{ A:= O(\left( x_0,y_0\right); r )= \left\{ \left( x,y\right) \in\RR ^2: \ \left( x-x_0\right)^2 +\left( y-y_0\right)^2= r^2 \right\} .}\)

Pokażemy, że \(\displaystyle{ A\in \mathcal{R} .}\) Zauważmy, że \(\displaystyle{ \left( x_0+r ,y_0\right) \in X=\left\{ \left( x,y\right) \in \RR^2: \ \ \left( x-x_0\right) ^{2}+\left( y-y_0\right)^2 \le r^2 \right\} }\), gdyż:
\(\displaystyle{ \left( x_0+r-x_0\right) ^2 + \left( y_0-y_0\right) ^{2}= r^2+0^2=r^2 \le r^2}\),
a zatem \(\displaystyle{ p:= \left( x_0+r , y_0\right)\in X.}\) Niech \(\displaystyle{ B\in \mathcal{R}}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}}\), takim, że \(\displaystyle{ p\in B}\) (taki zbiór jest dokładnie jeden, bo \(\displaystyle{ \mathcal{R}}\) jest rozkładem koła \(\displaystyle{ X}\)). Pokażemy, że \(\displaystyle{ A=B.}\) Ponieważ \(\displaystyle{ \mathcal {R}}\) jest rodziną okregów, to zbiór \(\displaystyle{ B\in \mathcal{R}}\) jest okręgiem o śrosdku w \(\displaystyle{ \left( x_0,y_0\right)}\) i pewnym promieniu \(\displaystyle{ R \ge 0.}\) Pokażemy, że \(\displaystyle{ R=r}\). Ponieważ \(\displaystyle{ \left( x_0+r, y_0\right) = p\in B}\), więc: \(\displaystyle{ \left( x_0+r-x_0 \right) ^{2}+ \left( y_0-y_0\right) ^2= R^2}\), czyli \(\displaystyle{ r^2+0^2= r^2= R^2}\), i ponieważ \(\displaystyle{ r>0, R \ge 0}\), a zatem \(\displaystyle{ r=R.}\) A zatem: \(\displaystyle{ B= O\left( \left( x_0,y_0\right) ;R\right) = O\left( \left( x_0, y_0\right); r \right)=A.}\) Poniewaz \(\displaystyle{ B\in \mathcal{R}}\) , to również \(\displaystyle{ A\in \mathcal{R}}\).

Ponieważ koło domknięte \(\displaystyle{ X}\) jest zbiorem niepustym, a \(\displaystyle{ \mathcal{R}}\) jest rozkładem koła \(\displaystyle{ X}\), a \(\displaystyle{ A \in \mathcal{R}}\) jest zbiorem tego rozkładu , więc na mocy przytoczonego faktu rodzina \(\displaystyle{ \mathcal{R} \setminus \left\{ A\right\}}\) jest rozkładem zbioru \(\displaystyle{ X \setminus A}\). Ale:

\(\displaystyle{ X \setminus A= \left\{ \left( x,y\right) \in \RR^2: \ \left( x-x_0 \right)^2+ \left( y-y_0 \right) ^{2} \le r^2 \right\} \setminus \left\{ \left( x,y\right) \in \RR^2: \ \left( x-x_0 \right)^2+ \left( y-y_0 \right) ^{2} = r^2\right\}= \\ = \left\{ \left( x,y\right) \in \RR^2: \ \left( x-x_0 \right)^2+ \left( y-y_0 \right) ^{2} < r^2\right\}=Y,}\)

czyli rodzina \(\displaystyle{ \mathcal{R} \setminus \left\{ A \right\}}\) jest rozkładem zbioru \(\displaystyle{ Y.}\)

I ponieważ rodzina \(\displaystyle{ \mathcal{R}}\) jest rodziną okręgów o środku w punkcie \(\displaystyle{ \left( x_0,y_0\right)}\) , więc również rodzina \(\displaystyle{ \mathcal{R} \setminus \left\{ A\right\} }\) jest rodziną okręgów o środku w punkcie \(\displaystyle{ \left( x_0,y_0\right). \square}\) :lol:

Ciekawi mnie jeszcze, czy kulę trójwymiarową można rozłożyć na sfery.


Wykażemy jeszcze, zgodnie z zapowiedzią, że:

Jeśli mamy niepusty przedział \(\displaystyle{ A\subset \RR}\), oraz funkcję \(\displaystyle{ g:A \rightarrow \RR}\), funkcję słabo rosnącą, wtedy zbiór,

\(\displaystyle{ -A=\left\{ -x\Bigl| \ x\in A\right\} }\),

również jest przedziałem , gdyż w zbiorze liczb trzeczywistych , jak mamy przedział, to zbiór wszystkich wartości przeciwnych, do elementów tego przedziału, również jest przedziałem- jest to prosty fakt,

i wykażemy, że funkcja \(\displaystyle{ g':-A \rightarrow \RR}\), dana jako:

\(\displaystyle{ g'(x)= g\left( -x\right)}\) ,

jest słabo malejąca ( jest to funkcja powstała po odbiciu względem osi \(\displaystyle{ y}\)).

DOWÓD TEGO CIEKAWEGO FAKTU:

Sprawdźmy najpierw czy funkcja \(\displaystyle{ g'}\) jest dobrze określona, gdyż funkcja \(\displaystyle{ g}\) jest określona tylko na przedziale.

Jeśli \(\displaystyle{ x\in \left( -A\right)}\) , wtedy \(\displaystyle{ x=-a }\), gdzie \(\displaystyle{ a\in A}\), wtedy \(\displaystyle{ -x= -\left( -a\right) =a}\), i ponieważ \(\displaystyle{ g:A \rightarrow \RR}\), a \(\displaystyle{ -x=a\in A}\), to: \(\displaystyle{ g'(x)= g\left( -x\right) = g(a)\in\RR}\), i funkcja: \(\displaystyle{ g':-A \rightarrow \RR,}\)

jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ g'}\) jest słabo malejąca.
W tym celu weźmy elementy \(\displaystyle{ x,y\in \left( -A \right)}\), takie, że \(\displaystyle{ x<y}\), i pokazmy, że \(\displaystyle{ g'(y) \le g'(x).}\)

Ponieważ \(\displaystyle{ x,y\in \left( -A\right)}\) , to \(\displaystyle{ x=-a}\), gdzie \(\displaystyle{ a\in A}\), i \(\displaystyle{ y=-b}\), gdzie \(\displaystyle{ b\in A}\). Ponieważ \(\displaystyle{ x<y}\), to \(\displaystyle{ -x>-y}\), a zatem: \(\displaystyle{ -x=-\left( -a\right) =a>-y= -\left( -b\right) =b,}\) czyli \(\displaystyle{ a>b}\). Ponieważ \(\displaystyle{ a,b\in A}\), a funkcja \(\displaystyle{ g:A \rightarrow \RR}\) jest słabo rosnąca, więc \(\displaystyle{ g(a) \ge g(b)}\). A zatem:

\(\displaystyle{ g'(y)= g(-y)= g\left( -\left( -b\right) \right) = g(b) \le g(a)= g\left( -\left( -a\right) \right) =g\left( -x\right) = g'(x)}\),

czyli \(\displaystyle{ g'(y) \le g'(x)}\) , i funkcja \(\displaystyle{ g'}\) jest słabo malejąca\(\displaystyle{ .\square}\) :D
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Rozkłady zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 10 sie 2022, o 20:10 Tzn. wczoraj, na dobranoc, udowodniłem sobie, że koło domknięte na płaszczyźnię można rozłożyć na okregi, a przed chwilą, udowodniłem, że koło otwarte można rozłożyć na okręgi.
No cóż, napisałeś się strasznie, ale skoro wiemy, że przedział (otwarty bądź domknięty) można rozłożyć na punkty, to tak samo koło można rozłożyć na okręgi (a kulę na sfery itd.) - to dość oczywiste obserwacje.

JK
3a174ad9764fefcb
Użytkownik
Użytkownik
Posty: 287
Rejestracja: 18 lip 2022, o 17:46
Płeć: Mężczyzna
wiek: 40
Podziękował: 3 razy
Pomógł: 41 razy

Re: Rozkłady zbiorów

Post autor: 3a174ad9764fefcb »

Jakub Gurak pisze: 10 sie 2022, o 20:10 wczoraj, na dobranoc, udowodniłem sobie, że koło domknięte na płaszczyźnię można rozłożyć na okregi
Jeśli w definicji okręgu nie wymagasz, żeby promień był dodatni, to można udowodnić twierdzenie ogólniejsze, mianowicie każdy podzbiór \(\RR^2\) można rozłożyć na okręgi. Weźmy dowolny \(X\subseteq \RR^2\). Taki zbiór jest sumą swoich singletonów, tzn. rozkładem zbioru jest rodzina \(\{\{x\}:x\in X\}\).

Jeśli natomiast okrąg musi mieć dodatni promień, to Twój dowód nie działa i możesz mieć problem ze znalezieniem lepszego.

Dodano po 25 minutach 38 sekundach:
Gdybyś natomiast chciał wykazać, że konstrukcja z okręgami o dodatnich promieniach jest niemożliwa, możesz skorzystać z następującego faktu: zstępujący ciąg niepustych zbiorów domkniętych i ograniczonych w \(\RR\) ma niepuste przecięcie. Gdyby taka rodzina okręgów istniała, mógłbyś skonstruować taki ciąg kół domkniętych wyznaczonych przez te okręgi, że każde kolejne koło jest zawarte w poprzednim i ma promień co najmniej dwa razy mniejszy od poprzedniego.
Ukryta treść:    
Dodano po 1 godzinie 56 minutach 39 sekundach:
3a174ad9764fefcb pisze: 11 sie 2022, o 11:31 zstępujący ciąg niepustych zbiorów domkniętych i ograniczonych w \(\RR\) ma niepuste przecięcie.
Oczywiście tu chodziło mi o zbiory w \(\RR^2\), nie w \(\RR\), żeby to jakoś pasowało do zadania.
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: Rozkłady zbiorów

Post autor: Jakub Gurak »

W ostatnią sobotę udowodniłem, że istnieje dokładnie continuum rozkładów zbioru liczb całkowitych \(\displaystyle{ \ZZ}\) na przedziały :o (przedziały w \(\displaystyle{ \left( \ZZ,\le\right) }\) ) . A potem, w ten sam wieczór, udowodniłem, a następnego dnia jeszcze to sprawdziłem , że również istnieje dokładnie continuum rozkładów zbioru liczb naturalnych na przedziały. Przedstawię teraz dowody tych ciekawych faktów.


Przypomnijmy:

Jeśli \(\displaystyle{ X}\) jest zbiorem równolicznym z \(\displaystyle{ \NN}\), to istnieje dokładnie continuum rozkładów tego przeliczalnego zbioru \(\displaystyle{ X}\)- udowodniłem to: TUTAJ, NA PIERWSZEJ STRONIE.

Przejdźmy do naszego problemu:

Niech:

\(\displaystyle{ \mathbb{B}=\left\{ \mathcal{R}: \ \ \mathcal{R} \hbox{ jest rozkładem zbioru } \ZZ \hbox{ na przedziały w } \left( \ZZ, \le \right) \right\} .}\)

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

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest mocy continuum.

DOWÓD TEGO FAKTU:

Definiujemy injekcję:

\(\displaystyle{ \alpha : \left\{ 0,1\right\} ^{\ZZ} \rightarrow \mathbb{B} }\), w następujący sposób:


(Będziemy musieli rozwazyć kilka przypadków, ale idea sposobu definicji tej funkcji jest zawsze taka sama :
Jeśli \(\displaystyle{ f:\ZZ \rightarrow \left\{ 0,1\right\}}\), i dla \(\displaystyle{ x\in\ZZ}\) jeśli mamy \(\displaystyle{ f(x)=1}\), to to \(\displaystyle{ 1}\) oznacza, że jest to początek nowego przedziału w tworzonym przypisanym rozkładzie, a jeśli \(\displaystyle{ f(x)=0}\), to to \(\displaystyle{ 0}\) oznacza, że dalej znajdujemy się w tym samym przedziale, co na poprzedniej liczbie całkowitej.

Formalnie:

Rozważmy przeciwobraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\}. }\)

Jeśli ten przeciwobraz jest pusty, to funkcji \(\displaystyle{ f}\) przypisujemy rozkład \(\displaystyle{ \mathcal{R}= \left\{ \ZZ \right\}}\)- jest to rozkład zbioru \(\displaystyle{ \ZZ}\), a cały zbiór \(\displaystyle{ \ZZ}\) jest przedziałem początkowym w \(\displaystyle{ \left( \ZZ, \le \right) }\), a więc jest przedziałem. A zatem \(\displaystyle{ \mathcal{R}\in\mathbb{B}.}\)

Jeśli ten przeciwobraz jest niepusty, to oznaczmy go jako \(\displaystyle{ A}\). Wtedy\(\displaystyle{ A\subset \ZZ\subset \RR}\), a więc zbiór \(\displaystyle{ A}\) jest liniowo uporządkowany przez naturalny porządek na nim. Ponieważ jest podobny do samego siebie- \(\displaystyle{ A \approx A\subset \ZZ,}\) czyli jest podobny do podzbioru zbioru liczb całkowitych, to na mocy twierdzenia które udowodniłem TUTAJ, W DRUGIM POŚCIE , możliwe są tylko cztery przypadki:

\(\displaystyle{ 1 ^{\circ} }\) zbiór \(\displaystyle{ A}\) jest skończony, albo
\(\displaystyle{ 2 ^{\circ} }\) \(\displaystyle{ A \approx \NN}\), albo
\(\displaystyle{ 3^{ \circ} }\) \(\displaystyle{ A \approx \ZZ_- \cup \left\{ 0 \right\} }\)- czyli zbiór \(\displaystyle{ A}\) jest podobny do zbioru liczb całkowitych ujemnych wraz z zerem, i mamy jeszcze jedną możliwość: albo
\(\displaystyle{ 4^{ \circ}}\) \(\displaystyle{ A \approx \ZZ.}\)

Jeśli w \(\displaystyle{ A}\) nie ma elementu najmniejszego ani największego, to ponieważ \(\displaystyle{ A \neq \left\{ \right\}}\) , to zbiór \(\displaystyle{ A}\) musi być nieskończony (w skończonym niepustym zbiorze jest element najmniejszy ). I mamy \(\displaystyle{ A\not \approx \NN}\) (w \(\displaystyle{ \left( \NN, \le \right) }\) liczba \(\displaystyle{ 0}\) jest najmniejsza ) , i \(\displaystyle{ A\not \approx \ZZ_- \cup \left\{ 0\right\}}\) (w \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\) liczba \(\displaystyle{ 0}\) jest największa), wobec czego pozostaje jedynie możliwość: \(\displaystyle{ A \approx \ZZ.}\)

Wtedy w zbiorze \(\displaystyle{ A}\), podobnie jak w zbiorze \(\displaystyle{ \ZZ}\), każdy element ma następnik i każdy element ma poprzednik.

Jeśli \(\displaystyle{ x\in A}\), to \(\displaystyle{ x}\) ma następnik \(\displaystyle{ x ^{+}}\), pozatym taki następnik jest jedyny( bo jest to najmniejszy element silnie większy od \(\displaystyle{ x}\)), oznaczmy więc go jako \(\displaystyle{ x ^{+} }\). Rozwazmy rozkład \(\displaystyle{ \mathcal{R}}\), dany jako:

\(\displaystyle{ \mathcal{R}=\left\{ \left[ x, x ^{+} \right)\Bigl| \ \ x\in A \right\}.}\)

gdzie:

\(\displaystyle{ \left[ x, x ^{+} \right)= \left\{ y\in \ZZ: \ \ x \le y < x ^{+} \right\} .}\)

Zauważmy, że jest to rodzina podzbiorów \(\displaystyle{ \ZZ}\). Wykażemy, że \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \ZZ}\).

Niewątpliwie \(\displaystyle{ \bigcup\mathcal{R}\subset \ZZ}\)- jest to suma podzbiorów zbioru \(\displaystyle{ \ZZ}\).
Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ y\in\ZZ}\). Niech \(\displaystyle{ x\in\ZZ}\) będzie największą liczbą całkowitą, taką, że \(\displaystyle{ x\in A}\) i \(\displaystyle{ x \le y.}\) Taka liczba istnieje, gdyż:
DOWÓD TEGO FAKTU::    
Wtedy element \(\displaystyle{ x\in A}\) ma następnik \(\displaystyle{ x ^{+}\in A}\), a wtedy \(\displaystyle{ x<x^{+}.}\) Ponieważ \(\displaystyle{ x}\) jest największym elementem \(\displaystyle{ A}\) nie większym od \(\displaystyle{ y}\), a \(\displaystyle{ x ^{+}\in A}\) i \(\displaystyle{ x ^{+} >x}\), to \(\displaystyle{ x ^{+}\not \le y}\), a więc \(\displaystyle{ x ^{+}>y.}\) Wtedy \(\displaystyle{ x \le y<x ^{+} }\), i \(\displaystyle{ y\in \ZZ,}\) a więc \(\displaystyle{ y\in \left[ x, x ^{+} \right)}\), gdzie \(\displaystyle{ x\in A}\), a zatem \(\displaystyle{ y\in \bigcup_{z\in A} \left[ z,z ^{+} \right) = \bigcup\mathcal{R},}\) i \(\displaystyle{ \bigcup\mathcal{R} =\ZZ}\).

Musimy wykazać, że \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów rozłącznych. W tym celu weźmy dwa różne zbiory tej rodziny, i pokażmy, że są one rozłączne.

Tzn. weźmy zbiory postaci \(\displaystyle{ B_1=\left[ x_1,x_1^+\right ),}\) gdzie \(\displaystyle{ x_1\in A}\); oraz weźmy zbiór postaci \(\displaystyle{ B_2=\left[ x_2,x_2 ^{+} \right) }\), gdzie \(\displaystyle{ x_2\in A}\) ,weźmy takie dwa różne zbiory. Ponieważ te zbiory są różne, więc \(\displaystyle{ x_1 \neq x_2}\). A zatem\(\displaystyle{ x_1<x_2}\) lub \(\displaystyle{ x_2<x_1.}\)

Jeśli \(\displaystyle{ x_1<x_2}\), to dla następnika \(\displaystyle{ x_1 ^{+}}\), ponieważ \(\displaystyle{ x_2>x_1}\), więc z definicji następnika wnioskujemy, że \(\displaystyle{ x_2 \ge x_1 ^{+} }\), a stąd, oraz z postaci tych zbiorów, już łatwo wynika, że te dwa zbiory są rozłączne.

Jeśli \(\displaystyle{ x_2<x_1}\), to analogicznie uzasadniamy, że zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ B_2}\) są rozłączne.

Wobec czego rodzina \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów rozłącznych.

I oczywiście \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów niepustych.

A zatem \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \ZZ}\). I

\(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów w \(\displaystyle{ (\ZZ, \le )}\), a zatem \(\displaystyle{ \mathcal{R}\in \mathbb{B}.}\)


Dalej zauważmy, że jeśli \(\displaystyle{ x\in A}\) i element \(\displaystyle{ x}\) nie jest największy w zbiorze \(\displaystyle{ A}\), to element \(\displaystyle{ x}\) ma następnik \(\displaystyle{ x^{+}}\) w zbiorze \(\displaystyle{ A.}\)

Wtedy rodzina:

Lemat Rodzina:

\(\displaystyle{ \mathcal{R}^ {'}= \left\{ \left[ x,x ^{+}\right)\Bigl| \ \ x\in A\hbox{ i } x \hbox{ nie jest największy w } A\right\}, }\)

jest rozkładem zbioru \(\displaystyle{ \bigcup\mathcal{R}'}\) na przedziały.

Można łatwo się o tym przekonać; i ten Lemat przyda nam się nie raz.

Rozważmy kolejne przypadki:

Jeśli w \(\displaystyle{ A}\) jest element najmniejszy \(\displaystyle{ a\in A,}\) i w \(\displaystyle{ A}\) nie ma elementu największego.
Wtedy pozostaje jedynie możliwość, że zbiór \(\displaystyle{ A}\) jest podobny do \(\displaystyle{ \NN}\). Łatwo, ponieważ w \(\displaystyle{ \left( \NN, \le\right) }\) kazda liczba naturalna ma następnik, to korzystając z definicji podobieństwa, łatwo możemy pokazać, że w dowolnym zbiorze liniowo uporządkowanym podobnym do \(\displaystyle{ (\NN, \le )}\)- tu również: każdy element ma następnik- łatwo, na podstawie definicji podobieństwa, możemy to udowodnić. A zatem również u nas, czyli w \(\displaystyle{ \left( A, \le\right), }\) tu również: każdy element \(\displaystyle{ A}\) ma następnik. Niech:

\(\displaystyle{ \mathcal{R}= \left\{ \left[ x,x^+\right)\Bigl| \ \ x\in A \right\} \cup \left\{ \left( \leftarrow ,a\right) \right\} }\), gdzie:

\(\displaystyle{ \left( \leftarrow ,a\right)= \left\{ b\in\ZZ: \ \ b<a\right\} .}\)

Wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \ZZ}\) na przedziały.

Wykażemy, że: \(\displaystyle{ \bigcup\mathcal{R}'= \left[ a, \rightarrow \right)}\).
DOWÓD TEGO FAKTU::    
A zatem, w myśl przytoczonego Lematu, rodzona \(\displaystyle{ \mathcal{R} ^{'}}\) jest rozkładem zbioru \(\displaystyle{ \left[ a, \rightarrow \right)}\) na przedziały.

Niech \(\displaystyle{ B=\left( \leftarrow ,a\right) }\), wtedy rodzina \(\displaystyle{ \left\{ B \right\}}\) jest rozkładem zbioru \(\displaystyle{ B \neq \left\{ \right\}}\). I zbiory \(\displaystyle{ B= \left( \leftarrow ,a\right) }\) oraz \(\displaystyle{ \left[ a, \rightarrow \right)}\) są rozłączne, a zatem suma tych dwóch rozkładów na zbiorach rozłącznych , na mocy pewnego prostego faktu, jest rozkładem w sumie zbiorów na których są określone te dwa rozkłady, czyli \(\displaystyle{ \mathcal{R}:=\mathcal{R}' \cup \left\{ B\right\} = \mathcal{R}' \cup \left\{ \left( \leftarrow ,a\right) \right\}}\) jest rozkladem zbioru \(\displaystyle{ \left[ a, \rightarrow \right) \cup \left( \leftarrow ,a\right) =\ZZ}\) na przedziały ( zbiór \(\displaystyle{ B= \left( \leftarrow, a\right)}\) jest przedziałem początkowym w \(\displaystyle{ \left( \ZZ, \le \right) }\), a więc jest przedziałem ). A zatem \(\displaystyle{ \mathcal{R}\in \mathbb{B}.}\)

Jeśli w zbiorze \(\displaystyle{ A}\) jest element najmniejszy \(\displaystyle{ a\in A}\) i w \(\displaystyle{ A}\) jest element największy \(\displaystyle{ b\in A}\), wtedy niech :

\(\displaystyle{ \mathcal{R}'= \left\{ \left[ x,x ^{+} \right)\Bigl| \ \ x\in A \setminus \left\{ b\right\} \right\}}\), czyli rozważamy przedziały po elementach \(\displaystyle{ x\in A}\): \(\displaystyle{ x \neq b.}\)

Jest to tożsama definicja z definicją rodziny \(\displaystyle{ \mathcal{R}'}\) podaną w naszym lemacie, gdyż element największy jest tylko jeden.

Wykażemy, że: \(\displaystyle{ \bigcup\mathcal{R}' =\left[ a,b\right).}\)
DOWÓD TEGO FAKTU::    
A zatem, w myśl podanego lematu: rodzina \(\displaystyle{ \mathcal{R}' }\) jest rozkładem zbioru \(\displaystyle{ \bigcup\mathcal{R}'=\left[ a,b\right) }\) na przedziały.

Niech \(\displaystyle{ B_1= \left( \leftarrow ,a\right). }\) Wtedy rodzina \(\displaystyle{ \left\{ B_1\right\} }\) jest rozkładem zbioru \(\displaystyle{ B_1 \neq \left\{ \right\}}\).

Niech \(\displaystyle{ B_2= \left[ b, \rightarrow \right).}\) Wtedy rodzina \(\displaystyle{ \left\{ B_2\right\} }\) jest rozkładem zbioru \(\displaystyle{ B_2.}\)

Zauważmy, że zbiory \(\displaystyle{ \left[ a,b\right)}\), \(\displaystyle{ \left[ b, \rightarrow \right]}\) i \(\displaystyle{ \left( \leftarrow ,a\right)}\) są rozłączne. A zatem \(\displaystyle{ \mathcal{R}:= \mathcal{R}' \cup \left\{ B_1\right\} \cup \left\{ B_2\right\}=\mathcal{R}' \cup \left\{ \left( \leftarrow ,a\right) ; \left[ b, \rightarrow \right) \right\}}\) jest rozkładem zbioru \(\displaystyle{ \left[ a,b\right) \cup \left( \leftarrow ,a\right) \cup \left[ b, \rightarrow \right)=\ZZ}\).

I ponieważ \(\displaystyle{ \mathcal{R}' }\) jest rodziną przedziałów , więc również rodzina \(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów ( zbiór \(\displaystyle{ B_1}\) jest przedziałem początkowym w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( \ZZ, \le \right) }\), gdyż zbiory w takiej postaci są zawsze przedziałami początkowymi, a więc zbiór \(\displaystyle{ B_1}\) jest przedziałem; a zbiór \(\displaystyle{ B_2 }\) jest resztą w \(\displaystyle{ \left( \ZZ, \le \right) }\) , bo zbiory w takiej postaci są zawsze resztą, a więc zbiór \(\displaystyle{ B_2}\) jest przedziałem ) . Wobec czego \(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów, i \(\displaystyle{ \mathcal{R}\in \mathbb{B}.}\)

Pozostał do rozważenia przypadek, gdy w zbiorze \(\displaystyle{ A}\) nie ma elementu najmniejszego, a jest w nim element największy \(\displaystyle{ b\in A.}\)

Wtedy \(\displaystyle{ \mathcal{R}'=\left\{ \left[ x,x ^{+} \right)\Bigl| \ \ x\in A \hbox{ i } x \neq b \right\} ,}\)

ten zapis może być formalnie nie za bardzo, chodzi o to, że zmienna \(\displaystyle{ x}\) przebiega elemnenty zbioru \(\displaystyle{ A}\) różne od elementu \(\displaystyle{ b}\).

Wykazemy, że: \(\displaystyle{ \bigcup\mathcal{R}'= \left( \leftarrow ,b\right) }\).
DOWÓD TEGO FAKTU::    
A zatem, na mocy naszego lematu, rodzina \(\displaystyle{ \mathcal{R}' }\) jest rozkładem zbioru \(\displaystyle{ \left( \leftarrow ,b\right)}\) na przedziały.

Wtedy \(\displaystyle{ B:= \left[ b, \rightarrow \right) \neq \left\{ \right\}}\) , a zatem rodzina \(\displaystyle{ \mathcal{R}_0:= \left\{ B\right\}}\) jest rozkldem zbioru \(\displaystyle{ B;}\) i zbiory \(\displaystyle{ \left[ b, \rightarrow \right)}\) oraz \(\displaystyle{ \left( \leftarrow ,b \right)}\) są rozłączne, a zatem \(\displaystyle{ \mathcal{R}:=\mathcal{R}' \cup \mathcal{R}_0=\mathcal{R}' \cup \left\{ \left[ b, \rightarrow \right) \right\}}\) jest rozkładem zbioru \(\displaystyle{ \left( \leftarrow ,b\right) \cup \left[ b, \rightarrow \right] =\ZZ}\).

Ponieważ \(\displaystyle{ \mathcal{R}'}\) jest rodziną przedziałów, a zbiór \(\displaystyle{ B}\) jest resztą w \(\displaystyle{ \left( \ZZ, \le \right) }\), a więc jest przedziałem, a więc również rodzina \(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów, a zatem \(\displaystyle{ \mathcal{R} \in \mathbb{B}}\).

A zatem funkcja \(\displaystyle{ \alpha}\) , działająca w poniższy sposób:

\(\displaystyle{ f\in \left\{ 0,1\right\} ^{\ZZ} \stackrel{ \alpha }{ \rightarrow} \mathcal{R} \in\mathbb{B}}\),

jest dobrze określona.

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

W tym celu weźmy dwie różne funkcje \(\displaystyle{ f_1,f_2:\ZZ \rightarrow \left\{ 0,1\right\}}\) . Wtedy \(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} \neq \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} .}\) Gdyby bowiem te przeciwobrazy byłyby sobie równe, to wtedy również:

\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left( \left\{ 0\right\} = \left\{ 1\right\} ' \right) = \ZZ \setminus \stackrel { \rightarrow }{f_1 ^{-1} } \left\{ 1\right\}= \ZZ \setminus \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} = \stackrel { \rightarrow } {f_2 ^{-1} } \left( \left\{ 0\right\} = \left\{ 1\right\} ^{'} \right).}\)

Czyli:

\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 0\right\} =\stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 0\right\} ,}\) oraz
\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} =\stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} ,}\)

a ponieważ \(\displaystyle{ f_1, f_2: \ZZ \rightarrow \left\{ 0,1\right\}}\) , to stąd łatwo jest pokazać, że \(\displaystyle{ f_1=f_2}\)- co daje sprzeczność z naszym założeniem.

Wobec czego:

\(\displaystyle{ A_1:= \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} \neq \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\}=:A_2}\).

Ponieważ \(\displaystyle{ A_1 \neq A_2}\), to \(\displaystyle{ A_1\not\subset A_2}\) lub \(\displaystyle{ A_2\not\subset A_1.}\)

Jeśli \(\displaystyle{ A_1\not\subset A_2}\), wtedy, z definicji inkluzji i na podstawie prawa zaprzeczania ograniczonemu kwantyfikatorowi ogólnemu, więc otrzymujemy pewien element \(\displaystyle{ x\in A_1}\), taki, że \(\displaystyle{ x\not\in A_2}\). Wtedy\(\displaystyle{ A_1\subset \ZZ}\), a więc \(\displaystyle{ x\in\ZZ}\). Ponieważ \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem zbioru \(\displaystyle{ \ZZ}\), to niech \(\displaystyle{ B_2\in \mathcal{R}_2}\) będizie zbiorem tego rozkładu takim, że \(\displaystyle{ x\in B_2}\)( taki zbiór jest dokładnie jeden, gdyż \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem zbioru \(\displaystyle{ \ZZ}\) ). Podobnie, niech \(\displaystyle{ B_1\in\mathcal{R}_1}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}_1}\) zawierającym element \(\displaystyle{ x}\). Wtedy \(\displaystyle{ B_2\not\in\mathcal{R}_1}\).
Gdyby bowiem byłoby \(\displaystyle{ B_2\in\mathcal{R}_1}\), to wtedy \(\displaystyle{ x\in B_2 \cap B_1}\), a \(\displaystyle{ B_1\in\mathcal{R}_1}\), a\(\displaystyle{ \mathcal{R}_1,}\) jako rozkład, jest rodziną zbiorów rozłącznych, a zatem z warunku rozłączności otrzymujemy, że \(\displaystyle{ B_1=B_2}\). Ponieważ \(\displaystyle{ x\in A_1}\), to łatwo sprawdzić, że element \(\displaystyle{ x}\) jest najmniejszy w \(\displaystyle{ B_1}\), a zatem również element \(\displaystyle{ x}\) jest najmniejszy w \(\displaystyle{ B_2.}\) Wtedy \(\displaystyle{ B_2\in\mathcal{R}_2}\), a zatem zbiór \(\displaystyle{ B_2}\) jest postaci \(\displaystyle{ \left[ y, y ^{+} \right),}\) gdzie \(\displaystyle{ y \in A_2;}\) lub zbiór \(\displaystyle{ B_2}\) jest postaci \(\displaystyle{ \left[ y, \rightarrow \right)}\), gdzie \(\displaystyle{ y\in A_2}\). W obydwu przypadkach element \(\displaystyle{ y}\) jest elementem najmniejszym zbioru \(\displaystyle{ B_2,}\) i, w obydwu przypadkach: \(\displaystyle{ y\in A_2}\). Ponieważ \(\displaystyle{ x}\) jest elementem najmniejszym zbioru \(\displaystyle{ B_2}\), a w danym zbiorze istnieje tylko jeden element najmniejszy, a zatem \(\displaystyle{ x=y\in A_2}\), a więc \(\displaystyle{ x\in A_2}\)- sprzeczność.
Wobec czego \(\displaystyle{ B_2\not\in\mathcal{R}_1}\), a \(\displaystyle{ B_2\in\mathcal{R}_2}\), a zatem \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2.}\)

Jeśli \(\displaystyle{ A_2\not\subset A_1}\), to w sposób analogiczny udowadniamy, że \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2.}\)

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest funkcją różnowartościową.

A zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \left\{ 0,1\right\} ^{\ZZ} \right| = \left| \left\{ 0,1\right\} ^{\NN} \right| =\left| \RR\right| }\). Czyli \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \RR\right|.}\)

Nierówność mocy zbiorów w drugą stronę, łatwo uzyskać, gdyż wszystkich rozkładów zbioru przeliczalnego jest continuum.

Tzn. niech:

\(\displaystyle{ \mathbb{A}= \left\{ \mathcal{R}: \ \ \mathcal{R} \hbox{ jest rozkładem zbioru } \ZZ\right\}}\).

Ponieważ zbiór liczb całkowitych jest równoliczny ze zbiorem liczb naturalnych, a wszystkich rozkładów zbioru przeliczalnego jest continuum, wobec czego rodzina \(\displaystyle{ \mathbb{A} }\) jest również mocy continuum. Łatwo jest zauważyć, że \(\displaystyle{ \mathbb{B} \subset \mathbb{A}}\), a zatem \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \mathbb{A}\right| = \left| \RR\right| }\).

Mamy \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \RR\right|}\) , a zatem, na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \mathbb{B}\sim \RR}\). Czyli istnieje dokładnie continuum rozkładów zbioru liczb całkowitych na przedziały\(\displaystyle{ .\square}\) :D 8-)


Rozważmy podonbne zadanie na zbiorze liczb naturalnych. Tzn rozważmy rodzinę rozkładów \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}= \left\{ \mathcal{R}: \ \ \mathcal{R} \hbox { jest rozkładem zbioru } \NN \hbox{ na przedziały w } \left( \NN, \le \right) \right\}.}\)

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

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest mocy continuum.

DOWÓD TEGO FAKTU:

Definiujemy funkcję \(\displaystyle{ \alpha : \left\{ 0,1\right\} ^{\NN} \rightarrow \mathbb{B}}\) w poniższy sposób:

(Podobnie jak dla konstrukcji na zbiorze liczb całkowitych, ale odrobinę odwrotnie wygląda ta konstrukcja, już tłumaczę, jeśli \(\displaystyle{ f:\NN \rightarrow \left\{ 0,1\right\}}\), i jeśli dla \(\displaystyle{ n\in\NN}\), mamy \(\displaystyle{ f(n)=1}\), to to \(\displaystyle{ 1}\) oznacza koniec rozpatrywanego przedziału, a jeśsli \(\displaystyle{ f(n)=0}\), to to \(\displaystyle{ 0}\) oznacza , że na następnej liczbie naturalnej będziemy dalej w tym samym przedzizale co o krok wcześniej).

Formalnie:

Rozwazmy przeciwobraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ 1\right\} =:A\subset \NN.}\)

Jeśli ten przeciwobraz jest pusty, to definiujemy \(\displaystyle{ \mathcal{R}= \left\{ \NN\right\}}\) - jest to rozkład zbioru \(\displaystyle{ \NN}\), i cały zbiór \(\displaystyle{ \NN}\) jest przedziałem początkowym w \(\displaystyle{ \left( \NN, \le \right)}\), a więc jest przedziałem, a zatem \(\displaystyle{ \mathcal{R}\in \mathbb{B}.}\)

Jesli ten przeciwobraz jest niepusty, i jeśli jest zbiorem skończonym , zatem ponumerujmy go ( tzn. przypuśćmy, że ma \(\displaystyle{ n}\)-elementów) i uporządkujmy go , tzn. niech:

\(\displaystyle{ A=\left\{ x_1,x_2,\ldots, x_n \right\}}\) , gdzie\(\displaystyle{ x_1<x_2<\ldots <x_n.}\)

Wtedy rozważmy rozklad \(\displaystyle{ \mathcal{R},}\) dany jako:

\(\displaystyle{ \mathcal{R}= \left\{ \left[ 0,x_1\right]; \left( x_1,x_2 \right]; \left( x_2,x_3\right];\ldots ; \left( x _{n-1}, x_n \right] ; \left( x_n, \rightarrow \right) \right\} .}\)

Jak łatwo sprawdzić, jest to rozklad zbioru \(\displaystyle{ \NN}\), i jest to rodzina przedziałów (zbiór \(\displaystyle{ \left( x_n, \rightarrow \right) }\) jest resztą w \(\displaystyle{ \left( \NN, \le \right) }\), bo zbiory, w takiej postaci, są zawsze resztą, a więc ten zbiór jest przedziałem). Wobec czego \(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów i \(\displaystyle{ \mathcal{R}\in \mathbb{B}.}\)

Jeśli zbiór \(\displaystyle{ A}\) jest nieskończony, a \(\displaystyle{ A\subset \NN}\) i zbiór \(\displaystyle{ A}\) jest podobny do samego siebie, czyli do podzbioru zbioru liczb naturalnych, to w podanym (ostatnim ) linku jest udowodnione twierdzenie z którego wynika, że zbiór \(\displaystyle{ A}\) musi być podobny do \(\displaystyle{ \NN}\). Wtedy w zbiorze \(\displaystyle{ A}\), podobnie jak w \(\displaystyle{ \NN}\), jest element najmniejszy \(\displaystyle{ a_0\in A}\). Wtedy , w zbiorze \(\displaystyle{ A}\), podobnie jak w \(\displaystyle{ \left( \NN, \le\right) }\) , każdy element ma następnik. Jeśli więc \(\displaystyle{ x\in A}\), to element \(\displaystyle{ x}\) ma następnik \(\displaystyle{ x^{+}}\). Niech:

\(\displaystyle{ \mathcal{R}=\left\{ \left[ 0,a_0\right] \right\} \cup \left\{ \left( x, x ^{+} \right]\Bigl| \ \ x\in A \right\} .}\)

Wykażemy, że rodzina \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN}\) na przedziały.

Niewątpliwie \(\displaystyle{ \bigcup\mathcal{R}\subset \NN}\) (jest to suma podzbiorów \(\displaystyle{ \NN}\)).

Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ n\in\NN.}\)

Jeśli \(\displaystyle{ n \le a_0}\), to \(\displaystyle{ n\in \left[ 0, a_0\right]}\) , a więc \(\displaystyle{ n \in \bigcup\mathcal{R}.}\)
A jeśli \(\displaystyle{ n> a_0}\), to niech \(\displaystyle{ m\in\NN}\) będzie największą liczbą naturalną taką, że \(\displaystyle{ m\in A}\) i \(\displaystyle{ m<n}\). Liczba taka istnieje, gdyż:
UZASADNIENIE TEGO FAKTU::    
Wtedy \(\displaystyle{ m^+>m}\), a \(\displaystyle{ m}\) jest największym elementem \(\displaystyle{ A}\) silnie mniejszym od \(\displaystyle{ n}\), a \(\displaystyle{ m^+\in A}\), więc \(\displaystyle{ m ^{+} \ge n}\), wtedy \(\displaystyle{ m<n \le m ^{+}}\) , a zatem \(\displaystyle{ n\in \left( m,m ^{+} \right]}\), gdzie \(\displaystyle{ m\in A}\), a zatem \(\displaystyle{ n\in \bigcup\mathcal{R},}\) i \(\displaystyle{ \bigcup\mathcal{R}=\NN. }\)

Niewątpliwie \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów rozłącznych, i \(\displaystyle{ \mathcal{R}}\) jest rodziną zbiorów niepustych.

A zatem \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \NN.}\)

I \(\displaystyle{ \mathcal{R}}\) jest rodziną przedziałów, a zatem \(\displaystyle{ \mathcal{R}\in\mathbb{B}.}\)

A zatem funkcja \(\displaystyle{ \alpha}\), działająca w poniższy sposób:

\(\displaystyle{ f\in \left\{ 0,1\right\} ^{\NN} \rightarrow \mathcal{R} _f\in \mathbb{B},}\)

jest dobrze określona.

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

W tym celu weżmy dwie różne funkcje \(\displaystyle{ f_1,f_2:\NN \rightarrow \left\{ 0,1\right\}}\) , i pokażmy , że przypisane im rozkłady, oznaczone odpowiednio jako \(\displaystyle{ \mathcal{R}_1}\) i \(\displaystyle{ \mathcal{R}_2}\) są różne.

Ponieważ \(\displaystyle{ f_1 \neq f_2}\), to \(\displaystyle{ A_1:=\stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} \neq \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} =:A_2.}\) Gdyby bowiem te przeciwobrazy byłyby sobie równe, to wtedy również:

\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left( \left\{ 0\right\} \right) = \stackrel { \rightarrow } {f_1 ^{-1} } \left( \left\{ 1\right\} ' \right)= \NN \setminus \stackrel { \rightarrow }{f_1 ^{-1} } \left\{ 1\right\}= \NN \setminus \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} = \stackrel { \rightarrow } {f_2 ^{-1} } \left( \left\{ 0\right\} \right).}\)

Czyli:

\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 0\right\} =\stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 0\right\} ,}\) oraz
\(\displaystyle{ \stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} =\stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} ,}\)

a ponieważ \(\displaystyle{ f_1, f_2: \NN \rightarrow \left\{ 0,1\right\}}\) , to stąd łatwo jest pokazać, że \(\displaystyle{ f_1=f_2}\)- co daje sprzeczność z naszym założeniem.

Wobec czego:

\(\displaystyle{ A_1:=\stackrel { \rightarrow } {f_1 ^{-1} } \left\{ 1\right\} \neq \stackrel { \rightarrow }{f_2 ^{-1} } \left\{ 1\right\} =:A_2.}\) .

Ponieważ \(\displaystyle{ A_1 \neq A_2}\), to \(\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 to oznacza, że istnieje element \(\displaystyle{ x\in A_1}\), taki, że \(\displaystyle{ x\not\in A_2}\). Wtedy \(\displaystyle{ x\in A_1 \subset \NN}\), a więc \(\displaystyle{ x\in\NN}\), a rodzina \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem zbioru \(\displaystyle{ \NN}\), zatem istnieje dokładnie jeden zbiór tego rozkładu zawierający element \(\displaystyle{ x}\), tzn. niech \(\displaystyle{ B_1\in\mathcal{R} _1}\) będzie takim zbiorem, tzn. zbiorem tego rozkładu, takim, że \(\displaystyle{ x\in B_1}\). Ponieważ \(\displaystyle{ x\in A_1}\), to elelemt \(\displaystyle{ x}\) musi być największy w \(\displaystyle{ B_1}\). Niech \(\displaystyle{ B_2\in\mathcal{R}_2}\) będzie zbiorem tego rozkładu zawierającym element \(\displaystyle{ x. }\)Wtedy \(\displaystyle{ B_1\not\in \mathcal{R}_2}\).
Gdyby bowiem byloby \(\displaystyle{ B_1\in\mathcal{R}_2}\), to wtedy ponieważ \(\displaystyle{ B_2\in\mathcal{R}_2}\), a \(\displaystyle{ \mathcal{R}_2}\), jako rozkład, jest rodziną zbiorów rozłącznych, i mamy \(\displaystyle{ x\in B_1 \cap B_2}\), więc z warunku rozłączności otrzymujemy, że \(\displaystyle{ B_1=B_2}\). Ponieważ element \(\displaystyle{ x}\) jest największy w zbiorze \(\displaystyle{ B_1}\), to również \(\displaystyle{ x}\) jest największy w zbiorze \(\displaystyle{ B_2}\). Ponieważ \(\displaystyle{ B_2\in \mathcal{R}_2,}\) to zbiór \(\displaystyle{ B_2}\) musi być postaci \(\displaystyle{ B_2= \left(z,y \right]}\) , gdzie \(\displaystyle{ z\in\NN}\) i \(\displaystyle{ y\in A_2}\), lub musi być postaci \(\displaystyle{ \left[ 0,y\right]}\) , gdzie \(\displaystyle{ y\in A_2}\), lub musi być postaci \(\displaystyle{ \left( y,y ^{+} \right]}\) , gdzie \(\displaystyle{ y\in A_2}\), w przypadku gdy zbiór \(\displaystyle{ A_2}\) jest nieskończony. W ostnim przypadku również \(\displaystyle{ y^+ \in A_2}\), więc ten przypadek podpada pod przypadek pierwszy. Tzn., mamy tak naprawdę dwa przypadki: zbiór \(\displaystyle{ B_2}\) musi być postaci \(\displaystyle{ \left( z,y\right]}\), gdzie \(\displaystyle{ z\in\NN}\), i \(\displaystyle{ y\in A_2}\) lub \(\displaystyle{ B_2= \left[ 0,y\right] }\), gdzie \(\displaystyle{ y\in A_2}\). W obydwu przypadkach element \(\displaystyle{ y}\) jest największy w \(\displaystyle{ B_2}\) oraz, w obydwu przypadkach , \(\displaystyle{ y\in A_2}\). Ponieważ element \(\displaystyle{ x}\) jest największy w \(\displaystyle{ B_2}\), a w danym zbiorze istnieje tylko jeden element największy, a zatem \(\displaystyle{ x=y}\). Ponieważ \(\displaystyle{ y\in A_2}\), to również \(\displaystyle{ x\in A_2}\), co daje sprzeczność.
Wobec czego \(\displaystyle{ B_1\not\in\mathcal{R}_2}\), a \(\displaystyle{ B_1\in\mathcal{R}_1}\), a zatem \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2.
}\)


Jeśli \(\displaystyle{ A_2\not\subset A_1}\), to w sposób symetryczny udowadniamy, że \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2.}\)

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. A zatem:

\(\displaystyle{ \left| \left\{ 0,1\right\} ^{\NN} \right| \le \left| \mathbb{B} \right| }\).

Czyli:

\(\displaystyle{ \left| \mathbb{B} \right| \ge \left| 2 ^{\NN} \right| =\left| \RR\right| .}\)

A \(\displaystyle{ \mathbb{B}}\) jest rodziną rozkładów zbioru \(\displaystyle{ \NN\sim \NN}\), a wszystkich rozkładów zbioru przeliczalnego jest continuum, wobec czego \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|}\). Na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \left| \mathbb{B}\right| = \left| \RR\right|}\), czyli istnieje dokładnie continuum rozkładów zbioru liczb naturalnych na przedziały.\(\displaystyle{ \square}\) :D
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Rozkłady zbiorów

Post autor: Jan Kraszewski »

No to krócej.

W oczywisty sposób wystarczy pokazać, że jest przynajmniej continuum rozkładów \(\displaystyle{ \NN}\) na przedziały (stąd od razu dostajemy oszacowanie od dołu dla \(\displaystyle{ \ZZ}\), a oszacowania z góry są trywialne). W tym celu wskażemy różnowartościowe przyporządkowanie funkcjom z \(\displaystyle{ \{0,1\}^\NN}\) takich rozkładów.

Dla \(\displaystyle{ f\in\{0,1\}^\NN}\) ustalamy rozkład \(\displaystyle{ \mathcal{R}_f}\) w następujący sposób: jeśli \(\displaystyle{ f(n)=1}\), to \(\displaystyle{ \{2n,2n+1\}\in\mathcal{R}_f }\), jeśli zaś \(\displaystyle{ f(n)=0}\), to \(\displaystyle{ \{2n\},\{2n+1\}\in\mathcal{R}_f }\). Elementami rozkładu \(\displaystyle{ \mathcal{R}_f}\) są przedziały jedno- i dwuelementowe i dla różnych funkcji dostajemy różne podziały.

JK

@edit: poprawa literówki.
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: Rozkłady zbiorów

Post autor: Jakub Gurak »

Mam jeszcze pytanie:
Jan Kraszewski pisze: 14 wrz 2022, o 00:08Dla \(\displaystyle{ f\in\{0,1\}^\NN}\) ustalamy rozkład \(\displaystyle{ \mathcal{R}_f}\) w następujący sposób: jeśli \(\displaystyle{ f(n)=0}\), to \(\displaystyle{ \{2n,2n+1\}\in\mathcal{R}_f }\), jeśli zaś \(\displaystyle{ f(n)=0}\), to \(\displaystyle{ \{2n\},\{2n+1\}\in\mathcal{R}_f }\).
Aha, tu zapewne pomyłka, bo nie rozpatruje Pan dwa razy tego samego przypadku.

Jak chcę Pan formalnie zdefiniować ten rozkład??
Trochę zdziwił mnie sposób w jaki Pan zdefiniował ten rozkład, nie spotkałem jeszcze czegoś takiego. Co więcej, musimy zdefiniować jeden rozkład, a tu w jednym przypadku mamy jeden zbiór, a w drugim przypadku rozważa Pan dwa zbiory. Nie wiem jaką wspólną cechę mają te dwa przypadki, aby zdefiniować jeden rozkład. Jak to zrobić formalnie??
ODPOWIEDZ