Chciałbym się upewnić, czy ja to dobrze rozumiem.
Ja rozumiem to tak że najpierw mamy zbiór relacji \(\displaystyle{ \alpha}\) o polu \(\displaystyle{ X}\)( oczywiście najpierw zbiór \(\displaystyle{ X}\)), potem zbiór relacji \(\displaystyle{ \alpha \subset \mathcal{P} \left( X \times X\right)}\), a dopiero potem bierzemy relację \(\displaystyle{ R \subset X \times X}\) i rozważamy jej domknięcie w zbiorze relacji \(\displaystyle{ \alpha}\), (czyli relację \(\displaystyle{ S}\) o własnościach \(\displaystyle{ R\subset S}\), \(\displaystyle{ S\in \alpha}\) i najmniejsza taka relacja)
Jeśli na przykład mamy zbiór \(\displaystyle{ \alpha =\left\{ R \subset X\times X \Bigl| \quad R \hbox{ jest symetryczna } \right\}}\), i jeśli sobie narysowałem pewną relację \(\displaystyle{ R}\) to ją domykamy (powiększamy ) tak aby była symetryczna.
Mój niepokój pochodzi stąd, że na ważniaku trochę tak z rozpędu się wyrażają, że tak powiem. Np. piszą że dowolne domknięcie relacji zwrotnej jest zwrotne. I czy to mogę w ten sposób rozumieć, że biorę dowolny zbiór relacji \(\displaystyle{ \alpha \subset \mathcal{P} \left( X \times X\right)}\) i dopiero potem biorę relację \(\displaystyle{ R}\) zwrotną i jej domknięcie w zbiorze relacji \(\displaystyle{ \alpha}\) będzie zwrotne ( no tak bo domknięcie jest większe). Chyba dobrze to rozumiem
Domknięcia relacji
-
- Użytkownik
- Posty: 1423
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 68 razy
- Pomógł: 84 razy
-
- Administrator
- Posty: 34462
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5220 razy
Domknięcia relacji
Nie bardzo rozumiem to rozróżnienie.Jakub Gurak pisze:Ja rozumiem to tak że najpierw mamy zbiór relacji \(\displaystyle{ \alpha}\) o polu \(\displaystyle{ X}\)( oczywiście najpierw zbiór \(\displaystyle{ X}\)), potem zbiór relacji \(\displaystyle{ \alpha \subset \mathcal{P} \left( X \times X\right)}\),
No tak.Jakub Gurak pisze:Jeśli na przykład mamy zbiór \(\displaystyle{ \alpha =\left\{ R \subset X\times X \Bigl| \quad R \hbox{ jest symetryczna } \right\}}\), i jeśli sobie narysowałem pewną relację \(\displaystyle{ R}\) to ją domykamy (powiększamy ) tak aby była symetryczna.
Dla mnie domykanie dotyczy nie tyle zbioru relacji, który oznaczasz \(\displaystyle{ \alpha}\), tylko własności (w tym wypadku relacji), względem której domykamy. To według mnie bardziej naturalne i odpowiada pewnemu ogólnemu schematowi. Dlatego mówimy o przechodnim domknięciu relacji (domknięciu ze względu na przechodniość), symetrycznym domknięciu relacji (domknięciu ze względu na symetrię) czy tranzytywnym domknięciu zbioru (domknięciu ze względu na tranzytywność).Jakub Gurak pisze:Mój niepokój pochodzi stąd, że na ważniaku trochę tak z rozpędu się wyrażają, że tak powiem. Np. piszą że dowolne domknięcie relacji zwrotnej jest zwrotne. I czy to mogę w ten sposób rozumieć, że biorę dowolny zbiór relacji \(\displaystyle{ \alpha \subset \mathcal{P} \left( X \times X\right)}\) i dopiero potem biorę relację \(\displaystyle{ R}\) zwrotną i jej domknięcie w zbiorze relacji \(\displaystyle{ \alpha}\) będzie zwrotne ( no tak bo domknięcie jest większe). Chyba dobrze to rozumiem
Wyrażenie "domknięcie relacji zwrotnej" jest dla mnie bez sensu, bo nie mówimy względem jakiej własności domykamy. Mógłbyś doprecyzować w jakim kontekście to się pojawia?
JK
-
- Użytkownik
- Posty: 1423
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 68 razy
- Pomógł: 84 razy
Domknięcia relacji
Już wszystko rozumiem.
Chodzi tu o to że z dowolną ustaloną własnością relacji ( \(\displaystyle{ \beta(R)}\) ) możemy rozważyć zbiór relacji spełniających tą własność : \(\displaystyle{ \alpha =\left\{ R \subset X \times X \Bigl| \quad \beta (R) \right\}}\)
I teraz jeśli weźmiemy relację \(\displaystyle{ \displaystyle R \subset X\times X}\),
to jej domknięcie \(\displaystyle{ \displaystyle S}\) w zbiorze relacji \(\displaystyle{ \displaystyle \alpha}\) jest to najmniejsza relacja z rodziny \(\displaystyle{ \displaystyle \alpha}\) zawierająca daną
Ponieważ jednak dowolna relacja \(\displaystyle{ \displaystyle T}\) spełnia \(\displaystyle{ \displaystyle T\in\alpha \Longleftrightarrow \beta (T)}\), więc jest to najmniejsza relacja zawierająca daną spełniająca własność \(\displaystyle{ \displaystyle\beta (T)}\), o co chodziło.
Czyli podejście ze zbiorem relacji \(\displaystyle{ \alpha}\) jest uogólnieniem wszelakiego domknięcia relacji, że dla relacji \(\displaystyle{ \displaystyle R}\) domykamy ją ze względu na relacje z rodziniy \(\displaystyle{ \displaystyle\alpha}\)
Według mnie też, to nie mój wymysł. Ale skoro na ważniaku tak to definiowali, to ja się nie wzbraniałem, i zrozumiałem to.Jan Kraszewski pisze:Dla mnie domykanie dotyczy nie tyle zbioru relacji, który oznaczasz alpha, tylko własności (w tym wypadku relacji), względem której domykamy. To według mnie bardziej naturalne
Chodzi tu o to że z dowolną ustaloną własnością relacji ( \(\displaystyle{ \beta(R)}\) ) możemy rozważyć zbiór relacji spełniających tą własność : \(\displaystyle{ \alpha =\left\{ R \subset X \times X \Bigl| \quad \beta (R) \right\}}\)
I teraz jeśli weźmiemy relację \(\displaystyle{ \displaystyle R \subset X\times X}\),
Ukryta treść:
Ponieważ jednak dowolna relacja \(\displaystyle{ \displaystyle T}\) spełnia \(\displaystyle{ \displaystyle T\in\alpha \Longleftrightarrow \beta (T)}\), więc jest to najmniejsza relacja zawierająca daną spełniająca własność \(\displaystyle{ \displaystyle\beta (T)}\), o co chodziło.
Czyli podejście ze zbiorem relacji \(\displaystyle{ \alpha}\) jest uogólnieniem wszelakiego domknięcia relacji, że dla relacji \(\displaystyle{ \displaystyle R}\) domykamy ją ze względu na relacje z rodziniy \(\displaystyle{ \displaystyle\alpha}\)
Domykamy względem dowolnego ustalonego zbioru relacji, o ile się da... Chyba nie potrzebowałem specjalnej pomocy...Jan Kraszewski pisze:Wyrażenie "domknięcie relacji zwrotnej" jest dla mnie bez sensu, bo nie mówimy względem jakiej własności domykamy.
-
- Administrator
- Posty: 34462
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 4 razy
- Pomógł: 5220 razy
Domknięcia relacji
No to podejście ważniakowe jest dla mnie formalistyczno-sztuczne. W dodatku ogranicza definicję do relacji na ustalonym wcześniej zbiorze. Nie bardzo rozumiem sens takiego podejścia czy korzyść z tego wynikającą.
JK
JK
-
- Użytkownik
- Posty: 1423
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 68 razy
- Pomógł: 84 razy
Re: Domknięcia relacji
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}\)
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}\)