Matematyka.pl

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

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)}\),

Nie bardzo rozumiem to rozróżnienie.

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.

No tak.

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

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ść).

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

Już wszystko rozumiem.

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

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.

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}\)

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.

Domykamy względem dowolnego ustalonego zbioru relacji, o ile się da... Chyba nie potrzebowałem specjalnej pomocy...

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

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}\)