1.Rodzina \(\displaystyle{ \mathbb{A}}\) jest zamknięta na przekroje mnogościowe i \(\displaystyle{ X \times X\in\mathbb{A}.}\)
2. Każda relacja w zbiorze \(\displaystyle{ X}\) ma domknięcie w zbiorze relacji \(\displaystyle{ \mathbb{A}.}\)
Domknięcie w zbiorze relacji to najmniejsza relacja(względem inkluzji) będąca nadzbiorem danej relacji należąca do zbioru relacji \(\displaystyle{ \mathbb{A}.}\)
Dowód:
\(\displaystyle{ (1) \rightarrow (2).}\) Niech \(\displaystyle{ R}\) będzie relacją w zbiorze \(\displaystyle{ X}\). Utwórzmy zbiór relacji jako: \(\displaystyle{ \mathbb{B}= \left\{ S\subset X \times X\Bigl | \ \ R\subset S \wedge S \in \mathbb{A}\right\} .}\) Ponieważ z założenia \(\displaystyle{ (1)}\), mamy \(\displaystyle{ X\times X \in \mathbb{A}}\), więc łatwo sprawdzić, że \(\displaystyle{ X\times X \in \mathbb{B}.}\) Zatem rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta. Pokażemy, że \(\displaystyle{ \bigcap \mathbb{B}}\) jest domknięciem relacji \(\displaystyle{ R}\), w zbiorze relacji \(\displaystyle{ \mathbb{A}.}\) Z określenia rodziny \(\displaystyle{ \mathbb{B}}\) wynika, że relacja \(\displaystyle{ R}\) zawiera się w każdej relacji tej rodziny, zatem również \(\displaystyle{ R}\) zawiera się w ich iloczynie, a więc \(\displaystyle{ R\subset \bigcap \mathbb{B}}\). Ponieważ z określenia rodziny \(\displaystyle{ \mathbb{B}}\) wynika, że każdy jej element jest elementem \(\displaystyle{ \mathbb{A}}\), to na podstawie \(\displaystyle{ (1)}\)otrzymujemy, że również \(\displaystyle{ \bigcap \mathbb{B} \in \mathbb{A}.}\) Minimalność \(\displaystyle{ \bigcap \mathbb{B}}\) uzasadniamy przez: niech relacja \(\displaystyle{ T \supset R}\), będzie taka, że \(\displaystyle{ T\in\mathbb{A}.}\) Oznacza to, że \(\displaystyle{ T\in\mathbb{B}.}\) Zatem z własności iloczynu \(\displaystyle{ \bigcap \mathbb{B}\subset T.}\) W ten oto sposób zostały spełnione wszystkie wymagania stawiane relacji \(\displaystyle{ \bigcap \mathbb{B}}\) na bycie domknięciem relacji \(\displaystyle{ R}\) w zbiorze relacji \(\displaystyle{ \mathbb{A}}\), a więc relacja \(\displaystyle{ R}\) ma domknięcie w zbiorze relacji \(\displaystyle{ \mathbb{A}.}\)
\(\displaystyle{ (2) \rightarrow (1).}\) Na początek zauważmy, że relacja \(\displaystyle{ X\times X}\) (jak każda) ma domknięcie w zbiorze relacji \(\displaystyle{ \mathbb{A}.}\) Domknięcie takie musi być nadzbiorem relacji i elementem zbioru \(\displaystyle{ \mathbb{A}.}\) A ponieważ domknięcie nie może być istotnym nadzbiorem \(\displaystyle{ X\times X}\), więc musi być równe \(\displaystyle{ X\times X}\), stąd \(\displaystyle{ X\times X \in \mathbb{A}.}\) Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{B} \subset \mathbb{A}.}\) Pokażemy, że \(\displaystyle{ \bigcap \mathbb{B} \in \mathbb{A}.}\) Niewątpliwie iloczyn niepustej rodziny relacji z \(\displaystyle{ X}\)do \(\displaystyle{ X}\) jest relacją z \(\displaystyle{ X}\) do \(\displaystyle{ X}\). Relacja ta (\(\displaystyle{ \bigcap \mathbb{B}}\)) ma domknięcie w zbiorze relacji \(\displaystyle{ \mathbb{A},}\) nazwijmy je \(\displaystyle{ S}\). Punkt \(\displaystyle{ (3)}\) definicji domknięcia mówi, że dla dowolnej relacji \(\displaystyle{ T}\), o ile \(\displaystyle{ \bigcap \mathbb{B} \subset T}\) i \(\displaystyle{ T\in \mathbb{A}}\) to \(\displaystyle{ S \subset T.}\) Połóżmy za \(\displaystyle{ T}\) dowolny element z \(\displaystyle{ \mathbb{B}.}\) Założenia implikacji pozostają spełnione, jest więc tak, że \(\displaystyle{ S \subset T}\), dla dowolnej relacji \(\displaystyle{ T\in\mathbb{B}.}\) W takim razie z własności iloczynu \(\displaystyle{ S \subset \bigcap \mathbb{B}}\). Ponieważ mamy też \(\displaystyle{ \bigcap \mathbb{B} \subset S}\), bo \(\displaystyle{ S}\) jest domknięciem \(\displaystyle{ \bigcap \mathbb{B},}\) jest więc \(\displaystyle{ \bigcap \mathbb{B}= S}\), a ponieważ domknięcie \(\displaystyle{ S}\) relacji \(\displaystyle{ \bigcap \mathbb{B}}\) w zbiorze relacji \(\displaystyle{ \mathbb{A},}\) jest elementem \(\displaystyle{ \mathbb{A},}\) to \(\displaystyle{ \bigcap \mathbb{B} \in \mathbb{A}}\). Zatem rodzina \(\displaystyle{ \mathbb{A}}\) jest zamknięta na przekroje i \(\displaystyle{ X\times X \in \mathbb{A}.\square}\)
Mogę zatem podać przykład zastosowania tego twierdzenia( i podać korzyść z takiego podejścia do domknięcia relacji). Najpierw przypomnę fakt:
Jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{B}}\) dowolną niepustą rodziną relacji równoważności, to \(\displaystyle{ \bigcap \mathbb{B}}\) jest relacją równoważności w \(\displaystyle{ X}\), oraz dla dowolnego \(\displaystyle{ x\in X}\):
\(\displaystyle{ \left[ x\right] _{\bigcap\mathbb{B} }= \bigcap_{R \in \mathbb{B}} \left[ x\right] _{R}.}\)
To można bardzo łatwo udowodnić.
W związku z czym, jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich relacji równoważności w \(\displaystyle{ X}\), to taka rodzina jest zamknięta na przekroje, i łatwo sprawdzić, że \(\displaystyle{ X \times X}\) jest relacją równoważności wobec czego, w myśl tego twierdzenia, każda relacja w zbiorze \(\displaystyle{ X}\) ma domknięcie wśród relacji równoważności. Ponadto domknięcie jeżeli istnieje, to zawsze jest jedyne. Wobec czego każda relacja w zbiorze \(\displaystyle{ X}\) ma dokładnie jedno domknięcie wśród relacji równoważności, czyli relacje równoważności będąca nadzbiorem danej relacji, i najmniejszą taką relacje pod względem inkluzji. Tyle- nie musimy robić nie wiadomo jakich konstrukcji.
Możliwe też, że dla przechodniego domknięcia relacji w podobny sposób (na logikę) można by wprowadzić przechodnie domkniecie relacji( ale musiałbym się zastanowić czy rodzina wszystkich relacji przechodnich jest zamknięta na przekroje).Wykażemy teraz, że jeśli \(\displaystyle{ X}\) jest zbiorem a \(\displaystyle{ R}\) relacją zwrotną w zbiorze \(\displaystyle{ X}\), równoważnie zawierającą identyczność \(\displaystyle{ I_X}\), to istnieje maksymalna relacja równoważności zawarta w \(\displaystyle{ R}\).
Czyli relacja zawarta w danej relacji \(\displaystyle{ R}\), maksymalna ale będąca relacją równoważności.
Dowód (korzystający z lematu Zorna):
Rozważmy rodzinę relacji:
\(\displaystyle{ \mathbb{B}=\left\{ S\subset X \times X\Bigl| \ \ S \subset R \hbox{ i } S \hbox{ jest relacją równoważności na } X\right\}. }\) Mamy, że \(\displaystyle{ I_X}\) jest relacją równoważności, i \(\displaystyle{ I_X\subset R}\), a więc \(\displaystyle{ I_X\in\mathbb{B}.}\) A zatem \(\displaystyle{ \mathbb{B} \neq \left\{ \right\} }\). Tą rodzinę relacji uporządkujmy inkluzją. Wtedy \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) jest zbiorem uporządkowanym. Stosujemy do niego lemat Zorna.
W tym celu ustalmy dowolny niepusty łańcuch \(\displaystyle{ \mathbb{D} \subset \mathbb{B}.}\)( dla pustego łańcucha możemy wziąć dowolny element \(\displaystyle{ \mathbb{B} \neq \left\{ \right\} }\).) Kładziemy \(\displaystyle{ \bigcup\mathbb{D} }\) jako ograniczenie górne, ale wpierw musimy zapewnić, że \(\displaystyle{ \bigcup\mathbb{D}\in\mathbb{B}}\). Suma rodziny \(\displaystyle{ \mathbb{D}}\) podzbiorów \(\displaystyle{ X \times X}\) niewątpliwie będzie podzbiorem \(\displaystyle{ X \times X}\)( czyli relacją w zbiorze \(\displaystyle{ X}\)). Musimy wykazać, że \(\displaystyle{ \bigcup\mathbb{D} \subset R}\), i że \(\displaystyle{ \bigcup\mathbb{D}}\) jest relacją równoważności. Ponieważ każda relacja w \(\displaystyle{ \mathbb{D}}\) jest elementem \(\displaystyle{ \mathbb{B}}\), i w związku z czym podzbiorem \(\displaystyle{ R}\), to również ich unia (suma) jest podzbiorem \(\displaystyle{ R}\), skąd \(\displaystyle{ \bigcup\mathbb{D} \subset R.}\) Wykażemy teraz, że \(\displaystyle{ \bigcup\mathbb{D}}\) jest relacją równoważności. Relacja \(\displaystyle{ \bigcup\mathbb{D}}\) jest zwrotna, gdyż jeśli \(\displaystyle{ x\in X}\), ponieważ \(\displaystyle{ \mathbb{D} \neq \left\{ \right\}}\), to istnieje \(\displaystyle{ C\in\mathbb{D} \subset \mathbb{B}}\), a więc \(\displaystyle{ C\in \mathbb{B}}\), skąd \(\displaystyle{ C}\) jest relacją równoważności (a więc jest zwrotna), skąd \(\displaystyle{ (x,x)\in C\in \mathbb{D}}\), a więc \(\displaystyle{ (x,x)\in \bigcup \mathbb{D}.}\) Relacja \(\displaystyle{ \bigcup\mathbb{D}}\) jest symetryczna, gdyż jeśli \(\displaystyle{ (a,b)\in \bigcup\mathbb{D}}\), wtedy dla pewnego \(\displaystyle{ C\in \mathbb{D}}\) mamy \(\displaystyle{ (a,b)\in C}\), ponieważ wtedy \(\displaystyle{ C\in \mathbb{D}}\), to \(\displaystyle{ C}\) jest relacją równoważności ( więc jest symetryczna), skąd \(\displaystyle{ (b,a)\in C\in\mathbb{D}}\), więc \(\displaystyle{ (b,a)\in\bigcup \mathbb{D}}\). Jest też przechodnia, gdyż jeśli \(\displaystyle{ (a,b),(b,c)\in \bigcup \mathbb{D}}\), to \(\displaystyle{ (a,b)\in C}\) dla pewnego \(\displaystyle{ C\in\mathbb{D}}\) oraz \(\displaystyle{ (b,c)\in A}\) dla pewnego \(\displaystyle{ A\in\mathbb{D}}\). Ponieważ \(\displaystyle{ \mathbb{D}}\) jest łańcuchem pod względem inkluzji, więc \(\displaystyle{ C \subset A}\) lub \(\displaystyle{ A \subset C}\). Jeśli \(\displaystyle{ C \subset A}\), to \(\displaystyle{ (a,b),(b,c)\in A}\), i ponieważ relacja \(\displaystyle{ A\in \mathbb{D}\subset \mathbb{B}}\), a więc jest relacją równoważności, a więc jest przechodnia, to \(\displaystyle{ (a,c)\in A\in\mathbb{D}}\), więc \(\displaystyle{ (a,c)\in \bigcup \mathbb{D}}\). Drugi przypadek jest analogiczny. Wobec czego \(\displaystyle{ \bigcup \mathbb{D}}\) jest przechodnia, i jest relacją równoważności. A więc \(\displaystyle{ \bigcup\mathbb{D}\in\mathbb{B}.}\) Poniewąż relacja \(\displaystyle{ \bigcup\mathbb{D}}\) jest nadzbiorem każdej relacji z \(\displaystyle{ \mathbb{D}}\), stąd \(\displaystyle{ \bigcup\mathbb{D}}\) jest ograniczeniem górnym dla \(\displaystyle{ \mathbb{D}}\)- tego łańcucha. Wnioskujemy, że w \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) każdy łańcuch ma ograniczenie górne.
Stosując lemat Zorna otrzymujemy element maksymalny w \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\). Jest to maksymalna relacja równoważności zawarta w \(\displaystyle{ R}\). \(\displaystyle{ \square}\)
