Relacje równoważności

W tym podrozdziale poznamy ważną klasę (zbiór) relacji zwaną klasą relacji równoważności(w innych podręcznikach mogą się państwo spotkać z nazwą relacja abstrakcji). Relacje takie będą służyły do definiowania pojęć abstrakcyjnych, o czym przekonamy się w wielu miejscach tego i innych wykładów. Bardzo dobrym ćwiczeniem pokazującym abstrakcyjne metody definiowania pojęć będzie wykład 8 "Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek", w którym zaprzęgniemy relacje abstrakcji do definiowania liczb.

Rozpoczynamy rozdział od koniecznej definicji.

Definicja 4.1.

Dla zbioru \( \displaystyle X \) definiujemy relację \( \displaystyle 1_X \subset X \times X \) jako \( \displaystyle \{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z \} \).

Definicja 4.2.

Relację \( \displaystyle R \subset X \times X \) nazywamy relacją równoważnością o polu \( \displaystyle X \), jeżeli:

zawiera relacje \( \displaystyle 1_X \) (zwrotność \( \displaystyle R \)),
\( \displaystyle R^{-1} \subset R \) (symetria \( \displaystyle R \)),
\( \displaystyle R \circ R \subset R \) (przechodniość \( \displaystyle R \)).

Ćwiczenie 4.3

Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu \( \displaystyle X \) są odpowiednio równoważne następującym własnościom:

\( \displaystyle \forall_{ x\in X} (x,x) \in R \),
\( \displaystyle \forall_{ x,y \in X} (x,y) \in R arrow (y,x) \in R \),
\( \displaystyle \forall_{ x,y,z\in X} (x,y)\in R \wedge (y,z) \in R arrow (x,z)\in R \).

Rozwiązanie

Ćwiczenie jest elementarne.

Definicja 4.4.

Niech \( \displaystyle R \) będzie relacją równoważności o polu \( \displaystyle X \). Klasą równoważności elementu \( \displaystyle x\in X \) jest zbiór

\( \displaystyle [x]_R := \{y \in X : (x,y) \in R\}. \)

Definicja 4.5.

Zbiór klas równoważności relacji \( \displaystyle R \) będący elementem zbioru \( \displaystyle \mathcal{P} ( \mathcal{P} (X \times X)) \) oznaczamy przez \( \displaystyle X/R \).

Twierdzenie 4.6.

Niech \( \displaystyle R \) będzie relacją równoważności o polu \( \displaystyle X \). Następujące warunki są równoważne:

\( \displaystyle [x]_R \cap [y]_R \neq \emptyset \),
\( \displaystyle [x]_R = [y]_R \),
\( \displaystyle (x,y) \in R \).

Dowód

Pokażemy, że \( \displaystyle (1)arrow (2) \). Niech wspólny element dwóch klas \( \displaystyle [x]_R \) oraz \( \displaystyle [y]_R \) nazywa się \( \displaystyle z \). Ze względu na pełną symetrię tezy wystarczy pokazać, że \( \displaystyle [x]_R \subseteq [y]_R \). Niech zatem \( \displaystyle p\in [x]_R \). Mamy więc \( \displaystyle (x,p) \in R \). Z założenia jest również \( \displaystyle (y,z) \in R \) oraz \( \displaystyle (x,z) \in R \). Z symetrii otrzymujemy \( \displaystyle (z,x) \in R \). Zatem \( \displaystyle (y,z) \in R \) i \( \displaystyle (z,x) \in R \) i \( \displaystyle (x,p) \in R \). Natychmiast z przechodniości otrzymujemy, że \( \displaystyle (y,p) \in R \).
Pokażemy, że \( \displaystyle (2)arrow (3) \). Ze zwrotności mamy, że \( \displaystyle y\in [y]_R \), co z założenia \( \displaystyle (2) \) daje \( \displaystyle y\in [x]_R \), a to tłumaczy się na \( \displaystyle (x,y) \in R \). Pokażemy, że \( \displaystyle (3)arrow (1) \). Wystarczy pokazać, że wspólnym elementem klas \( \displaystyle [x]_R \) oraz \( \displaystyle [y]_R \) jest \( \displaystyle y \). Dla pierwszej z nich wynika to z założenia \( \displaystyle (3) \), a dla drugiej ze zwrotności \( \displaystyle R \).

W następnym twierdzeniu zobaczymy, jak rodzina relacji równoważności jest odporna na przecinanie. Pokażemy mianowicie, że przecięcie dowolnej liczby relacji równoważności jest nadal relacją równoważności.

Twierdzenie 4.7.

Niech \( \displaystyle \kappa \neq \emptyset \) będzie pewną rodziną (zbiorem) relacji równoważności o tym samym polu \( \displaystyle X \). Mamy że:

\( \displaystyle \bigcap \kappa \) jest relacją równoważności o polu \( \displaystyle X \),
\( \displaystyle [x]_{ \bigcap \kappa } = \bigcap \{[x]_R : R\in \kappa\} \).

Dowód
\( \displaystyle (1) \) Zwrotność \( \displaystyle \bigcap \kappa \) jest oczywista, ponieważ \( \displaystyle 1_X \) zawiera się w każdej relacji rodziny \( \displaystyle \kappa \). Symetria. Weźmy \( \displaystyle (x,y)\in \bigcap \kappa \). Dla każdej relacji \( \displaystyle R\in\kappa \) jest \( \displaystyle (x,y)\in R \). Z symetrii każdej \( \displaystyle R \) jest więc \( \displaystyle (y,x)\in R \), co daje \( \displaystyle (y,x)\in \bigcap \kappa \). Przechodniość. Niech \( \displaystyle (x,y)\in \bigcap \kappa \) oraz \( \displaystyle (y,z)\in \bigcap \kappa \). Dla każdej relacji \( \displaystyle R\in\kappa \) jest więc \( \displaystyle (x,y)\in R \) i \( \displaystyle (y,z)\in R \). Z przechodniości każdej relacji \( \displaystyle R \) mamy, że \( \displaystyle (x,z) \in R \), co daje \( \displaystyle (x,z)\in \bigcap \kappa \).
\( \displaystyle (2) \) Niech \( \displaystyle y \in [x]_{ \bigcap \kappa } \). Mamy zatem, że \( \displaystyle (x,y) \in \bigcap \kappa \), co daje \( \displaystyle (x,y)\in R \) dla każdej relacji \( \displaystyle R\in\kappa \). To zaś daje, że \( \displaystyle y \in [x]_R \) dla każdej \( \displaystyle R \in \kappa \), co jest równoważne z \( \displaystyle y\in\bigcap \{[x]_R : R\in \kappa\} \).

W szczególności przecięcie wszystkich relacji równoważności o polu \( \displaystyle X \) daje \( \displaystyle 1_X \). Jest ona najsilniejszą relacją równoważności. Najsłabszą jest \( \displaystyle X^2 \).

Rozkłady zbiorów

Definicja 4.8.

Niech \( \displaystyle X \neq \emptyset \). Rodzinę \( \displaystyle r \in \mathcal{P} ( \mathcal{P} (X)) \) nazywamy rozkładem zbioru \( \displaystyle X \), gdy:

\( \displaystyle \forall_{C \in r} \;\; C \neq \emptyset \),
\( \displaystyle \bigcup r =X \),
\( \displaystyle (C \in r \hspace {0.1mm} \wedge D \in r \hspace {0.1mm} \wedge C \neq D )\hspace {0.1mm} \Rightarrow C\cap D =\emptyset \).

Lemat 4.9.

Dla relacji równoważności \( \displaystyle R \) o polu \( \displaystyle X \) zbiór \( \displaystyle X/R \) jest rozkładem \( \displaystyle X \).

Dowód

\( \displaystyle (1) \) Każda klasa jest niepusta, bo zawiera element, który ją wyznacza. \( \displaystyle (2)\displaystyle \bigcup X/R \subseteq X \), bo każda klasa jest podzbiorem \( \displaystyle X \). Odwrotnie każdy \( \displaystyle x \in [x]_R \in X/R \). \( \displaystyle (3) \) Dwie klasy, gdy są różne, muszą być rozłączne co udowodniliśmy w twierdzeniu 4.6.

Definicja 4.10.

Niech \( \displaystyle r \) będzie rozkładem zbioru \( \displaystyle X \). Definiujemy relacje \( \displaystyle R_r \subset X \times X \) następująco:

\( \displaystyle (x,y) \in R_r \) wtw \( \displaystyle \exists_{C\in r} \;\; x \in C \; \hspace {0.1mm} \wedge \; y\in C. \)

Lemat 4.11.

Dla rozkładu \( \displaystyle r \in \mathcal{P} ( \mathcal{P} (X)) \) relacja \( \displaystyle R_r \) jest:

równoważnością,
\( \displaystyle X/{R_r} = r. \)

Dowód

\( \displaystyle (1) \) Relacja \( \displaystyle R_r \) jest zwrotna, każdy bowiem \( \displaystyle x\in X \) musi leżeć w pewnym zbiorze \( \displaystyle C \) rozkładu \( \displaystyle r \). Symetria \( \displaystyle R_r \) nie wymaga dowodu. Przechodniość \( \displaystyle R_r \). Niech \( \displaystyle (x,y) \in R_r \) i \( \displaystyle (y,z) \in R_r \). Istnieją zatem dwa zbiory \( \displaystyle C \) i \( \displaystyle D \) rozkładu \( \displaystyle r \) takie, że \( \displaystyle x,y \in C \) oraz \( \displaystyle y,z \in D \). Przecięcie \( \displaystyle C \) i \( \displaystyle D \) jest więc niepuste, zatem \( \displaystyle C=D \), co daje tezę \( \displaystyle (x,z) \in R_r \).
\( \displaystyle (2) \) Inkluzja w prawo \( \displaystyle \subseteq \). Niech \( \displaystyle C \in X/{R_r} \). Klasa \( \displaystyle C \) jest zatem wyznaczona przez pewien element \( \displaystyle x \) taki, że \( \displaystyle C= [x]_{R_r} \). Niech \( \displaystyle D\in r \) będzie zbiorem rozkładu \( \displaystyle r \), do którego należy \( \displaystyle x \). Łatwo wykazać, że \( \displaystyle C=D \). Inkluzja w lewo \( \displaystyle \supset \). Niech \( \displaystyle C \in r \). \( \displaystyle C \) jest niepusty, więc istnieje \( \displaystyle x \in C \). Klasa \( \displaystyle [x]_{R_r} =C \).

Ćwiczenie 4.12

Niech \( \displaystyle X \) będzie niepustym zbiorem oraz niech \( \displaystyle Y \subset X \). Zdefiniujemy relację \( \displaystyle R \subset \mathcal{P}(X) \times \mathcal{P}(X) \) następująco: dla dowolnych zbiorów \( \displaystyle A,B \subset X \) mamy

\( \displaystyle (A,B)\in R \Leftrightarrow A\frac{.}{} B \subset Y. \)

(\( \displaystyle A\frac{.}{}B \) oznacza różnicę symetryczną zbiorów, czyli \( \displaystyle A\frac{.}{} B = (A\setminus B)\cup (B \setminus A) \)). Udowodnij, że relacja \( \displaystyle R \) jest relacją równoważności.

Wskazówka

Najtrudniej jest pokazać przechodniość. Udowodnij, że \( \displaystyle A \frac{.}{} C \subset (B\frac{.}{} C) \cup (A\frac{.}{} B) \). Dobrym punktem wyjścia jest naszkicowanie wszystkich przecięć zbiorów \( \displaystyle A,B,C \).

Rozwiązanie

Pokażemy po kolei zwrotność, przechodniość i symetryczność.

Dla każdego \( \displaystyle A\subset X \) mamy \( \displaystyle A\frac{.}{} A= \emptyset \subset Y \), a więc relacja \( \displaystyle R \) jest zwrotna.
Ponieważ dla dowolnych zbiorów \( \displaystyle A\frac{.}{} B= B\frac{.}{} A \), to \( \displaystyle (A,B)\in R \) wtedy i tylko wtedy, gdy \( \displaystyle (B,A)\in R \). Wobec tego relacja \( \displaystyle R \) jest symetryczna.
Weźmy zbiory \( \displaystyle A,B,C \subset X \), takie że \( \displaystyle (A,B), (B,C) \in R \). Wtedy

\( \displaystyle \begin{align*} A \frac{.}{} C= (A\setminus C) \cup (C\setminus A) = \\ (((A\cap B) \cup (A\setminus B))\setminus C) \cup (((C\cap B) \cup (C\setminus B))\setminus A) = \\ ((A\cap B)\setminus C) \cup ((A\setminus B)\setminus C) \cup ((C\cap B)\setminus A) \cup ((C\setminus B)\setminus A) \subset \\ (B\setminus C) \cup (A\setminus B) \cup (B\setminus A) \cup (C\setminus B)= \\ (B\frac{.}{} C) \cup (A\frac{.}{} B). \end{align*} \)

Ponieważ z definicji relacji \( \displaystyle R \) mamy \( \displaystyle (B\frac{.}{} C) \in Y \) oraz \( \displaystyle (A\frac{.}{} B)\in Y \), to ich suma też jest podzbiorem \( \displaystyle Y \) i w konsekwencji również \( \displaystyle A\frac{.}{} C \subset Y \). Oznacza to, że \( \displaystyle (A,C)\in R \), a więc relacja \( \displaystyle R \) jest przechodnia.

Ćwiczenie 4.13

Udowodnij, że dla relacji równoważności \( \displaystyle R,S \) na zbiorze \( \displaystyle X \), relacja \( \displaystyle R\cup S \) jest relacją równoważności wtedy i tylko wtedy, gdy

\( \displaystyle \forall_{x\in X}( [x]_R \subset [x]_S \vee [x]_R \supset [x]_S). \quad \mbox{(4.1)} \)

Podaj przykłady relacji równoważności \( \displaystyle R,S \) takich, że \( \displaystyle R\cup S \) jest relacją równoważności oraz \( \displaystyle R ⊈ S \) i \( \displaystyle S ⊈ R \).

Wskazówka

Przyjrzyj się dokładnie rodzinie zbiorów \( \displaystyle A=\{[x]_R \cup [x]_S : x\in X\} \).

Rozwiązanie

Zaczniemy od pokazania, że formuła 4.1 implikuje, iż relacja \( \displaystyle R\cup S \) jest relacją równoważności. Pokażemy, że rodzina \( \displaystyle A=\{[x]_R \cup [x]_S : x\in X\} \) tworzy rozkład zbioru \( \displaystyle X \). Oczywiście, dla każdego elementu \( \displaystyle x\in X \) mamy \( \displaystyle [x]_R \cup [x]_S \neq \emptyset \) oraz \( \displaystyle x\in [x]_R \cup [x]_S \). Wystarczy więc pokazać, że zbiory w rodzinie \( \displaystyle A \) są rozłączne. Weźmy dowolne dwa elementy rodziny \( \displaystyle A \) i przypuśćmy, że ich przecięcie jest niepuste. Niech to będą zbiory odpowiadające elementom \( \displaystyle x,y\in X \), a więc \( \displaystyle [x]_R \cup [x]_S \) oraz \( \displaystyle [y]_R \cup [y]_S \). Skoro te zbiory mają niepuste przecięcie, to istnieje \( \displaystyle z \in([x]_R \cup [x]_S) \cap([y]_R \cup [y]_S) \). Ponieważ \( \displaystyle z\in [x]_R \cup [x]_S \), to \( \displaystyle z\in [x]_R \vee z \in [x]_S \), co jest równoważne \( \displaystyle x\in [z]_R \vee x \in [z]_S \). Podobne rozumowanie dla \( \displaystyle z \) daje \( \displaystyle y\in [z]_R \vee y \in [z] S \). Wobec czego dostajemy \( \displaystyle x,y \in [z]_R \cup [z]_S \), ponieważ jednak zgodnie z formułą 4.1 jedna z tych klas jest nadzbiorem drugiej, to \( \displaystyle x,y \in [z]_R \) lub \( \displaystyle x,y \in [z]_S \). W przypadku, gdy \( \displaystyle [z]_R\supset [z]_S \), dostajemy również z 4.1. \( \displaystyle [z]_R=[x]_R\supset [x]_S \) oraz \( \displaystyle [z]_R=[y]_R\supset [y]_S \), wobec czego otrzymujemy \( \displaystyle [x]_R \cup [x]_S =[z]_R=[y]_R \cup [y]_S \). Drugi przypadek jest analogiczny. Wobec czego rodzina \( \displaystyle A \) jest rozkładem zbioru \( \displaystyle X \). Wystarczy teraz przekonać się, że \( \displaystyle (a,b)\in R\cup S \) wtedy i tylko wtedy, gdy \( \displaystyle a \in [b]_R \cup [b]_S \), aby udowodnić, że jest to rzeczywiście rozkład generowany przez relację \( \displaystyle R\cup S \). Weźmy dowolne \( \displaystyle a,b \in X \), wtedy

\( \displaystyle \begin{align*} (a,b)\in R\cup S \Leftrightarrow (a,b)\in R \vee (a,b)\in S \Leftrightarrow a\in[b]_R \vee a\in [b]_S \Leftrightarrow a \in [b]_R \cup [b]_S. \end{align*} \) Pokażemy teraz, że jeśli \( \displaystyle R\cup S \) jest relacją równoważności, to musi być spełniona formuła 4.1. Dla dowodu niewprost przypuśćmy, że nie jest spełniona. Oznacza to, że istnieje element \( \displaystyle x\in X \), dla którego \( \displaystyle [x]_R ⊈ [x]_S \) oraz \( \displaystyle [x]_R ⊉ [x]_S \). Wobec tego istnieje \( \displaystyle y\in [x]_R \setminus [x]_S \) oraz \( \displaystyle z \in [x]_S \setminus [x]_R \). Oznacza to, że \( \displaystyle (y,x)\in R\setminus S \) oraz \( \displaystyle (x,z)\in S\setminus R \). Skoro \( \displaystyle R\cup S \) jest relacją równoważności, to \( \displaystyle (z,y) \in R\cup S \). Przypuśćmy, że \( \displaystyle (z,y)\in R \). Wtedy \( \displaystyle (z,y),(y,x)\in R \), wobec czego \( \displaystyle (z,x)\in R \), co jest sprzeczne z tym, że \( \displaystyle (x,z)\in S\setminus R \), ponieważ relacja \( \displaystyle R \) jest symetryczna. Analogiczną sprzeczność otrzymujemy dla \( \displaystyle (z,x)\in S \). Obie możliwości prowadzą do sprzeczności, a więc formuła 4.1 musi być spełniona.

Na koniec podajemy przykład relacji równoważności, równoważności \( \displaystyle R,S \) takich, że \( \displaystyle R\cup S \) jest relacją równoważności oraz \( \displaystyle R ⊈ S \) i \( \displaystyle S ⊈ R \). Polem relacji będzie zbiór \( \displaystyle X=\{0,1,2,3\} \). Relacje \( \displaystyle R,S \) określimy poprzez wyznaczane przez nie rozkłady odpowiednio \( \displaystyle r,s \):

\( \displaystyle \begin{align*} r=\{\{0\},\{1\}, \{2,3\}\} \\ s=\{\{0,1\}, \{2\},\{3\}\}. \end{align*} \)

Łatwo sprawdzić, że \( \displaystyle R ⊈ S \) i \( \displaystyle S ⊈ R \), gdyż \( \displaystyle (2,3)\in R\setminus S \) oraz \( \displaystyle (0,1)\in S\setminus R \). Z rozkładów \( \displaystyle r,s \) w prosty sposób wynika, że formuła 4.1 jest prawdziwa dla tych relacji, wobec czego \( \displaystyle R\cup S \) jest relacją równoważności. Wyznaczany przez nią rozkład to \( \displaystyle \{\{0,1\},\{2,3\}\} \).

Domykanie relacji

W praktyce matematycznej często potrzebne jest rozważanie domknięć relacji ze względu na wiele przeróżnych własności. W podrozdziale tym dokonamy charakteryzacji domknięć. Pokażemy między innymi, kiedy takie domykanie jest możliwe.

Definicja 4.14.

Niech \( \displaystyle \alpha \) będzie rodziną relacji o polu \( \displaystyle X \), czyli niech \( \displaystyle \alpha \in \mathcal{P} ( \mathcal{P} (X^2)) \). Rodzina \( \displaystyle \alpha \) jest zamknięta na przecięcia, gdy:

\( \displaystyle X^2 \in \alpha, \)
jeżeli \( \displaystyle \emptyset \neq \alpha ' \subset \alpha \) to \( \displaystyle \bigcap \alpha ' \in \alpha. \)

Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji. Definiujemy intuicyjnie najmniejszą relację zawierającą daną należącą do klasy.

Definicja 4.15.

Relacja \( \displaystyle S \subset X^2 \) jest domknięciem relacji \( \displaystyle R \subset X^2 \) w klasie (zbiorze) relacji \( \displaystyle \alpha, \) gdy:

\( \displaystyle R \subset S, \)
\( \displaystyle S \in \alpha, \)
dla każdej relacji \( \displaystyle T \) jeżeli \( \displaystyle R \subset T \) oraz \( \displaystyle T \in \alpha \) to \( \displaystyle S \subset T. \)

Lemat 4.16.

Domknięcie relacji (w dowolnej klasie), jeżeli istnieje, to jest jedyne.

Dowód

Gdyby istniały dwa domknięcia pewnej relacji, to ze względu na warunek \( \displaystyle (3) \) wzajemnie by się zawierały.

Twierdzenie 4.17.

Następujące warunki są równoważne:

Klasa relacji \( \displaystyle \alpha \) jest domknięta na przecięcia.
Każda relacja ma domknięcie w klasie relacji \( \displaystyle \alpha \).

Dowód

\( \displaystyle (1) arrow (2) \). Niech \( \displaystyle R \) będzie relacją. Utwórzmy zbiór relacji \( \displaystyle \alpha ' \) jako \( \displaystyle \{S\in\mathcal{P} (X^2) : R\subset S \hspace {0.1mm} \wedge S\in\alpha \} \). Takie \( \displaystyle \alpha ' \) nie jest puste, bowiem relacja totalna \( \displaystyle X^2 \) należy do \( \displaystyle \alpha ' \). Pokażmy, że \( \displaystyle \bigcap \alpha ' \) jest domknięciem \( \displaystyle R \) w \( \displaystyle \alpha \). Istotnie \( \displaystyle R\subset \bigcap \alpha ' \). Z założenia mamy też \( \displaystyle \bigcap \alpha ' \in \alpha \). Minimalność \( \displaystyle \bigcap \alpha ' \) stwierdzamy przez: niech \( \displaystyle R \subset S' \) takie że \( \displaystyle S' \in \alpha \). Takie \( \displaystyle S' \) musi leżeć w zbiorze \( \displaystyle \alpha ' \), jest więc \( \displaystyle \bigcap \alpha ' \subset S' \).
\( \displaystyle (2) arrow (1) \). Po pierwsze \( \displaystyle X^2 \) leży w zbiorze \( \displaystyle \alpha \), bo wystarczy domknąć \( \displaystyle X^2 \). Niech \( \displaystyle \alpha ' \) będzie niepustym podzbiorem \( \displaystyle \alpha \). Niech \( \displaystyle S_0 \) będzie domknięciem \( \displaystyle \bigcap \alpha ' \) w \( \displaystyle \alpha \). Wiemy, że dla dowolnej relacji \( \displaystyle S' \), o ile \( \displaystyle \bigcap \alpha ' \subset S' \) i \( \displaystyle S'\in \alpha \) to \( \displaystyle S_0 \subset S' \). Połóżmy za \( \displaystyle S' \) dowolny element z \( \displaystyle \alpha ' \). Założenia implikacji pozostają automatycznie spełnione, jest więc tak, że \( \displaystyle S_0 \subset S' \) dla dowolnej \( \displaystyle S' \) wyjętej z \( \displaystyle \alpha ' \). W takim razie \( \displaystyle S_0 \subset \bigcap \alpha ' \). Ponieważ mamy też \( \displaystyle \bigcap \alpha '\subset S_0 \), bo \( \displaystyle S_0 \) było domknięciem, jest więc \( \displaystyle \bigcap \alpha '= S_0 \), a to oznacza, że \( \displaystyle S_0 \in \alpha \).

Ćwiczenie 4.18

Pokazać jak wyglądają domknięcia w klasie relacji, zwrotnych, symetrycznych i przechodnich.

Pokazać, stosując twierdzenie 4.17, że nie istnieje domknięcie spójne ani antysymetryczne. (Relacja \( \displaystyle R \) jest spójna, gdy \( \displaystyle \forall x,y (x,y) \in R \hspace {0.1mm} \vee (y,x)\in R \). Relacja \( \displaystyle R \) jest antysymetryczna, gdy z faktu, że \( \displaystyle (x,y) \in R \) oraz \( \displaystyle (y,x) \in R \), da się pokazać, że \( \displaystyle x=y \)).

Rozwiązanie

1. Pokażemy, że dla każdej relacji \( \displaystyle R\in X^2 \) jej domknięcie w klasie relacji zwrotnych na \( \displaystyle X \) to \( \displaystyle R\cup 1_X \). Pokażemy po kolei, że spełnia warunki domknięcia:

(a) \( \displaystyle R \subset R \cup 1_X, \)

(b) \( \displaystyle 1_X \subset R \cup 1_X \), a więc jest zwrotna,

(c) weźmy dowolną zwrotną relację \( \displaystyle T\supset R \). Ponieważ \( \displaystyle T \) jest zwrotna to \( \displaystyle T\supset 1_X \), a więc \( \displaystyle T\supset R \cup 1_X \).

2. Pokażemy, że dla każdej relacji \( \displaystyle R\in X^2 \) jej domknięcie w klasie relacji symetrycznych na \( \displaystyle X \) to \( \displaystyle R\cup R^{-1} \). Pokażemy po kolei, że spełnia warunki domknięcia:

(a) \( \displaystyle R \subset R \cup R^{-1}, \)

(b) \( \displaystyle (R \cup R^{-1})^{-1} = R^{-1} \cup (R^{-1})^{-1}= R^{-1} \cup R= R \cup R^{-1} \), a więc jest symetryczna ,

(c) weźmy dowolną symetryczną relację \( \displaystyle T\supset R \). Ponieważ \( \displaystyle T \) jest symetryczna to \( \displaystyle T \supset T^{-1} \). Skoro \( \displaystyle T \supset R \) to \( \displaystyle T^{-1} \supset R^{-1} \). Ponieważ \( \displaystyle T \supset T^{-1} \), to \( \displaystyle T\supset R\cup R^{-1} \).

3 Posługując się intuicyjnym pojęciem liczb naturalnych, przedstawimy szkic konstrukcji przechodniego domknięcia, pomimo że konstrukcja ta wyprzedza prezentowany materiał. Dla dowolnej liczby \( \displaystyle n\in N \setminus\{0\} \) przez \( \displaystyle R^n \) będziemy oznaczać \( \displaystyle n \)-krotne złożenie relacji \( \displaystyle R \) z sobą (czyli \( \displaystyle R^1=R \) oraz \( \displaystyle R^{n+1}= R^n \circ R \) dla \( \displaystyle n>1 \)). Zdefiniujmy rodzinę \( \displaystyle \mathcal{R} \) jako zbiór wszystkich skończonych wielokrotnych złożeń relacji \( \displaystyle R \) z sobą, czyli \( \displaystyle \mathcal{R}=\{r\subset X^2 : \exists_{n\in N} (n\neq 0 \wedge R^n=r)\} \). Do formalnego zdefiniowania rodziny \( \displaystyle \mathcal{R} \) potrzebne są pojęcia liczb naturalnych, funkcji oraz definiowania przez indukcje, które zostaną przedstawione w następnych rozdziałach. Pokażemy teraz, że domknięcie relacji \( \displaystyle R \) w klasie relacji przechodnich na \( \displaystyle X \) to relacja \( \displaystyle \bigcup \mathcal{R} \). Pokażemy po kolei, że spełnia warunki domknięcia:

(a) \( \displaystyle R=R^1 \subset \bigcup \mathcal{R}, \)

(b) Aby pokazać, że relacja \( \displaystyle \bigcup \mathcal{R} \) jest przechodnia, weźmy dowolne dwie pary \( \displaystyle (a,b),(b,c) \in \mathcal{R} \). Wtedy muszą istnieć liczby \( \displaystyle n,m \in N \) takie, że \( \displaystyle (a,b)\in R^n \) oraz \( \displaystyle (b,c)\in R^m \). Wobec tego \( \displaystyle (a,c)\in R^m \circ R^n \). Z łączności składania relacji wynika, że \( \displaystyle R^m \circ R^n= R^{m+n} \). Wobec tego \( \displaystyle (a,c)\in R^{m+n} \subset \bigcup \mathcal{R} \).

(c) Weźmy dowolną przechodnią relację \( \displaystyle T \) taką, że \( \displaystyle R\subset T \), pokażemy indukcyjnie, że dla każdego \( \displaystyle n\in N\setminus \{0\} \) mamy \( \displaystyle R^n\subset T \).

i. Baza indukcji. Dla \( \displaystyle n=1 \) mamy \( \displaystyle R^1=R \), a więc z założenia \( \displaystyle R^1\subset T \).

ii. Krok indukcyjny. Weźmy dowolne \( \displaystyle n\in N\setminus \{0,1\} \) i przypuśćmy, że dla każdego \( \displaystyle 0 < m < n \) zachodzi \( \displaystyle R^m\subset T \). Weźmy dowolną parę \( \displaystyle (a,c)\in R^n \). Ponieważ \( \displaystyle n>1 \), to \( \displaystyle R^n= R^{n-1} \circ R \). Oznacza to, że istnieje element \( \displaystyle b\in X \) taki, że \( \displaystyle (a,b)\in R \) oraz \( \displaystyle (b,c)\in R^{n-1} \). Z założenia indukcyjnego wynika, że \( \displaystyle (a,b)\in T \) oraz \( \displaystyle (b,c)\in T \). Ponieważ \( \displaystyle T \) jest przechodnia to \( \displaystyle (a,c)\in T \). Wobec dowolności wyboru pary \( \displaystyle (a,c) \) otrzymujemy \( \displaystyle R^n \subset T \).

Skoro dla każdego \( \displaystyle n\in N\setminus \{0\} \) mamy \( \displaystyle R^n \subset T \), to również \( \displaystyle \bigcup \mathcal{R} \subset T \).

Pokażemy teraz, że istnieje zbiór \( \displaystyle X \) taki, że klasa relacji spójnych na zbiorze \( \displaystyle X \) i klasa relacji symetrycznych na zbiorze \( \displaystyle X \) nie są domknięte na przecięcia. W obliczu Twierdzenia 4.17 będzie to oznaczało, że nie wszystkie relacje mają domknięcia w tych klasach. Niech \( \displaystyle X=\{0,1\} \).

Relacje \( \displaystyle \{(0,1),(0,0),(1,1)\}, \{(1,0),(0,0),(1,1)\} \) są spójne na \( \displaystyle X \), a ich przecięcie, czyli zbiór \( \displaystyle \{(0,0),(1,1)\} \), nie jest.
Relacja \( \displaystyle X^2 \) nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na \( \displaystyle X \) nie jest domknięta na przecięcia.

Ćwiczenie 4.19

Dla relacji \( \displaystyle R \) niech \( \displaystyle R^\alpha \), \( \displaystyle R^\beta \), \( \displaystyle R^\gamma \) oznaczają odpowiednio zwrotne, symetryczne, przechodnie domknięcie relacji \( \displaystyle R \). Czy prawdą jest, że:

dla dowolnej relacji \( \displaystyle R \) relacja \( \displaystyle ((R^\alpha)^\beta)^\gamma \) jest relacją równoważności,
dla dowolnej relacji \( \displaystyle R \) zachodzi

\( \displaystyle ((R^\alpha)^\beta)^\gamma =((R^\gamma)^\beta)^\alpha. \)

W każdym z powyższych przypadków proszę podać dowód lub kontrprzykład.

Rozwiązanie

1. Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze \( \displaystyle X \). Z definicji zwrotności mamy, \( \displaystyle R \) jest zwrotna wtedy i tylko wtedy gdy \( \displaystyle R\supset 1_X \). W definicji domknięcia 4.15 punkt pierwszy mówi, że jeśli \( \displaystyle S \) jest domknięciem to \( \displaystyle S\supset R \). Wobec tego konieczne jest, aby \( \displaystyle S\supset 1_X \). Zwróćmy uwagę, że powyższy argument działa dla dowolnych klas rodzin relacji domkniętych na przecięcia. Stąd otrzymujemy, że symetryczne domknięcie relacji zwrotnej jest zwrotne, i przechodnie domknięcie relacji zwrotnej jest zwrotne. Ponieważ relacja \( \displaystyle R^\alpha \) jest zwrotna, to również zwrotna musi być \( \displaystyle ((R^\alpha)^\beta)^\gamma \). Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia 4.18. Można łatwo pokazać indukcyjnie, że dla dowolnego \( \displaystyle n\in N \setminus\{0\} \) mamy \( \displaystyle (R^n)^{-1}=(R^{-1})^n \). Dla relacji symetrycznych dostajemy więc \( \displaystyle (R^n)^{-1}=R^n \). Wobec tego mamy:

\( \displaystyle (\bigcup\{R^n:n\in N \setminus \{0\}\})^{-1} = \bigcup\{(R^n)^{-1}:n\in N \setminus \{0\}\}= \bigcup\{R^n:n\in N \setminus \{0\}\}, \)

a więc przechodnie domknięcie relacji symetrycznej jest symetryczne. Oznacza to, że relacja \( \displaystyle ((R^\alpha)^\beta)^\gamma \) jest symetryczna. Wcześniej pokazaliśmy, że jest zwrotna. Ponieważ jest przechodnim domknięciem, to jest też przechodnia. Wobec tego jest relacją równoważności. 2. Pokażemy relację \( \displaystyle R \), dla której relacja \( \displaystyle ((R^\gamma)^\beta)^\alpha \) nie jest przechodnia. Ponieważ relacja \( \displaystyle ((R^\alpha)^\beta)^\gamma \) jest przechodnia, będzie to oznaczało, że te relacje są różne. Niech \( \displaystyle X=\{0,1,2\} \) oraz \( \displaystyle R=\{(0,2),(1,2)\} \). Relacja \( \displaystyle R \) jest przechodnia, więc \( \displaystyle R^\gamma=R \); jej symetryczne domknięcie to \( \displaystyle (R^\gamma)^\beta=\{(0,2),(2,0),(1,2),(2,1)\} \). I po zwrotnym domknięciu otrzymujemy \( \displaystyle ((R^\gamma)^\beta)^\alpha=\{(0,2),(2,0),(1,2),(2,1),(0,0),(1,1),(2,2)\} \). Łatwo zauważyć, że otrzymana relacja nie jest przechodnia, gdyż \( \displaystyle (0,2),(2,1)\in ((R^\gamma)^\beta)^\alpha \), podczas gdy \( \displaystyle (0,1)\notin ((R^\gamma)^\beta)^\alpha \).