Korzyść jest taka, że dzięki temu możemy łatwo uzasadnić, że każda relacja
\(\displaystyle{ R}\) w zbiorze
\(\displaystyle{ X}\) ma domknięcie będącą relacją równoważności (oraz każda relacja ma domknięcie będące relacją przechodnią) -gdyż łatwo jest uzasadnić, że jeśli mamy niepustą rodzinę relacji równoważności w zbiorze
\(\displaystyle{ X}\), to jej przekrój jest relacją równoważności, i łatwo jest pokazać, że cały kwadrat
\(\displaystyle{ X \times X}\) jest relacją równoważności, wobec czego, w myśl charakteryzacji domknięcia: każda relacja w zbiorze
\(\displaystyle{ X}\) ma domknięcie będące relacją równoważności. W podobny sposób uzasadniamy, że każda relacja w zbiorze
\(\displaystyle{ X}\) ma dokładnie jedno przechodnie domknięcie.
Wykazałem przed chwilą, że w zbiorze
\(\displaystyle{ X}\) dowolna relacja
\(\displaystyle{ R }\) ma domknięcie słabo spójne, dokładnie wtedy, gdy ta relacja
\(\displaystyle{ R}\) jest słabo spójna (tzn. jeśli relacja
\(\displaystyle{ R}\) jest słabo spójna, to jej domknięcie jest jej równe, a jeśli nie, to w ogóle nie ma domknięcia). Wykazałem też, że jeśli relacja
\(\displaystyle{ R}\) w zbiorze
\(\displaystyle{ X}\) nie jest silnie spójna i ma domknięcie silnie spójne, to relacja
\(\displaystyle{ R \setminus I_X}\) musi być relacją spójną; oraz wykazałem, że jeśli dla relacji
\(\displaystyle{ R}\) silnie spójnej mamy, że relacja
\(\displaystyle{ R \setminus I_X}\) jest relacją słabo spójną, to relacja
\(\displaystyle{ R}\) ma domknięcie silnie spójne. Podałem też przykład pokazujący, że istnieje zbiór
\(\displaystyle{ X,}\) oraz istnieje relacja w nim, nie będąca liniowym porządkiem, mająca domknięcie, będące liniowym porządkiem. Przedstawię teraz dowody tych
ciekawych faktów.
Niech
\(\displaystyle{ X}\) będzie zbiorem, a
\(\displaystyle{ R}\) relacją w nim, która nie jest relacją słabo spójną. Wykażemy, że nie ma ona domknięcia słabo-spójnego. Ponieważ relacja
\(\displaystyle{ R}\) nie jest słabo spójna, to dla pewnych różnych elementów
\(\displaystyle{ x,y \in X}\), mamy:
\(\displaystyle{ \left( x,y\right)\not \in R}\) i
\(\displaystyle{ \left( y,x\right)\not \in R}\). Rozważmy zbiór:
\(\displaystyle{ S:= \left\{ \left( x', y'\right) \in\left( X \times X\right) \setminus \left\{ \left( x,y\right); \left( y,x\right) \right\}\Bigl| \ \ \left( x', y'\right)\not \in R \hbox{ i } \left( y',x'\right)\not \in R \right\} .}\)
Jest to zbiór pozostałych par, takich, że dana para, wraz z przeciwległą parą, obydwie te pary nie należą do naszej relacji.
Rozważmy teraz dwie relacje:
\(\displaystyle{ S_1= R \cup S \cup \left\{ \left( x,y\right) \right\};}\) i
\(\displaystyle{ S_2= R \cup S \cup \left\{ \left( y,x\right) \right\} .}\)
Pokażemy, że relacja
\(\displaystyle{ S_1}\) jest spójna.
Niech:
\(\displaystyle{ x', y' \in X}\) będą jej dwoma różnymi elementami.
Jeśli
\(\displaystyle{ \left( x', y'\right) = \left( x,y\right) }\), to
\(\displaystyle{ \left( x', y'\right) \in S_1}\).
Jeśli
\(\displaystyle{ \left( x', y'\right)= \left( y,x\right)}\) , to
\(\displaystyle{ \left( y', x'\right) = \left( x,y\right) \in S_1}\), a zatem:
\(\displaystyle{ \left( x', y'\right) \in S_1 \hbox{ lub } \left( y',x'\right) \in S_1.}\)
Pozostaje teraz zakładać, że:
\(\displaystyle{ \left( y,x\right) \neq \left( x', y'\right) \neq \left( x,y\right).}\)
Jeśli
\(\displaystyle{ \left( x', y'\right) \in R}\), to
\(\displaystyle{ \left( x', y'\right) \in S_1}\).
Jeśli
\(\displaystyle{ \left( y', x' \right) \in R}\), to:
\(\displaystyle{ \left( x', y'\right) \in S_1 \hbox{ lub } \left( y',x'\right) \in S_1.}\)
Pozostaje zatem zakładać, że:
\(\displaystyle{ \left( x',y'\right)\not \in R \hbox{ i } \left( y',x'\right)\not \in R.}\)
Wtedy:
\(\displaystyle{ \left( x',y'\right) \in S}\), a zatem
\(\displaystyle{ \left( x', y'\right) \in S_1}\).
A zatem relacja
\(\displaystyle{ S_1}\) jest spójna.
W podobny sposób uzasadniamy, że relacja
\(\displaystyle{ S_2}\) jest spójna.
Mamy ponadto:
\(\displaystyle{ S_1\supset R}\) i
\(\displaystyle{ S_2\supset R}\).
Przypuśćmy, że relacja
\(\displaystyle{ T}\) jest spójna i jest domknięciem relacji
\(\displaystyle{ R}\).
Wtedy, z trzeciego punktu definicji domknięcia:
\(\displaystyle{ T \subset S_1}\) i
\(\displaystyle{ T \subset S_2}\), a zatem
\(\displaystyle{ T \subset S_1 \cap S_2= \left( R \cup S\right) \cup \left( \left\{\left( x,y\right) \right\} \cap \left\{ \left( y,x\right) \right\} \right)}\), i ponieważ
\(\displaystyle{ x \neq y}\), to to jest równe:
\(\displaystyle{ = R \cup S}\), czyli
\(\displaystyle{ T \subset R \cup S}\), i ponieważ
\(\displaystyle{ \left( x,y\right); \left( y,x\right)\not \in R;}\) i
\(\displaystyle{ \left( x,y\right); \left( y,x\right)\not \in S}\), to również te dwie pary nie należą do relacji
\(\displaystyle{ T}\), i ponieważ
\(\displaystyle{ x \neq y}\), to relacja
\(\displaystyle{ T}\) nie jest słabo spójna, a ona jest spójnym domknięciem -sprzeczność.
Wobec czego relacja
\(\displaystyle{ R}\) nie ma słabo-spójnego domknięcia, co kończy jedną z dwóch części naszego dowodu.
Ale druga część tego dowodu jest oczywista:
Jeśli relacja
\(\displaystyle{ R}\) jest słabo spójna, to
\(\displaystyle{ S:=R}\) jest domknięciem spójnym relacji
\(\displaystyle{ R.\square}\)
Wobec czego udowodniliśmy, że:
Dla dowolnej relacji
\(\displaystyle{ R}\) w zbiorze
\(\displaystyle{ X}\), mamy:
\(\displaystyle{ R}\) ma domknięcie słabo-spójne (nie zawsze), lecz dokładnie wtedy, gdy
\(\displaystyle{ R}\) jest słabo spójna.
Wykażemy teraz drugi nasz fakt:
Jeśli
\(\displaystyle{ R}\) jest relacją w zbiorze
\(\displaystyle{ X}\) nie będącą relacją silnie spójną, i
\(\displaystyle{ R}\) ma domknięcie
\(\displaystyle{ S}\) silnie spójne, to relacja
\(\displaystyle{ R \setminus I_X}\) jest relacją spójną (oczywiście słabo spójną).
Czyli relacja, która nie jest silnie spójna może mieć domknięcie silnie spójne, tylko wtedy, gdy poza przekątną jest spójna, a na przekątnej brakuje jej pewnej pary.
DOWÓD TEGO FAKTU:
Wykażemy, że relacja
\(\displaystyle{ S \setminus I_X}\) jest domknięciem słabo-spójnym relacji
\(\displaystyle{ R \setminus I_X.}\)
\(\displaystyle{ 1 ^{\circ}}\): Ponieważ relacja
\(\displaystyle{ S}\), jako domknięcie silnie spójne, jest relacją silnie spójną (a więc i spójną), to relacja
\(\displaystyle{ S \setminus I_X}\) jest spójna.
\(\displaystyle{ 2 ^{\circ}}\): Mamy:
\(\displaystyle{ S\supset R}\), a zatem
\(\displaystyle{ S \setminus I_X \supset R \setminus I_X}\).
\(\displaystyle{ 3 ^{\circ}}\): Jeśli
\(\displaystyle{ T\supset R \setminus I_X}\) jest relacją w
\(\displaystyle{ X}\), i
\(\displaystyle{ T}\) jest słabo spójna, to
\(\displaystyle{ T \cup I_X}\) jest relacją silnie spójną. Wtedy
\(\displaystyle{ T \cup I_X\supset \left( R \setminus I_X\right) \cup I_X \supset R.}\) Ponieważ
\(\displaystyle{ S}\) jest domknięciem silnie spójnym relacji
\(\displaystyle{ R}\), to:
\(\displaystyle{ S \subset T \cup I_X}\), a zatem
\(\displaystyle{ S \setminus I_X \subset T.}\)
A zatem relacja
\(\displaystyle{ S\setminus I_X}\) jest domknięciem słabo spójnym relacji
\(\displaystyle{ R \setminus I_X}\), więc na mocy pierwszego z naszych udowodnionych w tym poście faktów: relacja
\(\displaystyle{ R \setminus I_X}\) musi być słabo spójna
\(\displaystyle{ .\square}\)
Wykażemy teraz, że dla relacji
\(\displaystyle{ R}\) silnie spójnej w zbiorze
\(\displaystyle{ X}\), jeśli
\(\displaystyle{ R \setminus I_X}\) jest relacją słabo spójną, to
\(\displaystyle{ R}\) ma domknięcie silnie spójne.
DOWÓD TEGO FAKTU:
Ponieważ relacja
\(\displaystyle{ R}\) jest silnie spójna, to
\(\displaystyle{ R}\) jest relacją zwrotną, a zatem
\(\displaystyle{ R\supset I _{X}}\). Ponieważ relacja
\(\displaystyle{ R \setminus I_X}\) jest relacją słabo spójną, to
\(\displaystyle{ \left( R \setminus I_X\right) \cup I_X}\) jest relacją silnie spójną. I ponieważ
\(\displaystyle{ R\supset I_X}\), to ta suma jest równa relacji
\(\displaystyle{ R}\), a zatem
\(\displaystyle{ R}\) jest relacją silnie spójną. A zatem
\(\displaystyle{ S:= R}\) jest domknięciem silnie spójnym relacji
\(\displaystyle{ R.\square}\)
Wykażemy jeszcze, zgodnie z zapowiedzią, że istnieje zbiór
\(\displaystyle{ X,}\) oraz istnieje relacja w nim, nie będąca liniowym porządkiem, mająca domknięcie będące liniowym porządkiem.
DOWÓD TEGO FAKTU:
Niech:
\(\displaystyle{ X= \left\{ 0,1,2\right\};}\)
i niech:
\(\displaystyle{ R= \left\{ \left( 0,1\right); \left( 0,2\right); \left( 1,2\right) \right\} .}\)
(Nawiasem mówiąc jest to zwykły (silny) porządek na
\(\displaystyle{ \left\{ 0,1,2\right\}).}\)
A zatem, ponieważ
\(\displaystyle{ \left( 0,0\right)\not \in R}\) (
\(\displaystyle{ 0\not<0}\)), to nie jest to relacja zwrotna, i nie jest to liniowy porządek. A wtedy:
\(\displaystyle{ S:= \left\{ \left( 0,1\right); \left( 0,2\right); \left( 1,2\right); \left( 0,0\right) ; \left( 1,1\right); \left( 2,2\right) \right\}}\) jest jej domknięciem, będącym liniowym porządkiem.
\(\displaystyle{ \square}\)
Dodam tutaj jeszcze jeden dowodzik.
Wpierw przypomnę, że podzbiór
\(\displaystyle{ A \subset \RR}\) jest całkowito-pełny, gdy z każdymi jego dwoma elementami
\(\displaystyle{ a_1,a_2 \in A}\) każda pośrednia liczba całkowita
\(\displaystyle{ b}\) ( tzn. taka liczba całkowita, że:
\(\displaystyle{ a_1<b<a_2}\)) do niego należy.
Czyli zbiór
\(\displaystyle{ A \subset \RR}\) jest całkowito-pełny, gdy wchodząc do środka zbioru, zbiór ten zawiera wszystkie liczby całkowite.
Wykażemy zatem, że jeśli zbiór
\(\displaystyle{ A \subset \RR}\) jest całkowito-pełny, to przekrój
\(\displaystyle{ A \cap \ZZ}\) jest przedziałem w zbiorze liniowo uporządkowanym
\(\displaystyle{ \left( \ZZ, \le\right)}\).
DOWÓD TEGO FAKTU:
Jeśli zbiór
\(\displaystyle{ A}\) jest całkowito-pełny, to aby pokazać, że przekrój
\(\displaystyle{ A \cap \ZZ}\) jest przedziałem w
\(\displaystyle{ \left( \ZZ, \le \right)}\), to niech
\(\displaystyle{ a_1,a_2 \in A \cap \ZZ}\) i niech
\(\displaystyle{ b \in \ZZ}\) będzie taką liczbą całkowitą, że:
\(\displaystyle{ a_1< _{\ZZ} b < _{\ZZ} a_2}\). Pokażemy, że:
\(\displaystyle{ b \in A \cap \ZZ}\).
Mamy:
\(\displaystyle{ a_1,a_2 \in A}\),
\(\displaystyle{ b \in \ZZ}\), i
\(\displaystyle{ A\ni a_1<b<a_2\in A}\), więc ponieważ zbiór
\(\displaystyle{ A}\) jest całkowito-pełny, to wnioskujemy, że:
\(\displaystyle{ b \in A}\), a zatem
\(\displaystyle{ b \in A \cap \ZZ,}\) i zbiór
\(\displaystyle{ A \cap \ZZ}\) jest przedziałem w zbiorze liniowo uporządkowanym
\(\displaystyle{ \left( \ZZ, \le \right).\square}\)