Wczoraj udowodniłem ogólniejszy fakt niż tytułowy fakt (ale w dowodzie z niego korzystałem, to inna sprawa, myślę, że jest dobrze)- udowodniłem, że jeśli
\(\displaystyle{ X}\) jest zbiorem,
\(\displaystyle{ R}\) relacją równoważności w
\(\displaystyle{ X}\), gdy
\(\displaystyle{ Y}\) jest zbiorem,
\(\displaystyle{ S}\) relacją równoważności w
\(\displaystyle{ Y}\), to
\(\displaystyle{ R\cup S}\) jest relacją równoważności w
\(\displaystyle{ X\cup Y}\) (oczywiście nie zawsze), ale dokładnie wtedy, gdy dla dowolnego
\(\displaystyle{ x\in X\cap Y}\), mamy
\(\displaystyle{ ([x]_R\subset [x]_S\subset X\cap Y \hbox{ lub } [x]_S\subset [x]_R\subset X\cap Y).}\) Przedstawię teraz dowód, a na koniec podam jak wygłąda w takim wypadku rozkład względem
\(\displaystyle{ R\cup S}\) w
\(\displaystyle{ X\cup Y}\).
Dowód:
Zauważmy najpierw, że
\(\displaystyle{ R\subset X\times X, S\subset Y\times Y}\), więc
\(\displaystyle{ R\cup S\subset (X\times X)\cup (Y\times Y)\subset \left( X\cup Y\right) \times\left( X\cup Y\right) \cup\left( X\cup Y\right) \times\left( X\cup Y\right) = (X\cup Y)\times (X\cup Y)}\), a więc istotnie
\(\displaystyle{ R\cup S}\) jest relacją w
\(\displaystyle{ X\cup Y.}\)
Udowodnijmy
Lemat, gdyż będziemy z niego korzystać wielokrotnie , że jeśli
\(\displaystyle{ A}\) jest zbiorem, a relacja
\(\displaystyle{ T}\) w zbiorze
\(\displaystyle{ A}\) jest relacją równoważności, a
\(\displaystyle{ B\subset A }\) jest podzbiorem zbioru
\(\displaystyle{ A}\), to
\(\displaystyle{ T\cap B\times B}\) jest relacją równoważności w
\(\displaystyle{ B}\) (czyli zawężenie relacji równoważności do podzbioru jest relacją równoważności w tym podzbiorze).
Dowód Lematu:
Wiemy, że dla dowolnego ustalonego zbioru
\(\displaystyle{ C}\) relacja
\(\displaystyle{ C\times C}\) jest relacją równoważności w
\(\displaystyle{ C}\). Wobec czego dla zbioru
\(\displaystyle{ B\subset A}\) relacja
\(\displaystyle{ B\times B}\) jest relacją równoważności w
\(\displaystyle{ B}\), oraz relacja
\(\displaystyle{ T}\) w zbiorze
\(\displaystyle{ A}\) jest relacją równoważności, wobec czego przekrój
\(\displaystyle{ T\cap (B\times B)}\) jest relacją równoważności w
\(\displaystyle{ A\cap B=B}\) (na mocy faktu który ostatnio udowodniłem
TUTAJ ).
\(\displaystyle{ \square}\)
Przejdźmy do właściwego dowodu:
Przypuśćmy, że
\(\displaystyle{ R\cup S}\) jest relacją równoważności w
\(\displaystyle{ X\cup Y}\)( wiemy, że
\(\displaystyle{ R,S}\) również są relacjami równoważności odpowiednio w
\(\displaystyle{ X}\) i
\(\displaystyle{ Y}\)).
Na mocy lematu
\(\displaystyle{ (R\cup S)\cap ((X\cap Y)\times (X\cap Y ))}\) jest relacją równoważności w
\(\displaystyle{ X\cap Y}\), będziemy dalej, dla uproszczenia zapisu oznaczać
\(\displaystyle{ (R\cup S)_{|X\cap Y}.}\) Ogólniej, dla relacji
\(\displaystyle{ T}\) w zbiorze
\(\displaystyle{ A}\), dla podzbioru
\(\displaystyle{ B\subset A}\), relację z tego lematu
\(\displaystyle{ T\cap B\times B}\) będziemy oznaczać jako
\(\displaystyle{ T_{|B}}\). Zatem
\(\displaystyle{ \left( R\cup S\right) _{|X\cap Y}}\) jest relacją równoważności w
\(\displaystyle{ X\cap Y.}\) Stosując lemat ponownie do relacji
\(\displaystyle{ R}\), i do zbioru
\(\displaystyle{ X\cap Y}\) otrzymujemy, że
\(\displaystyle{ R_{|X\cap Y}}\) jest relacją równoważności w
\(\displaystyle{ X\cap Y}\), i podobnie stosując lemat dla relacji
\(\displaystyle{ S}\) otrzymujemy, że
\(\displaystyle{ S_{|X\cap Y}}\) jest relacją równoważności w
\(\displaystyle{ X\cap Y.}\) Łatwo się przekonać, że
\(\displaystyle{ (R\cup S)_{|X\cap Y}=R _{|X\cap Y} \cup S_{|X\cap Y}}\), a relacja z lewej strony równości jest relacją równoważności w
\(\displaystyle{ X\cap Y}\). Zauważmy, że również
\(\displaystyle{ R _{|X\cap Y} }\) oraz
\(\displaystyle{ S _{|X\cap Y} }\) są relacjami równoważności w
\(\displaystyle{ X\cap Y}\), i ich suma jest relacja równoważności w
\(\displaystyle{ X\cap Y}\). Możemy zatem zastosować tytułowe twierdzenie tego postu otrzymując, że musi dla każdego
\(\displaystyle{ x\in X \cap Y }\) zachodzić :
\(\displaystyle{ [x]_{R _{X\cap Y}} \subset [x]_{S_{|X\cap Y}}}\) lub
\(\displaystyle{ [x]_{S_{|X\cap Y}}\subset [x]_{R_{|X\cap Y}}.}\) Oznacza, to że dla każdego
\(\displaystyle{ x\in X\cap Y}\):
\(\displaystyle{ [x]_R\subset [x]_S\subset X\cap Y}\) lub
\(\displaystyle{ [x]_S\subset [x]_R\subset X\cap Y}\), co dowodzi implikacji w jedną stronę.
Przypuśćmy teraz, że dla każdego
\(\displaystyle{ x\in X\cap Y}\), mamy:
\(\displaystyle{ \left( [x]_R\subset [x]_S\subset X\cap Y \hbox{ lub } [x]_S\subset [x]_R\subset X\cap Y.\right) }\)) Uzasadnijmy krótko, że dla każdego
\(\displaystyle{ x\in X\cap Y}\), mamy:
\(\displaystyle{ [x]_{R_{|X\cap Y}}=[x]_R}\) oraz
\(\displaystyle{ [x]_S=[x]_{S_{|X\cap Y}}}\). Aby uzasadnić pierwszą równość zauważmy, że zbiór po lewej stronie równości jest podzbiorem
\(\displaystyle{ X\cap Y,}\) i zbiór po prawej stronie również jest podzbiorem
\(\displaystyle{ X\cap Y}\)- na mocy założenia. W związku z czym, aby pokazać równość tych dwóch zbiorów, wystarczy pokazać, że dowolny element
\(\displaystyle{ y\in X\cap Y}\) należy do zbioru po lewej stronie równości, wtedy i tylko wtedy, gdy należy do zbioru po prawej. Wobec czego niech
\(\displaystyle{ y\in X\cap Y.}\) Wtedy
\(\displaystyle{ y\in[x]_{R_{|X\cap Y}} \Leftrightarrow (y,x)\in R \cap \left( X \cap Y\right)\times \left( X \cap Y\right) \Leftrightarrow (y,x)\in R \hbox{ i } y\in X \cap Y \hbox{ i } x\in X\cap Y \mathop{\stackrel {y\in X\cap Y, } {\Longleftrightarrow} } _{x\in X\cap Y} (y,x)\in R \Leftrightarrow y\in [x]_R.}\)
Zatem (patrz komentarz powyżej)
\(\displaystyle{ [x]_{R_{|X\cap Y}}=[x]_R.}\) Dowód, że
\(\displaystyle{ [x]_{S_{|X\cap Y}}=[x]_S}\) jest analogiczny. Mamy zatem, że dla każdego
\(\displaystyle{ x\in X\cap Y: [x]_{R_{|X\cap Y}}=[x]_R}\) oraz dla każdego
\(\displaystyle{ x\in X\cap Y: [x]_S=[x]_{S_{|X\cap Y}}}\), i z założenia dla każdego
\(\displaystyle{ x\in X\cap Y}\), mamy:
\(\displaystyle{ [x]_R\subset [x]_S}\) lub
\(\displaystyle{ [x]_S\subset [x]_R}\). Wnioskujemy zatem, że dla każdego
\(\displaystyle{ x\in X \cap Y}\), mamy:
\(\displaystyle{ [x]_{R_{|X\cap Y}}\subset [x]_{S_{|X\cap Y}}}\) lub
\(\displaystyle{ [x]_{S_{|X\cap Y}}\subset [x]_{R_{|X\cap Y}}}\). Na mocy lematu relacje
\(\displaystyle{ R _{|X\cap Y} , S _{|X\cap Y} }\) są relacjami równoważności w
\(\displaystyle{ X\cap Y.}\) Ponadto dla każdego
\(\displaystyle{ x\in X\cap Y}\) zachodzi ostatnio wspomniana własność. W związku z czym, na mocy tytułowego twierdzenia
\(\displaystyle{ (R _{|X\cap Y} )\cup\left( S_{|X\cap Y} \right) }\) jest relacją równoważności w
\(\displaystyle{ X \cap Y.}\) Na mocy lematu
\(\displaystyle{ R _{|X \setminus Y} }\) jest relacją równoważności w
\(\displaystyle{ X \setminus Y}\), jak również
\(\displaystyle{ S _{Y \setminus X} }\) jest relacją równoważności w
\(\displaystyle{ Y \setminus X.}\)
Wykażemy teraz, że
\(\displaystyle{ R \cup S=(R _{|X\cap Y} \cup S _{|X\cap Y}) \cup R _{|X \setminus Y}\cup S _{Y \setminus X} .}\)
W tym celu wykażemy najpierw, że
\(\displaystyle{ R=R _{|X\cap Y} \cup R _{|X \setminus Y}.}\)
Ponieważ
\(\displaystyle{ R\subset X\times X}\), (będziemy wyjątkowo oznaczać zbiór
\(\displaystyle{ A\times A}\) jako
\(\displaystyle{ A^{2}}\)- dla uproszczenia zapisu, i tak będzie trochę żmudny), więc
\(\displaystyle{ R=R \cap X^{2} =R \cap \left[ \left( X \setminus Y\right) \cup \left( X \cap Y\right)\right] ^{2}=R \cap\left[ \left( X \setminus Y\right) ^{2} \cup \left( \left( X \setminus Y\right) \times \left( X \cap Y\right)\right) \cup \left( \left( X \cap Y\right) \times \left( X \setminus Y\right) \right) \cup \left( \left( X \cap Y\right) ^{2} \right) \right]= \\
=\left[ R \cap \left( X \setminus Y\right) ^{2}=R _{|X \setminus Y}\right] \cup \left[ R \cap \left( X \cap Y\right) ^{2}=R _{|X\cap Y}\right] \cup \left[ R \cap \left( X \setminus Y\right) \times \left( X \cap Y\right) \right] \cup \left[ R \cap \left( X \cap Y\right) \times \left( X \setminus Y\right)\right]= }\)
Pozostaje wyzerować dwa ostatnie składniki( czyli, pokazać, że są zbiorami pustymi).
Przypuśćmy nie wprost, że
\(\displaystyle{ R \cap \left( X \setminus Y\right) \times \left( X \cap Y \right) \neq \left\{ \right\} .}\) Istnieje wtedy para
\(\displaystyle{ (a,b)}\) należąca do takiego zbioru. Wtedy
\(\displaystyle{ (a,b)\in R, a\in X \setminus Y, b\in X \cap Y.}\) Ponieważ
\(\displaystyle{ b\in X\cap Y }\), na mocy naszego głównego założenia
\(\displaystyle{ \left[ b\right] _R\subset X \cap Y}\), ponieważ
\(\displaystyle{ (a,b)\in R}\), więc
\(\displaystyle{ a\in\left[ b\right] _R\subset X \cap Y}\), więc
\(\displaystyle{ a\in X \cap Y}\), a
\(\displaystyle{ a\in X \setminus Y}\)- sprzeczność. Wobec czego
\(\displaystyle{ R \cap \left( X \setminus Y\right) \times \left( X \cap Y \right)=\left\{ \right\}.}\)
Pozostaje wyzerować drugi zbiór.
Przypuśćmy nie wprost, że istnieje para
\(\displaystyle{ (a,b)\in R \cap \left( X \cap Y\right) \times \left( X \setminus Y \right) }\), wtedy
\(\displaystyle{ (a,b)\in R}\),
\(\displaystyle{ a\in X \cap Y, b\in X\setminus Y.}\) Ponieważ
\(\displaystyle{ a\in X \cap Y}\) więc na mocy naszego głównego założenia
\(\displaystyle{ [a]_R\subset X \cap Y}\), ponieważ
\(\displaystyle{ (a,b)\in R}\), to
\(\displaystyle{ b\in[a]_R\subset X \cap Y}\), więc
\(\displaystyle{ b\in Y}\),a
\(\displaystyle{ b\in X \setminus Y}\)- sprzeczność. Wobec czego
\(\displaystyle{ R \cap \left( X \cap Y\right) \times \left( X \setminus Y\right)=\left\{ \right\} .}\)
Otrzymujemy zatem, że
\(\displaystyle{ R=R _{|X\cap Y} \cup R _{|X \setminus Y}.}\)
Podobnie wykażemy, że
\(\displaystyle{ S=S _{|X\cap Y} \cup S _{|Y \setminus X}.}\)
Ponieważ
\(\displaystyle{ S\subset Y\times Y}\), to
\(\displaystyle{ S=S \cap \left( Y\times Y\right)=S \cap Y^{2}=S \cap \left( \left( X \cap Y\right) \cup( Y \setminus X ) \right) ^{2}= \\
=S \cap \left[ \left( \left( X \cap Y\right) ^{2} \right) \cup \left( \left( X \cap Y\right)\times \left( Y \setminus X\right)\right) \cup\left( \left( Y\setminus X \right) \times \left( X \cap Y\right)\right) \cup\left( \left( Y \setminus X\right) ^{2}\right) \right]=\\
= \left[ S \cap \left( X \cap Y\right) ^{2}=S _{|X\cap Y}\right] \cup \left[ S \cap \left( Y \setminus X\right) ^{2}=S _{|Y \setminus X}\right] \cup \left[ S \cap \left( X\cap Y\right) \times \left( Y \setminus X\right) \right] \cup \left[ S \cap \left( Y \setminus X\right) \times \left( X \cap Y\right)\right].}\) Pozostaje wyzerować dwa ostatnie składniki (czyli pokazać, że są puste) .
Aby wyzerować ostatni zbiór, przypuśćmy nie wprost, że istnieje para
\(\displaystyle{ (a,b)\in S \cap \left( Y \setminus X\right) \times \left( X \cap Y\right).}\) Wtedy
\(\displaystyle{ (a,b)\in S, a\in Y \setminus X, b\in X \cap Y}\). Wtedy, z głównego naszego założenia
\(\displaystyle{ \left[ b\right]_S \subset X\cap Y.}\) Ponieważ
\(\displaystyle{ (a,b)\in S}\), to
\(\displaystyle{ a\in\left[ b\right] _S\subset X \cap Y}\), więc
\(\displaystyle{ a\in X \cap Y}\), a
\(\displaystyle{ a\in Y \setminus X}\)- sprzeczność. Wobec czego
\(\displaystyle{ S \cap \left( Y \setminus X\right) \times \left( X \cap Y\right)=\left\{ \right\}.
}\)
Ostatni zbiór, czyli
\(\displaystyle{ S \cap \left( X \cap Y\right) \times \left( Y \setminus X\right) }\) zerujemy podobnie (dowodem nie wprost).
Otrzymujemy zatem, że
\(\displaystyle{ S=S _{|X\cap Y} \cup S _{|Y \setminus X}.}\)
Przypominam udowodniliśmy podobnie wcześniej, że
\(\displaystyle{ R=R _{|X\cap Y} \cup R _{|X \setminus Y}.}\)
, wobec czego
\(\displaystyle{ R\cup S=(R _{|X\cap Y} \cup R _{|X \setminus Y}) \cup \left( S _{|X\cap Y} \cup S _{|Y \setminus X}\right) =\left( R _{|X\cap Y} \cup S _{|X\cap Y} \right) \cup \left( R_{|X \setminus Y} \right) \cup \left( S _{|Y \setminus X}\right).}\)
Ponieważ uzasadniliśmy już że pierwszy składnik tej sumy jest relacją równoważności w
\(\displaystyle{ X \cap Y}\), również drugi składnik jest relacją równoważności w
\(\displaystyle{ X \setminus Y}\) na mocy lematu, i znowu z tego lematu trzeci składnik jest relacją równoważności w
\(\displaystyle{ Y \setminus X}\), wobec czego suma takich trzech relacji równoważności, czyli
\(\displaystyle{ R \cup S}\) (na zbiorach rozłącznych) jest relacją równoważności w
\(\displaystyle{ \left( X\cap Y \right) \cup \left( X \setminus Y\right) \cup \left( Y \setminus X\right)= X\cup Y}\) ( w podanym linku można znaleźć dowód, że suma dwóch relacji równoważności na zbiorach rozłącznych jest relacją równoważności)
\(\displaystyle{ .\square}\) 
W takim wypadku rozkład w
\(\displaystyle{ X \cup Y}\) względem
\(\displaystyle{ R \cup S}\) jest równy
\(\displaystyle{ \left\{ \left[ x\right] _{R} \cup [x]_S\Bigl | \ x\in X \cap Y \right\} \cup \left\{ \left[ x\right]_R\Bigl | \ | x\in X \setminus Y \right\} \cup \left\{ \left[ x\right]_S\Bigl| \ x\in Y \setminus X \right\},}\)
Czyli w części wspólnej mamy ten bombowy rozkład (to, jak już kiedyś chyba przyznałem, jest dla mnie chyba najpiękniejsza ilustracja matematyczna, więc będę się starał ponownie nie zachwycać) , gdzie klasą równoważności dowolnego punktu względem
\(\displaystyle{ R \cup S}\) jest większa z klas równoważności tego punktu względem odpowiednio
\(\displaystyle{ R}\) i
\(\displaystyle{ S}\), na
\(\displaystyle{ X \setminus Y}\) mamy rozkład jak dla
\(\displaystyle{ R}\), na
\(\displaystyle{ Y \setminus X}\) mamy rozkład jak dla
\(\displaystyle{ S}\). Może się nie będę zachwycał, powiem tylko, że dalej mi się to podoba, nawet, choć tamto znałem, to ten nowy wynik wygląda ładnie.
Zauważmy na koniec, że wygląda na to, że tytułowe twierdzenie jest szczególnym przypadkiem (pojęciowo, nie w dowodzie, w naszym dowodzie z tego tytułowego twierdzenia korzystaliśmy) pojęciowo jest szczególnym przypadkiem wykazanego teraz twierdzenia, jak również, wygląda na to, że fakt, mówiący że suma dwóch relacji równoważności na zbiorach rozłącznych jest relacją równoważności ten fakt jest szczególnym przypadkiem tego twierdzenia( wtedy
\(\displaystyle{ X \cap Y}\) jest zbiorem pustym, więc warunek jest pusto spełniony, więc formalnie jest spełniony i chyba się zgadza), znowu nie w dowodzie, tylko pod względem treści. Jest to po prostu najogólniejszy warunek kiedy suma dwóch relacji równoważności jest relacją równoważności w sumie tych dwóch zbiorów na których są określone te relacje równoważności.
