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,

$\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 ,

$\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}$ .

$\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$ .