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ótka dyskusja. 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" . Proponuje 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:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x \times \emptyset &= \emptyset \quad \mbox{(2.1)}\\ x \times (y \cup z) &= (x \times y) \cup (x \times z) \quad \mbox{(2.2)}\\ x \times (y \cap z) &= (x \times y) \cap (x \times z) \quad \mbox{(2.3)}\\ x \times (y \setminus z) &= (x \times y) \setminus (x \times z) \quad \mbox{(2.4)} \endaligned}

Rozwiązanie

Z definicji iloczynu kartezjańskiego, oraz twierdzenia 1.2 (patrz twierdzenie 1.2.) łatwo 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.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x \times \emptyset =\\ \{z\in \mathcal{P}(\mathcal{P}(x \cup z)): \exists_{a\in x} \exists_{b\in \emptyset} (a,b)=z\}=\\ \{z\in \mathcal{P}(\mathcal{P}(x \cup z)): \exists_{a\in x} \exists_{b}[ (b \in \emptyset) \wedge (a,b)=z]\} \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (a,b)\in x \times (y \cup z) \Leftrightarrow\\ a \in x \wedge b\in (y\cup z) \Leftrightarrow\\ a\in x \wedge (b\in y \vee b\in z) \Leftrightarrow\\ (a\in x \wedge b\in y) \vee (a\in x \wedge b\in z) \Leftrightarrow\\ (a,b) \in x \times y \vee (a,b)\in x \times z \Leftrightarrow\\ (a,b) \in x \times y \cup x \times z. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (a,b)\in x \times (y \cap z) \Leftrightarrow\\ a \in x \wedge b\in (y\cap z) \Leftrightarrow\\ a\in x \wedge (b\in y \wedge b\in z) \Leftrightarrow\\ (a\in x \wedge b\in y) \wedge (a\in x \wedge b\in z) \Leftrightarrow\\ (a,b) \in x \times y \wedge (a,b)\in x \times z \Leftrightarrow\\ (a,b) \in x \times y \cap x \times z. \endaligned}

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (a,b) \in (x \times y) \setminus (x \times z) \Leftrightarrow \\ a\in x \wedge b\in y \wedge \neg(a\in x \wedge b\in z) \Leftrightarrow\\ b\in y \wedge (a\in x \wedge (a\notin x \vee b\notin z)) \Leftrightarrow\\ b\in y \wedge [(a\in x \wedge a\notin x) \vee (a\in x \wedge b\notin z)] \Leftrightarrow\\ b\in y \wedge (a\in x \wedge b\notin z) \Leftrightarrow\\ a\in x \wedge (b\in y \setminus z) \Leftrightarrow\\ (a,b) \in x \times (y \setminus z) \endaligned}

Ć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 „\aligned”): {\displaystyle \displaystyle \aligned 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)} \endaligned}

Rozwiązanie

Ćwiczenie jest elementarne.

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (a,b)\in x\times z \Leftrightarrow\\ a\in x \wedge b \in z \Rightarrow\\ a\in y \wedge b \in z \Leftrightarrow\\ (a,b)\in y\times z. \endaligned}

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

Ćwiczenie jest elementarne.

1.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,z)\in T \circ ( S \circ R ) \Leftrightarrow\\ \exists_{u} [(x,u)\in ( S \circ R ) \wedge (u,z)\in T]\Leftrightarrow\\ \exists_{u} [\exists_{v}( (x,v)\in R\wedge (v,u)\in S) \wedge (u,z)\in T]\Leftrightarrow\\ \exists_{u} \exists_{v}[ (x,v)\in R\wedge (v,u)\in S \wedge (u,z)\in T]\Leftrightarrow\\ \exists_{v} \exists_{u}[ (x,v)\in R\wedge ((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow\\ \exists_{v} [ (x,v)\in R\wedge \exists_{u}((v,u)\in S \wedge (u,z)\in T)]\Leftrightarrow\\ \exists_{v} [ (x,v)\in R\wedge (v,z)\in T \circ S]\Leftrightarrow\\ (x,z) \in (T \circ S) \circ R \Leftrightarrow\\ \endaligned}

2.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,z)\in (S \circ R )^{-1} \Leftrightarrow \\ (z,x) \in S\circ R \Leftrightarrow \\ \exists_{y} [(z,y) \in R \wedge (y,x)\in S] \Leftrightarrow \\ \exists_{y} [(y,z) \in R^{-1} \wedge (x,y)\in S^{-1}] \Leftrightarrow \\ (x,z)\in R^{-1} \circ S^{-1} \\ \endaligned}

3.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,z)\in R \Rightarrow \\ \exists_{y} (x,u) \in R \wedge \exists_{v} (v,y)\in R \Leftrightarrow\\ x\in R_L \wedge y\in R_P \Leftrightarrow \\ (x,y) \in R_L \times R_P \endaligned}

4.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x \in (S \circ R)_L \Leftrightarrow \\ \exists_{z} (x,z)\in S\circ R \Leftrightarrow\\ \exists_{z} \exists_{y} [(x,y)\in R \wedge (y,z)\in S ] \Rightarrow \\ \exists_{z} \exists_{y} (x,y)\in R \Leftrightarrow \\ \exists_{y} (x,y)\in R \Leftrightarrow \\ x \in R_L \endaligned}

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

6.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x\in (R^{-1} )_L \Leftrightarrow\\ \exists_{y} (x,y)\in R^{-1} \Leftrightarrow\\ \exists_{y} (y,x)\in R \Leftrightarrow\\ x\in R_P \endaligned}

Ć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

Ćwiczenie jest elementarne. 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.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,y)\in (R\cup S)^{-1} \Leftrightarrow\\ (y,x)\in (R\cup S) \Leftrightarrow\\ (y,x)\in R \vee (y,x) \in S \Leftrightarrow\\ (x,y)\in R^{-1} \vee (x,y) \in S^{-1} \Leftrightarrow\\ (x,y)\in R^{-1} \cup S^{-1} \endaligned}

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.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,y)\in (R^{-1})^{-1} \Leftrightarrow\\ (y,x)\in R^{-1} \Leftrightarrow\\ (x,y)\in R \endaligned}

4.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,z)\in (R \cup S ) \circ T \Leftrightarrow\\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cup S )] \Leftrightarrow\\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \vee (y,z)\in S ))] \Leftrightarrow\\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \vee ((x,y) \in T \wedge (y,z)\in S ))] \Leftrightarrow\\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \vee [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\ (x,z)\in (R \circ T) \vee (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cup (S \circ T) \endaligned}

5.

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (x,z)\in (R \cap S ) \circ T \Leftrightarrow\\ \exists_y [(x,y) \in T \wedge (y,z)\in (R \cap S )] \Leftrightarrow\\ \exists_y [(x,y) \in T \wedge ((y,z)\in R \wedge (y,z)\in S ))] \Leftrightarrow\\ \exists_y [((x,y) \in T \wedge (y,z)\in R) \wedge ((x,y) \in T \wedge (y,z)\in S ))] \Rightarrow\\ [\exists_y ((x,y) \in T \wedge (y,z)\in R)] \wedge [\exists_y ((x,y) \in T \wedge (y,z)\in S )] \Leftrightarrow\\ (x,z)\in (R \circ T) \wedge (x,z)\in (S \circ T) \Leftrightarrow \\ (x,z)\in (R \circ T) \cap (S \circ T) \endaligned}

Ć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ą roż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 wiec 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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned 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). \endaligned}

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 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, że 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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (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. \endaligned}

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 nie wprost 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$:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned r=\{\{0\},\{1\}, \{2,3\}\}\\ s=\{\{0,1\}, \{2\},\{3\}\}. \endaligned}

Ł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$ łatwo 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ą relacje 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

Ćwiczenie jest elementarne.

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