Logika i teoria mnogości/Wykład 5: Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów

Para uporządkowana

Bardzo często będziemy chcieli mieć do czynienia ze zbiorem, który niesie w sobie informację o dwóch innych zbiorach, informację tak trafnie zakodowaną, aby można było odzyskać z niej każdą z jego składowych. Do tego celu wprowadzimy zbiór nazywany parą uporządkowaną dwóch innych zbiorów.

Definicja 1.1.

Niech $x$ oraz $y$ będą zbiorami. Przez parę uporządkowaną $(x,y)$ rozumiemy zbiór

$\{\left\{x\right\},\{x,y\}\}$

Parę uporządkowaną można zdefiniować inaczej na wiele sposobów. Chodzi jednak o to, aby ze zbioru, który jest parą, można było odzyskać jednoznacznie każdą z jego składowych. Tak więc moglibyśmy zaakceptować każdą inną inną definicję pod warunkiem, że będzie spełnione następujące twierdzenie:

Twierdzenie 1.2.

Dla dowolnych zbiorów $a,b,c,d$ zachodzi:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b) = (c,d) \Leftrightarrow a=c \hspace*{0.1mm} \wedge b= d}

Dowód

Dowód przeprowadzimy tylko ze strony lewej do prawej, bo w odwrotnym kierunku jest to fakt oczywisty. Niech zatem dwie pary $(a,b)$ i $(c,d)$ będą równe. Ponieważ $\left\{a\right\}\in (a,b)$, więc $\left\{a\right\}\in (c,d)$. Mamy zatem $\left\{a\right\}=\left\{c\right\}$ lub $\left\{a\right\}=\{c,d\}$. W pierwszym przypadku $a=c$, ale w drugim również jest tak, mamy bowiem, że $c\in \left\{a\right\}$. Pierwszą część twierdzenia mamy za sobą, bo już wiemy, że pierwsze współrzędne równych par są równe.

$(a,b)=(a,d).$

Następnie przeprowadzamy dowód przez przypadki. Jeżeli jest tak, że $a=b$, to $(a,b)=\left\{\left\{a\right\}\right\}$. Zatem $\left\{\left\{a\right\}\right\}=\{\left\{a\right\},\{a,d\}\}$, co daje, że $\{a,d\}=\left\{a\right\}$, a zatem $d=a$. W przeciwnym przypadku, gdy $a\ne b$ mamy, że $\{a,b\}\in \{\left\{a\right\},\{a,d\}\}$. Daje to dwie możliwości albo $\{a,b\}=\left\{a\right\}$, co nie może mieć miejsca, bo mielibyśmy, że $a=b$ albo zaś $\{a,b\}=\{a,d\}$. To drugie prowadzi do naszej tezy $b=d$.

Ćwiczenie 1.3

Dla każdej pary $x=(a,b)$ udowodnij, że

$\bigcap \bigcap x=a.$

Rozwiązanie

Rozważymy dwa przypadki.

1. Jeśli $a=b$, to $x=\{\{a\}\}$ i wtedy $\bigcap \bigcap x=a$.
2. Jeśli $a\ne b$, to $x=\{\{a\},\{a,b\}\}$ a więc

$\bigcap x=\bigcap \{\{a\},\{a,b\}\}=\{a\}\cap \{a,b\}=\{a\},$

skąd otrzymujemy

$\bigcap \bigcap x=a.$

Ćwiczenie 1.4

Udowodnij, że dla dowolnej pary uporządkowanej $x$ zbiór

$\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))$

jest pusty, gdy współrzędne par są różne, a w przeciwnym przypadku jest zbiorem jednoelementowym zawierającym współrzędną pary $x$.

Rozwiązanie

Jeśli $x$ jest parą, to istnieją zbiory $a,b$ takie, że $x=(a,b)$. 1. Przypuśćmy, że $a\ne b$. Wtedy $x=\{\{a\},\{a,b\}\}$ i ${𝒫}(x)=\{\mathrm{\varnothing },\{\{a\}\},\{\{a,b\}\},x\}$. Ponieważ ${𝒫}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$ to ${𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })=\{\{\{a\}\},\{\{a,b\}\},x\}$, a wtedy

$\bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing },$

gdyż przecinany zbiór zawiera elementy rozłączne $\{\{a\}\},\{\{a,b\}\}$. Wobec tego również

$\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing }.$

2. W przypadku, gdy $a=b$, otrzymujemy $x=\{\{a\}\}$, a więc ${𝒫}(x)=\{\mathrm{\varnothing },\{\{a\}\}\}$ i wtedy ${𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })=\{\{\{a\}\}\}$ skąd otrzymujemy

$\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\{a\}.$

Ćwiczenie 1.5

{{{3}}}

Rozwiązanie

Rozważmy najpierw przypadek, gdy para ma różne elementy. Zobaczymy, że dla każdej takiej pary $x=(a,b)$, mamy

$\bigcup (\bigcup x\setminus \bigcap x)=b.\text{(1.1)}$

Ponieważ $a\ne b$, to $x=\{\{a\},\{a,b\}\}$ i wtedy

$\bigcup (\bigcup x\setminus \bigcap x)=\bigcup (\{a,b\}\setminus \{a\})=\bigcup \{b\}=b.$

Zobaczmy teraz, jak proponowany wzór działa na parach o równych współrzędnych. Jeśli $x=(a,a)$, to $x=\{\{a\}\}$ i wtedy

$\bigcup (\bigcup x\setminus \bigcap x)=\bigcup (\{a\}\setminus \{a\})=\bigcup \mathrm{\varnothing }=\mathrm{\varnothing }.$

Musimy więc jeszcze trochę popracować. Wykorzystajmy ćwiczenie 1.4 (patrz ćwiczenie 1.4), niech nowy wzór będzie postaci

$\bigcup (\bigcup x\setminus \bigcap x)\cup \bigcap \bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })).$

Dla par o różnych elementach dodana część wzoru jest zbiorem pustym, więc ta sytuacja jest analogiczna do 1.1, skąd otrzymujemy, że tak zdefiniowany zbiór jest równy $b$.

Dla par o równych elementach pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu 1.4 (patrz ćwiczenie 1.4) pokazaliśmy, że w takim przypadku mamy $\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\{b\}$, jeśli $b$ jest współrzędną pary $x$. Wobec tego

$\bigcup (\bigcup x\setminus \bigcap x)\cup \bigcap \bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing }\cup \bigcap \{b\}=b.$

Iloczyn kartezjański

Zanim wprowadzimy definicję zbioru wszystkich par uporządkowanych elementów dwóch zbiorów (zwanego dalej iloczynem kartezjańskim), należy nam się krótkie wprowadzenie. Otóż niech $x\in X$ oraz $y\in Y$. Łatwo zauważyć, że zarówno $\{x,y\}$, jak i $\left\{x\right\}$ są podzbiorami $X\cup Y$. Zatem $\{x,y\}\in {𝒫}(X\cup Y)$ oraz $\left\{x\right\}\in {𝒫}(X\cup Y)$. Więc $\{\left\{x\right\},\{x,y\}\}\subseteq {𝒫}(X\cup Y)$, co daje, że $(x,y)\in {𝒫}({𝒫}(X\cup Y))$.

Istnienie i konstrukcja iloczynu kartezjańskiego zostało dokładnie omówione w dodatkowym rozdziale "Iloczyn kartezjański i aksjomat wyróżniania" . Proponuję przestudiowanie dodatkowego rozdziału dopiero po zapoznaniu się z rozdziałami wcześniejszymi, pomimo braku precyzji w następnej definicji.

Definicja 2.1.

Niech $x,y$ będą zbiorami. Iloczynem kartezjańskim (produktem) $x\times y$ nazywamy zbiór

$\{z\in {𝒫}({𝒫}(x\cup y)):{\mathrm{\exists }}_{a\in x}{\mathrm{\exists }}_{b\in y}(a,b)=z\}.$

Będziemy używać specjalnej notacji $x^2$ na zbiór $x\times x$.

Ćwiczenie 2.2

Pokaż następujące elementarne własności iloczynu kartezjańskiego:

$\begin{array}{rl}x\times \mathrm{\varnothing }& =\mathrm{\varnothing }\text{(2.1)}\\ x\times (y\cup z)& =(x\times y)\cup (x\times z)\text{(2.2)}\\ x\times (y\cap z)& =(x\times y)\cap (x\times z)\text{(2.3)}\\ x\times (y\setminus z)& =(x\times y)\setminus (x\times z)\text{(2.4)}\end{array}$

Rozwiązanie

Z definicji iloczynu kartezjańskiego oraz twierdzenia 1.2 (patrz twierdzenie 1.2.) w sposób oczywisty wynika następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów $a,b,x,y$ zachodzi

$(a,b)\in x\times y\iff (a\in x\wedge b\in y).$

1.

$\begin{array}{r}x\times \mathrm{\varnothing }=\\ \{z\in {𝒫}({𝒫}(x\cup z)):{\mathrm{\exists }}_{a\in x}{\mathrm{\exists }}_{b\in \mathrm{\varnothing }}(a,b)=z\}=\\ \{z\in {𝒫}({𝒫}(x\cup z)):{\mathrm{\exists }}_{a\in x}{\mathrm{\exists }}_b[(b\in \mathrm{\varnothing })\wedge (a,b)=z]\}\end{array}$

Ponieważ $b\in \mathrm{\varnothing }$ jest zawsze fałszem, to powyższy zbiór jest pusty.

2. Ponieważ obydwa zbiory są zbiorami par, więc wykażemy, że dowolna para należy do jednego wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę $(a,b)$, wtedy

$\begin{array}{r}(a,b)\in x\times (y\cup z)\iff \\ a\in x\wedge b\in (y\cup z)\iff \\ a\in x\wedge (b\in y\vee b\in z)\iff \\ (a\in x\wedge b\in y)\vee (a\in x\wedge b\in z)\iff \\ (a,b)\in x\times y\vee (a,b)\in x\times z\iff \\ (a,b)\in x\times y\cup x\times z.\end{array}$

3. Analogicznie do poprzedniego punktu, weźmy dowolną parę $(a,b)$, wtedy

$\begin{array}{r}(a,b)\in x\times (y\cap z)\iff \\ a\in x\wedge b\in (y\cap z)\iff \\ a\in x\wedge (b\in y\wedge b\in z)\iff \\ (a\in x\wedge b\in y)\wedge (a\in x\wedge b\in z)\iff \\ (a,b)\in x\times y\wedge (a,b)\in x\times z\iff \\ (a,b)\in x\times y\cap x\times z.\end{array}$

4. Analogicznie do poprzednich punktów, weźmy dowolną parę $(a,b)$, wtedy

$\begin{array}{r}(a,b)\in (x\times y)\setminus (x\times z)\iff \\ a\in x\wedge b\in y\wedge \mathrm{\neg }(a\in x\wedge b\in z)\iff \\ b\in y\wedge (a\in x\wedge (a\notin x\vee b\notin z))\iff \\ b\in y\wedge [(a\in x\wedge a\notin x)\vee (a\in x\wedge b\notin z)]\iff \\ b\in y\wedge (a\in x\wedge b\notin z)\iff \\ a\in x\wedge (b\in y\setminus z)\iff \\ (a,b)\in x\times (y\setminus z).\end{array}$

Ćwiczenie 2.3

Produkt kartezjański $\times$ jest monotoniczny ze względu na każdą współrzędną osobno, to znaczy:

Parser nie mógł rozpoznać (nieznana funkcja „\begin{align}”): {\displaystyle \displaystyle \begin{align} x \subset y & \hspace*{0.1mm} \Rightarrow & (x \times z) \subset (y \times z) \quad \mbox{(2.5)}\\ x \subset y & \hspace*{0.1mm} \Rightarrow & (z \times x) \subset (z \times y) \quad \mbox{(2.6)} \end{align}}

Rozwiązanie

1. Niech $x,y$ będą dowolnymi zbiorami takimi, że $x\subset y$. Wtedy dla dowolnej pary $(a,b)$ mamy

$\begin{array}{r}(a,b)\in x\times z\iff \\ a\in x\wedge b\in z\Rightarrow \\ a\in y\wedge b\in z\iff \\ (a,b)\in y\times z.\end{array}$

Stąd $(x\times z)\subset (y\times z)$.

1. Dla dowolnych zbiorów $x\subset y$ mamy $x\cup y=y$. Z poprzedniego

ćwiczenia otrzymujemy

$z\times y=z\times (x\cup y)=(z\times x)\cup (z\times y)\supset (z\times x).$

(Metoda z poprzedniego punktu podziała równie dobrze.)

Ćwiczenie 2.4

Sprawdź, czy dla dowolnych zbiorów $A,B,C$, prawdziwa jest następująca implikacja:

$A\times B=A\times C\Rightarrow B=C$

Rozwiązanie

Nie. Na przykład, gdy $A=\mathrm{\varnothing }$, to dla dowolnych zbiorów $B,C$ mamy

$\mathrm{\varnothing }\times B=\mathrm{\varnothing }=\mathrm{\varnothing }\times C.$

Biorąc różne zbiory $B,C$, otrzymamy kontrprzykład dla badanej implikacji.

Relacje

Definicja 3.1.

Relacją nazywamy każdy podzbiór iloczynu $x\times y$.

Operacje na relacjach:

Definicja 3.2.

Niech $R\subset A\times B$ oraz $S\subset B\times C$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle S \circ R  := \left\{(x,z)\in A \times C : \exists_{y\in B} (x,y)\in R \hspace*{0.1mm} \wedge (y,z)\in S \right\}}

$R^{-1}:=\{(y,x)\in B\times A:(x,y)\in R\}$
$R_L:=\{x\in A:{\mathrm{\exists }}_{y\in B}(x,y)\in R\}$
$R_P:=\{y\in B:{\mathrm{\exists }}_{x\in A}(x,y)\in R\}$

Ćwiczenie 3.3

Niech relacja $R\subset A\times B,S\subset B\times C$ oraz $T\subset C\times D$. Pokazać elementarne własności operacji na relacjach:

$\begin{array}{rll}T\circ (S\circ R)& =& (T\circ S)\circ R\text{(3.1)}\\ (S\circ R{)}^{-1}& =& R^{-1}\circ S^{-1}\text{(3.2)}\\ R& \subset & R_L\times R_P\text{(3.3)}\\ (S\circ R{)}_L& \subset & R_L\text{(3.4)}\\ (S\circ R{)}_P& \subset & S_P\text{(3.5)}\\ (R^{-1}{)}_L& =& R_P\text{(3.6)}\end{array}$

Rozwiązanie

1.

$\begin{array}{r}(x,z)\in T\circ (S\circ R)\iff \\ {\mathrm{\exists }}_u[(x,u)\in (S\circ R)\wedge (u,z)\in T]\iff \\ {\mathrm{\exists }}_u[{\mathrm{\exists }}_v((x,v)\in R\wedge (v,u)\in S)\wedge (u,z)\in T]\iff \\ {\mathrm{\exists }}_u{\mathrm{\exists }}_v[(x,v)\in R\wedge (v,u)\in S\wedge (u,z)\in T]\iff \\ {\mathrm{\exists }}_v{\mathrm{\exists }}_u[(x,v)\in R\wedge ((v,u)\in S\wedge (u,z)\in T)]\iff \\ {\mathrm{\exists }}_v[(x,v)\in R\wedge {\mathrm{\exists }}_u((v,u)\in S\wedge (u,z)\in T)]\iff \\ {\mathrm{\exists }}_v[(x,v)\in R\wedge (v,z)\in T\circ S]\iff \\ (x,z)\in (T\circ S)\circ R\\ \end{array}$

2.

$\begin{array}{r}(x,z)\in (S\circ R{)}^{-1}\iff \\ (z,x)\in S\circ R\iff \\ {\mathrm{\exists }}_y[(z,y)\in R\wedge (y,x)\in S]\iff \\ {\mathrm{\exists }}_y[(y,z)\in R^{-1}\wedge (x,y)\in S^{-1}]\iff \\ (x,z)\in R^{-1}\circ S^{-1}\\ \end{array}$

3.

$\begin{array}{r}(x,z)\in R\Rightarrow \\ {\mathrm{\exists }}_y(x,u)\in R\wedge {\mathrm{\exists }}_v(v,y)\in R\iff \\ x\in R_L\wedge y\in R_P\iff \\ (x,y)\in R_L\times R_P\end{array}$

4.

$\begin{array}{r}x\in (S\circ R{)}_L\iff \\ {\mathrm{\exists }}_z(x,z)\in S\circ R\iff \\ {\mathrm{\exists }}_z{\mathrm{\exists }}_y[(x,y)\in R\wedge (y,z)\in S]\Rightarrow \\ {\mathrm{\exists }}_z{\mathrm{\exists }}_y(x,y)\in R\iff \\ {\mathrm{\exists }}_y(x,y)\in R\iff \\ x\in R_L\end{array}$

5. Dowód $(S\circ R{)}_P\subset S_P$ jest analogiczny do poprzedniego.

6.

$\begin{array}{r}x\in (R^{-1}{)}_L\iff \\ {\mathrm{\exists }}_y(x,y)\in R^{-1}\iff \\ {\mathrm{\exists }}_y(y,x)\in R\iff \\ x\in R_P\end{array}$

Ćwiczenie 3.4

Niech relacja $R\subset B\times C,S\subset B\times C$ oraz $T\subset A\times B$. Pokaż własności:

$\begin{array}{rll}(R\cup S{)}^{-1}& =& R^{-1}\cup S^{-1}\text{(3.7)}\\ (R\cap S{)}^{-1}& =& R^{-1}\cap S^{-1}\text{(3.8)}\\ (R^{-1}{)}^{-1}& =& R\text{(3.9)}\\ (R\cup S)\circ T& =& (R\circ T)\cup (S\circ T)\text{(3.10)}\\ (R\cap S)\circ T& \subset & (R\circ T)\cap (S\circ T)\text{(3.11)}\end{array}$

Rozwiązanie

W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej stronie odpowiedniej równości wtedy i tylko wtedy, gdy należy do prawej. W punkcie 5, pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić inkluzję.

1.

$\begin{array}{r}(x,y)\in (R\cup S{)}^{-1}\iff \\ (y,x)\in (R\cup S)\iff \\ (y,x)\in R\vee (y,x)\in S\iff \\ (x,y)\in R^{-1}\vee (x,y)\in S^{-1}\iff \\ (x,y)\in R^{-1}\cup S^{-1}\end{array}$

2. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć $\cap$ w miejsce $\cup$ oraz $\wedge$ w miejsce $\vee$.

3.

$\begin{array}{r}(x,y)\in (R^{-1}{)}^{-1}\iff \\ (y,x)\in R^{-1}\iff \\ (x,y)\in R\end{array}$

4.

$\begin{array}{r}(x,z)\in (R\cup S)\circ T\iff \\ {\mathrm{\exists }}_y[(x,y)\in T\wedge (y,z)\in (R\cup S)]\iff \\ {\mathrm{\exists }}_y[(x,y)\in T\wedge ((y,z)\in R\vee (y,z)\in S))]\iff \\ {\mathrm{\exists }}_y[((x,y)\in T\wedge (y,z)\in R)\vee ((x,y)\in T\wedge (y,z)\in S))]\iff \\ [{\mathrm{\exists }}_y((x,y)\in T\wedge (y,z)\in R)]\vee [{\mathrm{\exists }}_y((x,y)\in T\wedge (y,z)\in S)]\iff \\ (x,z)\in (R\circ T)\vee (x,z)\in (S\circ T)\iff \\ (x,z)\in (R\circ T)\cup (S\circ T)\end{array}$

5.

$\begin{array}{r}(x,z)\in (R\cap S)\circ T\iff \\ {\mathrm{\exists }}_y[(x,y)\in T\wedge (y,z)\in (R\cap S)]\iff \\ {\mathrm{\exists }}_y[(x,y)\in T\wedge ((y,z)\in R\wedge (y,z)\in S))]\iff \\ {\mathrm{\exists }}_y[((x,y)\in T\wedge (y,z)\in R)\wedge ((x,y)\in T\wedge (y,z)\in S))]\Rightarrow \\ [{\mathrm{\exists }}_y((x,y)\in T\wedge (y,z)\in R)]\wedge [{\mathrm{\exists }}_y((x,y)\in T\wedge (y,z)\in S)]\iff \\ (x,z)\in (R\circ T)\wedge (x,z)\in (S\circ T)\iff \\ (x,z)\in (R\circ T)\cap (S\circ T)\end{array}$

Ćwiczenie 3.5

Podaj przykład relacji, dla których poniższa równość nie jest prawdziwa.

$(R\cap S)\circ T=(R\circ T)\cap (S\circ T).$

Rozwiązanie

Niech $R=\{(1,3)\},S=\{(2,3)\},T=\{(0,1),(0,2)\}$, wtedy

1. $R\cap S=\mathrm{\varnothing }$, więc $(R\cap S)\circ T=\mathrm{\varnothing }$.
2. $T\circ R=\{(0,3)\}$ i $T\circ S=\{0,3\}$, a więc $(R\circ T)\cap (S\circ T)=\{0,3\}$

Ćwiczenie 3.6

Udowodnij, że zbiór $A$ jest relacją wtedy i tylko wtedy, gdy

$A\subset (\bigcup \bigcup A)\times (\bigcup \bigcup A).$

Rozwiązanie

Pokażemy najpierw, że dla każdej relacji $R$ mamy

$\bigcup \bigcup R=R_L\cup R_P.\text{(3.12)}$

Zaczniemy od inkluzji $\subset$. Weźmy dowolny element $x\in \bigcup \bigcup R$, wtedy musi istnieć element $y\in \bigcup R$ taki, że $x\in y$. Skoro $y\in \bigcup R$, to musi istnieć para $(a,b)\in R$ taka, że $y\in (a,b)$. Wobec tego z definicji pary uporządkowanej $y=\{a\}$ lub $y=\{a,b\}$. Ponieważ $x\in y$, to $x=a$ i wtedy $x\in R_L$ lub $x=b$ i wtedy $x\in R_P$. Wobec tego $x\in R_L\cup R_P$.

Pokażemy teraz prawdziwość inkluzji $\supset$ w równaniu 3.12. Weźmy dowolny element $a\in R_L$ wtedy istnieje element $b\in R_P$ taki, że $(a,b)\in R$, a więc $\{(a,b)\}\subset R$. Stąd otrzymujemy

$\bigcup \bigcup \{(a,b)\}\subset \bigcup \bigcup R.$

Ponieważ $\bigcup \bigcup \{(a,b)\}=\bigcup \{\{a\},\{a,b\}\}=\{a,b\}$, to otrzymujemy $\{a,b\}\subset R$, a więc $a\in R$. Analogiczne rozumowanie można przeprowadzić dla elementu $b\in R_P$. Zakończyliśmy więc dowód równości 3.12.

W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli $A$ jest zbiorem, to $\bigcup \bigcup A$ jest zbiorem i $A$ jest podzbiorem iloczynu kartezjańskiego dwóch zbiorów, więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że $A$ jest relacją, wtedy

$A\subset A_L\times A_P\subset (A_L\cup A_P)\times (A_L\cup A_P)=(\bigcup \bigcup A)\times (\bigcup \bigcup A)$

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, w którym zaprzęgniemy relacje abstrakcji do definiowania liczb.

Rozpoczynamy rozdział od koniecznej definicji.

Definicja 4.1.

Dla zbioru $X$ definiujemy relację $1_X\subset X\times X$ jako $\{z\in X\times X:{\mathrm{\exists }}_{x\in X}(x,x)=z\}$.

Definicja 4.2.

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

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

Ćwiczenie 4.3

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

• ${\mathrm{\forall }}_{x\in X}(x,x)\in R$,
• ${\mathrm{\forall }}_{x,y\in X}(x,y)\in R\to (y,x)\in R$,
• ${\mathrm{\forall }}_{x,y,z\in X}(x,y)\in R\wedge (y,z)\in R\to (x,z)\in R$.

Rozwiązanie

Ćwiczenie jest elementarne.

Definicja 4.4.

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

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

Definicja 4.5.

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

Twierdzenie 4.6.

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

1. $[x{]}_R\cap [y{]}_R\ne \mathrm{\varnothing }$,
2. $[x{]}_R=[y{]}_R$,
3. $(x,y)\in R$.

Dowód

Pokażemy, że $(1)\to (2)$. Niech wspólny element dwóch klas $[x{]}_R$ oraz $[y{]}_R$ nazywa się $z$. Ze względu na pełną symetrię tezy wystarczy pokazać, że $[x{]}_R\subseteq [y{]}_R$. Niech zatem $p\in [x{]}_R$. Mamy więc $(x,p)\in R$. Z założenia jest również $(y,z)\in R$ oraz $(x,z)\in R$. Z symetrii otrzymujemy $(z,x)\in R$. Zatem $(y,z)\in R$ i $(z,x)\in R$ i $(x,p)\in R$. Natychmiast z przechodniości otrzymujemy, że $(y,p)\in R$.
Pokażemy, że $(2)\to (3)$. Ze zwrotności mamy, że $y\in [y{]}_R$, co z założenia $(2)$ daje $y\in [x{]}_R$, a to tłumaczy się na $(x,y)\in R$. Pokażemy, że $(3)\to (1)$. Wystarczy pokazać, że wspólnym elementem klas $[x{]}_R$ oraz $[y{]}_R$ jest $y$. Dla pierwszej z nich wynika to z założenia $(3)$, a dla drugiej ze zwrotności $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 $\kappa \ne \mathrm{\varnothing }$ będzie pewną rodziną (zbiorem) relacji równoważności o tym samym polu $X$. Mamy że:

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

Dowód

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

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

Rozkłady zbiorów

Definicja 4.8.

Niech $X\ne \mathrm{\varnothing }$. Rodzinę $r\in {𝒫}({𝒫}(X))$ nazywamy rozkładem zbioru $X$, gdy:

1. ${\mathrm{\forall }}_{C\in r}C\ne \mathrm{\varnothing }$,
2. $\bigcup r=X$,
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 $R$ o polu $X$ zbiór $X/R$ jest rozkładem $X$.

Dowód

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

Definicja 4.10.

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

$(x,y)\in R_r$ wtw Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \exists_{C\in r} \;\; x \in C \; \hspace*{0.1mm} \wedge \; y\in C. }

Lemat 4.11.

Dla rozkładu $r\in {𝒫}({𝒫}(X))$ relacja $R_r$ jest:

1. równoważnością,
2. $X/R_r=r.$

Dowód

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

Ćwiczenie 4.12

{{{3}}}

Rozwiązanie

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

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

$\begin{array}{r}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{array}$

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

Ćwiczenie 4.13

{{{3}}}

Rozwiązanie

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

$\begin{array}{r}(a,b)\in R\cup S\iff (a,b)\in R\vee (a,b)\in S\iff a\in [b{]}_R\vee a\in [b{]}_S\iff a\in [b{]}_R\cup [b{]}_S.\end{array}$

Pokażemy teraz, że jeśli $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 $x\in X$, dla którego $[x{]}_R⊈[x{]}_S$ oraz $[x{]}_R⊉[x{]}_S$. Wobec tego istnieje $y\in [x{]}_R\setminus [x{]}_S$ oraz $z\in [x{]}_S\setminus [x{]}_R$. Oznacza to, że $(y,x)\in R\setminus S$ oraz $(x,z)\in S\setminus R$. Skoro $R\cup S$ jest relacją równoważności, to $(z,y)\in R\cup S$. Przypuśćmy, że $(z,y)\in R$. Wtedy $(z,y),(y,x)\in R$, wobec czego $(z,x)\in R$, co jest sprzeczne z tym, że $(x,z)\in S\setminus R$, ponieważ relacja $R$ jest symetryczna. Analogiczną sprzeczność otrzymujemy dla $(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 $R,S$ takich, że $R\cup S$ jest relacją równoważności oraz $R⊈S$ i $S⊈R$. Polem relacji będzie zbiór $X=\{0,1,2,3\}$. Relacje $R,S$ określimy poprzez wyznaczane przez nie rozkłady odpowiednio $r,s$:

$\begin{array}{r}r=\{\{0\},\{1\},\{2,3\}\}\\ s=\{\{0,1\},\{2\},\{3\}\}.\end{array}$

Łatwo sprawdzić, że $R⊈S$ i $S⊈R$, gdyż $(2,3)\in R\setminus S$ oraz $(0,1)\in S\setminus R$. Z rozkładów $r,s$ w prosty sposób wynika, że formuła 4.1 jest prawdziwa dla tych relacji, wobec czego $R\cup S$ jest relacją równoważności. Wyznaczany przez nią rozkład to $\{\{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 $\alpha$ będzie rodziną relacji o polu $X$, czyli niech $\alpha \in {𝒫}({𝒫}(X^2))$. Rodzina $\alpha$ jest zamknięta na przecięcia, gdy:

1. $X^2\in \alpha ,$
2. jeżeli $\mathrm{\varnothing }\ne {\alpha }^{\prime }\subset \alpha$ to $\bigcap {\alpha }^{\prime }\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 $S\subset X^2$ jest domknięciem relacji $R\subset X^2$ w klasie (zbiorze) relacji $\alpha ,$ gdy:

1. $R\subset S,$
2. $S\in \alpha ,$
3. dla każdej relacji $T$ jeżeli $R\subset T$ oraz $T\in \alpha$ to $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 $(3)$ wzajemnie by się zawierały.

Twierdzenie 4.17.

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

1. Klasa relacji $\alpha$ jest domknięta na przecięcia.
2. Każda relacja ma domknięcie w klasie relacji $\alpha$.

Dowód

$(1)\to (2)$. Niech $R$ będzie relacją. Utwórzmy zbiór relacji ${\alpha }^{\prime }$ jako Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \left\{S\in\mathcal{P} (X^2) : R\subset S \hspace*{0.1mm} \wedge S\in\alpha \right\}} . Takie ${\alpha }^{\prime }$ nie jest puste, bowiem relacja totalna $X^2$ należy do ${\alpha }^{\prime }$. Pokażmy, że $\bigcap {\alpha }^{\prime }$ jest domknięciem $R$ w $\alpha$. Istotnie $R\subset \bigcap {\alpha }^{\prime }$. Z założenia mamy też $\bigcap {\alpha }^{\prime }\in \alpha$. Minimalność $\bigcap {\alpha }^{\prime }$ stwierdzamy przez: niech $R\subset S^{\prime }$ takie że $S^{\prime }\in \alpha$. Takie $S^{\prime }$ musi leżeć w zbiorze ${\alpha }^{\prime }$, jest więc $\bigcap {\alpha }^{\prime }\subset S^{\prime }$.
$(2)\to (1)$. Po pierwsze $X^2$ leży w zbiorze $\alpha$, bo wystarczy domknąć $X^2$. Niech ${\alpha }^{\prime }$ będzie niepustym podzbiorem $\alpha$. Niech $S_0$ będzie domknięciem $\bigcap {\alpha }^{\prime }$ w $\alpha$. Wiemy, że dla dowolnej relacji $S^{\prime }$, o ile $\bigcap {\alpha }^{\prime }\subset S^{\prime }$ i $S^{\prime }\in \alpha$ to $S_0\subset S^{\prime }$. Połóżmy za $S^{\prime }$ dowolny element z ${\alpha }^{\prime }$. Założenia implikacji pozostają automatycznie spełnione, jest więc tak, że $S_0\subset S^{\prime }$ dla dowolnej $S^{\prime }$ wyjętej z ${\alpha }^{\prime }$. W takim razie $S_0\subset \bigcap {\alpha }^{\prime }$. Ponieważ mamy też $\bigcap {\alpha }^{\prime }\subset S_0$, bo $S_0$ było domknięciem, jest więc $\bigcap {\alpha }^{\prime }=S_0$, a to oznacza, że $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 (patrz twierdzenie 4.17.), że nie istnieje domknięcie spójne ani antysymetryczne. (Relacja $R$ jest spójna, gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \forall x,y (x,y) \in R \hspace*{0.1mm} \vee (y,x)\in R} . Relacja $R$ jest antysymetryczna, gdy z faktu, że $(x,y)\in R$ oraz $(y,x)\in R$, da się pokazać, że $x=y$).

Rozwiązanie

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

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

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

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

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

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

(b) $(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ę $T\supset R$. Ponieważ $T$ jest symetryczna to $T\supset T^{-1}$. Skoro $T\supset R$ to $T^{-1}\supset R^{-1}$. Ponieważ $T\supset T^{-1}$, to $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 $n\in N\setminus \{0\}$ przez $R^n$ będziemy oznaczać $n$-krotne złożenie relacji $R$ z sobą (czyli $R^1=R$ oraz $R^{n+1}=R^n\circ R$ dla $n>1$). Zdefiniujmy rodzinę ${ℛ}$ jako zbiór wszystkich skończonych wielokrotnych złożeń relacji $R$ z sobą, czyli ${ℛ}=\{r\subset X^2:{\mathrm{\exists }}_{n\in N}(n\ne 0\wedge R^n=r)\}$. Do formalnego zdefiniowania rodziny ${ℛ}$ 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 $R$ w klasie relacji przechodnich na $X$ to relacja $\bigcup {ℛ}$. Pokażemy po kolei, że spełnia warunki domknięcia:

(a) $R=R^1\subset \bigcup {ℛ},$

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

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

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

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

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

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

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

Ćwiczenie 4.19

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

1. dla dowolnej relacji $R$ relacja $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$ jest relacją równoważności,
2. dla dowolnej relacji $R$ zachodzi

$((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 $X$. Z definicji zwrotności mamy, $R$ jest zwrotna wtedy i tylko wtedy gdy $R\supset 1_X$. W definicji domknięcia 4.15 (patrz Definicja 4.15.) punkt pierwszy mówi, że jeśli $S$ jest domknięciem to $S\supset R$. Wobec tego konieczne jest, aby $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 $R^{\alpha }$ jest zwrotna, to również zwrotna musi być $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$. Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia 4.18 (patrz ćwiczenie 4.18.). Można łatwo pokazać indukcyjnie, że dla dowolnego Parser nie mógł rozpoznać (nieznana funkcja „\inN”): {\displaystyle \displaystyle n\inN\setminus\{0\}} mamy $(R^n{)}^{-1}=(R^{-1}{)}^n$. Dla relacji symetrycznych dostajemy więc $(R^n{)}^{-1}=R^n$. Wobec tego mamy:

$(\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 $((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ę $R$, dla której relacja $((R^{\gamma }{)}^{\beta }{)}^{\alpha }$ nie jest przechodnia. Ponieważ relacja $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$ jest przechodnia, będzie to oznaczało, że te relacje są różne. Niech $X=\{0,1,2\}$ oraz $R=\{(0,2),(1,2)\}$. Relacja $R$ jest przechodnia, więc $R^{\gamma }=R$; jej symetryczne domknięcie to $(R^{\gamma }{)}^{\beta }=\{(0,2),(2,0),(1,2),(2,1)\}$. I po zwrotnym domknięciu otrzymujemy $((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ż $(0,2),(2,1)\in ((R^{\gamma }{)}^{\beta }{)}^{\alpha }$, podczas gdy $(0,1)\notin ((R^{\gamma }{)}^{\beta }{)}^{\alpha }$.