Tekst źródłowy strony 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 <math>\displaystyle x</math> oraz <math>\displaystyle y</math> będą
zbiorami. Przez parę uporządkowaną <math>\displaystyle (x,y)</math> rozumiemy zbiór

<center><math>\displaystyle \left\{ \left\{x\right\}, \left\{x,y\right\}\right\}</math></center>
}}
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:

<span id="twierdzenie_1_2">{{twierdzenie|1.2.||

Dla dowolnych zbiorów <math>\displaystyle a,b,c,d</math> zachodzi:

<center><math>\displaystyle (a,b) = (c,d) \Leftrightarrow  a=c  \wedge  b= d</math></center>

}}</span>

{{dowod|||

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

<center><math>\displaystyle (a,b) = (a,d). </math></center>

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

{{cwiczenie|1.3||

Dla każdej pary <math>\displaystyle x=(a,b)</math> udowodnij, że

<center><math>\displaystyle \bigcap \bigcap x= a.
</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Rozważymy dwa przypadki.
# Jeśli <math>\displaystyle a=b</math>, to <math>\displaystyle x=\{\{a\}\}</math> i wtedy <math>\displaystyle \bigcap \bigcap x= a</math>.
# Jeśli <math>\displaystyle a\neq b</math>, to <math>\displaystyle x=\{\{a\},\{a,b\}\}</math> a więc

<center><math>\displaystyle \bigcap x= \bigcap \{\{a\},\{a,b\}\}=  \{a\} \cap \{a,b\}= \{a\},
</math></center>

skąd otrzymujemy

<center><math>\displaystyle \bigcap \bigcap x=a.
</math></center>

</div></div>

<span id="cwiczenie_1_4">{{cwiczenie|1.4||

Udowodnij, że dla dowolnej pary uporządkowanej <math>\displaystyle x</math> zbiór

<center><math>\displaystyle \bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset))
</math></center>

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

}}</span>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Jeśli <math>\displaystyle x</math> jest parą, to istnieją zbiory <math>\displaystyle a,b</math> takie, że <math>\displaystyle x=(a,b)</math>.
1. Przypuśćmy, że <math>\displaystyle a\neq b</math>. Wtedy <math>\displaystyle x= \{\{a\}, \{a,b\}\}</math> i <math>\displaystyle \mathcal{P}(x)= \{\emptyset, \{\{a\}\}, \{\{a,b\}\},x \}</math>. Ponieważ <math>\displaystyle \mathcal{P}(\emptyset)=\{\emptyset\}</math> to <math>\displaystyle \mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\}, \{\{a,b\}\},x \}</math>, a wtedy

<center><math>\displaystyle \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset,
</math></center> 

gdyż przecinany zbiór zawiera elementy rozłączne <math>\displaystyle \{\{a\}\}, \{\{a,b\}\}</math>.  Wobec tego również

<center><math>\displaystyle \bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset.
</math></center>
2. W przypadku, gdy <math>\displaystyle a=b</math>, otrzymujemy <math>\displaystyle x=\{\{a\}\}</math>, a więc <math>\displaystyle \mathcal{P}(x)=\{\emptyset ,\{\{a\}\}\}</math> i wtedy <math>\displaystyle \mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\} \}</math> skąd otrzymujemy

<center><math>\displaystyle \bigcap \bigcap ( \mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \{a\}.
</math></center>

</div></div>

{{cwiczenie|1.5||

Pokaż, że z każdej pary <math>\displaystyle x</math> można otrzymać jej drugą współrzędną, posługując się
jedynie parą <math>\displaystyle x</math>, mnogościowymi operacjami <math>\displaystyle \bigcup, \bigcap, \cup,\cap,\setminus,\mathcal{P}()</math> oraz stałą <math>\displaystyle \emptyset</math>.
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none"> 
# Rozważ najpierw pary różnych elementów.
# Wykorzystaj zbiór z Ćwiczenia 1.4 (patrz [[#cwiczenie_1_4|ćwiczenie 1.4]]) .
</div></div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

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

<center><math>\displaystyle 
\bigcup (\bigcup x \setminus \bigcap x) =b. \quad \mbox{(1.1)}
</math></center>

Ponieważ <math>\displaystyle a\neq b</math>, to <math>\displaystyle x=\{\{a\}, \{a,b\}\}</math> i wtedy

<center><math>\displaystyle \bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a,b\} \setminus \{a\})=
\bigcup \{b\}= b.
</math></center>

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

<center><math>\displaystyle \bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a\} \setminus \{a\})= \bigcup
\emptyset= \emptyset.
</math></center>

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

<center><math>\displaystyle \bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset)).
</math></center>

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 <math>\displaystyle b</math>.

Dla par o równych elementach pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu 1.4 (patrz [[#cwiczenie_1_4|ćwiczenie 1.4]]) pokazaliśmy, że w takim przypadku mamy <math>\displaystyle \bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset))=\{b\}</math>, jeśli <math>\displaystyle b</math> jest współrzędną pary <math>\displaystyle x</math>. Wobec tego

<center><math>\displaystyle \bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset))= \emptyset \cup \bigcap\{b\}=b.
</math></center>

</div></div>

==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 <math>\displaystyle x\in X</math> oraz <math>\displaystyle y \in Y</math>.
Łatwo zauważyć, że zarówno
<math>\displaystyle \left\{x,y\right\}</math>, jak i <math>\displaystyle \left\{x\right\}</math> są podzbiorami <math>\displaystyle X \cup Y</math>.
Zatem
<math>\displaystyle \left\{x,y\right\} \in \mathcal{P} (X \cup Y)</math> oraz <math>\displaystyle \left\{x\right\} \in \mathcal{P} (X \cup Y)</math>.
Więc <math>\displaystyle \left\{\left\{x\right\},\left\{x,y\right\}\right\} \subseteq  \mathcal{P} (X \cup Y)</math>, co daje,
że <math>\displaystyle (x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y))</math>.

Istnienie i konstrukcja iloczynu
kartezjańskiego zostało dokładnie omówione  w dodatkowym
rozdziale [[Logika i teoria mnogości/Wykład 5.2| "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.

<span id="definicja_2_1">{{definicja|2.1.||

Niech <math>\displaystyle x,y</math> będą zbiorami. Iloczynem kartezjańskim (produktem)
<math>\displaystyle x \times y</math> nazywamy zbiór

<center><math>\displaystyle \left\{z\in \mathcal{P}( \mathcal{P}( x \cup y)): \exists_{a \in x} \exists_{b \in y}
\;\; (a,b) =z\right\}.
</math></center>

Będziemy używać specjalnej notacji <math>\displaystyle x^2</math> na zbiór <math>\displaystyle x \times x</math>.
}}</span>
{{cwiczenie|2.2||

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

<center><math>\displaystyle \begin{align} 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)}
\end{align}</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Z definicji iloczynu kartezjańskiego oraz twierdzenia 1.2 (patrz [[#twierdzenie_1_2|twierdzenie 1.2.]]) w sposób oczywisty wynika
następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów <math>\displaystyle a,b,x,y</math>
zachodzi

<center><math>\displaystyle (a,b)\in x \times y \Leftrightarrow (a\in x \wedge b\in y).
</math></center>
1. 

<center><math>\displaystyle \begin{align} 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]\}
\end{align}</math></center>

Ponieważ <math>\displaystyle b\in \emptyset</math> 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ę <math>\displaystyle (a,b)</math>, wtedy

<center><math>\displaystyle \begin{align} (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.
\end{align}</math></center>

3. Analogicznie do poprzedniego punktu, weźmy dowolną parę <math>\displaystyle (a,b)</math>, wtedy

<center><math>\displaystyle \begin{align} (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.
\end{align}</math></center>

4. Analogicznie do poprzednich punktów, weźmy dowolną parę <math>\displaystyle (a,b)</math>, wtedy

<center><math>\displaystyle \begin{align} (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).
\end{align}</math></center>

</div></div>

{{cwiczenie|2.3||

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

<center><math>\displaystyle \begin{align} x \subset y  &  \Rightarrow   &  (x \times z) \subset  (y \times z) \quad \mbox{(2.5)}\\
x \subset y  &  \Rightarrow   &  (z \times x) \subset  (z \times y) \quad \mbox{(2.6)} \end{align}</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

# Niech <math>\displaystyle x,y</math> będą dowolnymi zbiorami takimi, że <math>\displaystyle x\subset y</math>. Wtedy dla dowolnej pary <math>\displaystyle (a,b)</math> mamy

<center><math>\displaystyle \begin{align} (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.
\end{align}</math></center>

Stąd <math>\displaystyle (x \times z) \subset  (y \times z)</math>.
# Dla dowolnych zbiorów <math>\displaystyle x\subset y</math> mamy <math>\displaystyle x \cup y =y</math>. Z poprzedniego
ćwiczenia otrzymujemy

<center><math>\displaystyle z \times y =z \times (x\cup y) =  (z \times x)\cup(z \times y) \supset (z \times x).
</math></center>

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

</div></div>

{{cwiczenie|2.4||

Sprawdź, czy dla dowolnych zbiorów <math>\displaystyle A,B,C</math>, prawdziwa jest następująca implikacja:

<center><math>\displaystyle A\times B = A\times C \Rightarrow B=C
</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Nie. Na przykład, gdy <math>\displaystyle A=\emptyset</math>, to dla dowolnych zbiorów <math>\displaystyle B,C</math> mamy

<center><math>\displaystyle \emptyset \times B =\emptyset = \emptyset \times C.
</math></center>

Biorąc różne zbiory <math>\displaystyle B,C</math>, otrzymamy kontrprzykład dla badanej implikacji.
</div></div>

==Relacje==

{{definicja|3.1.||

Relacją nazywamy każdy podzbiór iloczynu <math>\displaystyle x
\times y</math>.
}}
===Operacje na relacjach:===

{{definicja|3.2.||

Niech <math>\displaystyle R \subset A \times B</math> oraz <math>\displaystyle S \subset B \times C</math>.

<math>\displaystyle S \circ R  :=  \left\{(x,z)\in A \times C : \exists_{y\in B}
(x,y)\in R  \wedge  (y,z)\in S \right\}</math>

<math>\displaystyle R^{-1} := \left\{(y,x)\in B \times A : \;\; (x,y)\in R \right\}</math><br>
<math>\displaystyle R_L := \left\{x\in A : \exists_{y\in B} \;\; (x,y) \in R\right\}</math><br>
<math>\displaystyle R_P := \left\{y\in B : \exists_{x\in A} \;\; (x,y) \in R\right\}</math>
}}
{{cwiczenie|3.3||

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

<center><math>\displaystyle \begin{array}{rllll} T \circ ( S \circ R ) & = & (T \circ S)\circ R \quad \mbox{(3.1)}\\ (S \circ R )^{-1} & = & R^{-1} \circ S^{-1} \quad \mbox{(3.2)}\\ R & \subset & R_L \times R_P \quad \mbox{(3.3)}\\
(S \circ R)_L & \subset & R_L \quad \mbox{(3.4)}\\
(S \circ R)_P & \subset & S_P \quad \mbox{(3.5)}\\
(R^{-1} )_L & = & R_P \quad \mbox{(3.6)}
\end{array}</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  


1. 

<center><math>\displaystyle \begin{align} (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 \\
\end{align}</math></center>

2. 

<center><math>\displaystyle \begin{align} (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} \\
\end{align}</math></center>

3. 

<center><math>\displaystyle \begin{align} (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
\end{align}</math></center>

4.

<center><math>\displaystyle \begin{align} 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
\end{align}</math></center>

5. Dowód <math>\displaystyle (S \circ R)_P \subset  S_P </math> jest analogiczny do poprzedniego.

6.

<center><math>\displaystyle \begin{align} 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
\end{align}</math></center>

</div></div>

{{cwiczenie|3.4||

Niech relacja  <math>\displaystyle  R \subset B \times C,\;  S \subset B \times C</math> oraz
<math>\displaystyle T \subset A \times  B</math>. Pokaż własności:

<center><math>\displaystyle \begin{array}{rlllll} (R \cup  S )^{-1} & = & R^{-1} \cup S^{-1} \quad \mbox{(3.7)}\\ (R \cap  S )^{-1} & = & R^{-1} \cap S^{-1} \quad \mbox{(3.8)}\\ (R^{-1})^{-1} & = & R \quad \mbox{(3.9)}\\ (R \cup  S ) \circ T & = & (R \circ T) \cup (S  \circ T) \quad \mbox{(3.10)}\\ (R \cap  S ) \circ T & \subset &  (R \circ T) \cap (S  \circ T) \quad \mbox{(3.11)}\end{array}</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

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. 

<center><math>\displaystyle \begin{align} (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}
\end{align}</math></center>

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

3. 

<center><math>\displaystyle \begin{align} (x,y)\in (R^{-1})^{-1}   \Leftrightarrow\\
(y,x)\in R^{-1}   \Leftrightarrow\\
(x,y)\in R
\end{align}</math></center>
4. 

<center><math>\displaystyle \begin{align} (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)
\end{align}</math></center>
5. 

<center><math>\displaystyle \begin{align} (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)
\end{align}</math></center>

</div></div>

{{cwiczenie|3.5||

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

<center><math>\displaystyle (R \cap  S ) \circ T =  (R \circ T) \cap (S  \circ T).
</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Niech <math>\displaystyle R=\{(1,3)\}, S= \{(2,3)\}, T=\{(0,1),(0,2)\}</math>, wtedy
# <math>\displaystyle R\cap S=\emptyset</math>, więc      <math>\displaystyle (R\cap S)\circ T=\emptyset</math>.
# <math>\displaystyle T\circ R =\{(0,3)\}</math> i <math>\displaystyle T \circ S=\{0,3\}</math>, a więc <math>\displaystyle (R \circ T) \cap (S  \circ T) =\{0,3\}</math>

</div></div>

{{cwiczenie|3.6||

Udowodnij, że zbiór <math>\displaystyle A</math> jest relacją wtedy i tylko wtedy, gdy

<center><math>\displaystyle A \subset (\bigcup \bigcup A) \times  (\bigcup \bigcup A).
</math></center>

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Pokażemy najpierw, że dla każdej relacji <math>\displaystyle R</math> mamy

<center><math>\displaystyle 
\bigcup \bigcup R = R_L \cup R_P. \quad \mbox{(3.12)}
</math></center>

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

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

<center><math>\displaystyle \bigcup \bigcup \{(a,b)\} \subset \bigcup \bigcup R.
</math></center>

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

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

<center><math>\displaystyle 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)
</math></center>

</div></div>

==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 [[Logika i teoria mnogości/Wykład 8: Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek|wykład 8]], w którym
zaprzęgniemy relacje abstrakcji do definiowania liczb.

Rozpoczynamy rozdział od koniecznej definicji.

<span id="definicja_4_1">{{definicja|4.1.||

Dla zbioru <math>\displaystyle X</math> definiujemy relację <math>\displaystyle 1_X \subset X \times X</math>
jako <math>\displaystyle \left\{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z  \right\}</math>.
}}</span>
{{definicja|4.2.||

Relację <math>\displaystyle R \subset X \times X</math> nazywamy relacją równoważnością o
polu <math>\displaystyle X</math>, jeżeli:
* zawiera relacje <math>\displaystyle 1_X </math> (zwrotność <math>\displaystyle R</math>),
* <math>\displaystyle R^{-1} \subset R</math> (symetria <math>\displaystyle R</math>),
* <math>\displaystyle R \circ R \subset R</math> (przechodniość <math>\displaystyle R</math>).
}}
{{cwiczenie|4.3||

Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu <math>\displaystyle X</math>
są odpowiednio równoważne następującym własnościom:
* <math>\displaystyle \forall_{ x\in X} (x,x) \in R</math>,
* <math>\displaystyle \forall_{ x,y \in X} (x,y) \in R \rightarrow (y,x) \in R</math>,
* <math>\displaystyle \forall_{ x,y,z\in X} (x,y)\in R \wedge (y,z) \in R \rightarrow (x,z)\in R</math>.

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Ćwiczenie jest elementarne.
</div></div>

{{definicja|4.4.||

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

<center><math>\displaystyle [x]_R := \left\{y \in X : (x,y) \in R\right\}. </math></center>
}}
{{definicja|4.5.||

Zbiór klas równoważności relacji <math>\displaystyle R</math> będący elementem zbioru <math>\displaystyle \mathcal{P}
( \mathcal{P} (X \times X))</math> oznaczamy przez <math>\displaystyle X/R</math>.   
}}
<span id="twierdzenie_4_6">{{twierdzenie|4.6.||

Niech <math>\displaystyle R</math> będzie relacją równoważności o polu <math>\displaystyle X</math>. Następujące warunki są równoważne:
# <math>\displaystyle [x]_R \cap [y]_R \neq \emptyset</math>,
# <math>\displaystyle [x]_R = [y]_R</math>,
# <math>\displaystyle (x,y) \in R</math>.

}}</span>

{{dowod|||

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

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 <math>\displaystyle \kappa \neq \emptyset </math> będzie pewną rodziną
(zbiorem) relacji równoważności o tym samym polu <math>\displaystyle X</math>. Mamy że:
# <math>\displaystyle \bigcap \kappa </math> jest relacją równoważności o polu <math>\displaystyle X</math>,
# <math>\displaystyle [x]_{ \bigcap \kappa } = \bigcap \left\{[x]_R : R\in
\kappa\right\}</math>.

}}

{{dowod|||

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

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

===Rozkłady zbiorów===

{{definicja|4.8.||

Niech <math>\displaystyle X \neq \emptyset</math>. Rodzinę
<math>\displaystyle r \in \mathcal{P} ( \mathcal{P} (X))</math> nazywamy rozkładem zbioru <math>\displaystyle X</math>, gdy:
# <math>\displaystyle \forall_{C \in r} \;\; C \neq \emptyset</math>,
# <math>\displaystyle \bigcup r =X</math>,
# <math>\displaystyle (C \in r  \wedge  D \in r  \wedge  C \neq D ) \Rightarrow  C\cap D =\emptyset</math>.
}}
{{lemat|4.9.||

Dla relacji równoważności <math>\displaystyle R</math> o polu <math>\displaystyle X</math> zbiór <math>\displaystyle X/R</math> jest rozkładem
<math>\displaystyle X</math>. 
}}

{{dowod|||

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

}}

{{definicja|4.10.||

Niech <math>\displaystyle r</math> będzie rozkładem zbioru <math>\displaystyle X</math>. Definiujemy relacje <math>\displaystyle R_r
\subset X \times X</math> następująco:

<center><math>\displaystyle (x,y) \in R_r  </math>   wtw   <math>\displaystyle   \exists_{C\in r} \;\; x \in C \;  \wedge  \; y\in C.
</math></center>
}}
{{lemat|4.11.||

Dla rozkładu <math>\displaystyle r \in \mathcal{P} ( \mathcal{P}
(X))</math> relacja <math>\displaystyle R_r</math> jest:
# równoważnością,
# <math>\displaystyle X/{R_r} = r.</math>

}}

{{dowod|||

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

{{cwiczenie|4.12||

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

<center><math>\displaystyle (A,B)\in R \Leftrightarrow A\frac{.}{} B \subset Y.
</math></center>

(<math>\displaystyle A\frac{.}{}B</math> oznacza różnicę symetryczną zbiorów, czyli <math>\displaystyle A\frac{.}{} B = (A\setminus B)\cup
(B \setminus A)</math>). Udowodnij, że relacja <math>\displaystyle R</math> jest relacją równoważności. 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Najtrudniej jest pokazać przechodniość. Udowodnij, że <math>\displaystyle A \frac{.}{} C \subset    (B\frac{.}{} C) \cup (A\frac{.}{} B)</math>. Dobrym punktem wyjścia
jest naszkicowanie wszystkich przecięć zbiorów <math>\displaystyle A,B,C</math>.
</div></div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

Pokażemy po kolei zwrotność, przechodniość i symetryczność.
# Dla każdego <math>\displaystyle A\subset X</math> mamy <math>\displaystyle A\frac{.}{} A= \emptyset \subset Y</math>, a więc relacja <math>\displaystyle R</math> jest zwrotna.
# Ponieważ dla dowolnych zbiorów <math>\displaystyle A\frac{.}{} B= B\frac{.}{} A</math>, to <math>\displaystyle (A,B)\in R</math> wtedy i tylko wtedy, gdy <math>\displaystyle (B,A)\in R</math>. Wobec tego relacja <math>\displaystyle R</math> jest symetryczna.
# Weźmy zbiory <math>\displaystyle A,B,C \subset X</math>, takie że <math>\displaystyle (A,B), (B,C) \in R</math>. Wtedy

<center><math>\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}</math></center>

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

</div></div>

{{cwiczenie|4.13||

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

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

Podaj przykłady relacji równoważności <math>\displaystyle R,S</math> takich, że <math>\displaystyle R\cup S</math> jest relacją
równoważności oraz <math>\displaystyle R\nsubseteq S</math> i <math>\displaystyle S\nsubseteq R</math>. 
}}
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Wskazówka </span><div class="mw-collapsible-content" style="display:none">
Przyjrzyj się dokładnie rodzinie zbiorów <math>\displaystyle A=\{[x]_R \cup [x]_S : x\in X\}</math>.
</div></div>


<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

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

<center><math>\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}</math></center>

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

<center><math>\displaystyle \begin{align} r=\{\{0\},\{1\}, \{2,3\}\}\\
s=\{\{0,1\}, \{2\},\{3\}\}.
\end{align}</math></center>

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

===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 <math>\displaystyle \alpha</math> będzie rodziną relacji o polu
<math>\displaystyle X</math>, czyli niech <math>\displaystyle \alpha \in \mathcal{P} ( \mathcal{P} (X^2))</math>.
Rodzina <math>\displaystyle \alpha</math> jest zamknięta na przecięcia, gdy:
# <math>\displaystyle X^2 \in \alpha,</math>
# jeżeli <math>\displaystyle \emptyset \neq \alpha ' \subset \alpha</math> to  <math>\displaystyle \bigcap
\alpha ' \in \alpha.</math>
}}
Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji.
Definiujemy intuicyjnie najmniejszą relację zawierającą daną  należącą do klasy.

<span id="definicja_4_15">{{definicja|4.15.||

Relacja <math>\displaystyle S \subset X^2</math> jest domknięciem relacji <math>\displaystyle R \subset X^2</math> w klasie (zbiorze)
relacji <math>\displaystyle \alpha,</math> gdy:
# <math>\displaystyle R \subset S,</math>
# <math>\displaystyle S \in \alpha,</math>
# dla każdej relacji <math>\displaystyle T</math> jeżeli <math>\displaystyle R \subset T</math> oraz <math>\displaystyle T \in \alpha</math> to <math>\displaystyle S \subset T.</math>
}}</span>
{{lemat|4.16.||

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

{{dowod|||

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

{{twierdzenie|4.17.||

Następujące warunki są równoważne:
# Klasa relacji <math>\displaystyle \alpha</math> jest domknięta na przecięcia.
# Każda relacja ma domknięcie w klasie relacji <math>\displaystyle \alpha</math>.

}}

{{dowod|||

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

<span id="cwiczenie_4_18">{{cwiczenie|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|twierdzenie 4.17.]]), że nie istnieje domknięcie spójne
ani antysymetryczne. (Relacja <math>\displaystyle R</math> jest spójna, gdy <math>\displaystyle \forall x,y (x,y) \in R  \vee 
(y,x)\in R</math>. Relacja <math>\displaystyle R</math> jest antysymetryczna, gdy z faktu, że <math>\displaystyle (x,y) \in R</math> oraz
<math>\displaystyle (y,x) \in R</math>, da się pokazać, że <math>\displaystyle x=y</math>).

}}</span>

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  

1. Pokażemy, że dla każdej relacji <math>\displaystyle R\in X^2</math> jej domknięcie w klasie relacji zwrotnych na <math>\displaystyle X</math> to <math>\displaystyle R\cup 1_X</math>. Pokażemy po kolei, że spełnia warunki domknięcia:
:(a)  <math>\displaystyle R \subset R \cup 1_X,</math>
:(b)  <math>\displaystyle 1_X \subset R \cup 1_X</math>, a więc jest zwrotna,
:(c)  weźmy dowolną zwrotną relację <math>\displaystyle T\supset R</math>. Ponieważ <math>\displaystyle T</math> jest zwrotna to <math>\displaystyle T\supset 1_X</math>, a więc <math>\displaystyle T\supset R \cup 1_X</math>.

2. Pokażemy, że dla każdej relacji <math>\displaystyle R\in X^2</math> jej domknięcie w klasie relacji symetrycznych na <math>\displaystyle X</math> to <math>\displaystyle R\cup R^{-1}</math>. Pokażemy po kolei, że spełnia warunki domknięcia:
:(a)  <math>\displaystyle R \subset R \cup R^{-1},</math>
:(b)  <math>\displaystyle (R \cup R^{-1})^{-1} = R^{-1} \cup (R^{-1})^{-1}= R^{-1} \cup R= R \cup R^{-1} </math>, a więc jest symetryczna ,
:(c) weźmy dowolną symetryczną relację <math>\displaystyle T\supset R</math>. Ponieważ <math>\displaystyle T</math> jest symetryczna to <math>\displaystyle T \supset T^{-1}</math>. Skoro <math>\displaystyle T \supset R</math> to <math>\displaystyle T^{-1} \supset R^{-1}</math>. Ponieważ <math>\displaystyle T \supset T^{-1}</math>, to <math>\displaystyle T\supset R\cup R^{-1}</math>.

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 <math>\displaystyle n\in N \setminus\{0\}</math> przez <math>\displaystyle R^n</math> będziemy oznaczać <math>\displaystyle n</math>-krotne złożenie relacji <math>\displaystyle R</math> z sobą (czyli <math>\displaystyle R^1=R</math> oraz <math>\displaystyle R^{n+1}= R^n \circ R</math> dla <math>\displaystyle n>1</math>). Zdefiniujmy rodzinę <math>\displaystyle \mathcal{R}</math> jako zbiór wszystkich skończonych wielokrotnych złożeń relacji <math>\displaystyle R</math> z sobą, czyli <math>\displaystyle \mathcal{R}=\{r\subset X^2 : \exists_{n\in N}  (n\neq 0 \wedge R^n=r)\}</math>. Do formalnego zdefiniowania rodziny <math>\displaystyle \mathcal{R}</math> 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 <math>\displaystyle R</math> w klasie relacji przechodnich na <math>\displaystyle X</math> to relacja <math>\displaystyle \bigcup \mathcal{R}</math>. Pokażemy po kolei, że spełnia warunki domknięcia:
:(a) <math>\displaystyle R=R^1 \subset \bigcup \mathcal{R},</math>
:(b) Aby pokazać, że relacja <math>\displaystyle \bigcup \mathcal{R}</math> jest przechodnia, weźmy dowolne dwie pary <math>\displaystyle (a,b),(b,c) \in \mathcal{R}</math>. Wtedy muszą istnieć liczby <math>\displaystyle n,m \in N</math> takie, że <math>\displaystyle (a,b)\in R^n</math> oraz <math>\displaystyle (b,c)\in R^m</math>. Wobec tego <math>\displaystyle (a,c)\in R^m \circ R^n</math>. Z łączności składania relacji wynika, że <math>\displaystyle R^m \circ R^n= R^{m+n}</math>. Wobec tego <math>\displaystyle (a,c)\in R^{m+n} \subset \bigcup \mathcal{R}</math>.
:(c) Weźmy dowolną przechodnią relację <math>\displaystyle T</math> taką, że <math>\displaystyle R\subset T</math>, pokażemy indukcyjnie, że dla każdego <math>\displaystyle n\in N\setminus \{0\}</math> mamy <math>\displaystyle R^n\subset T</math>.
::i. Baza indukcji. Dla <math>\displaystyle n=1</math> mamy <math>\displaystyle R^1=R</math>, a więc z założenia <math>\displaystyle R^1\subset T</math>.
::ii. Krok indukcyjny. Weźmy dowolne <math>\displaystyle n\in N\setminus \{0,1\}</math> i przypuśćmy, że dla każdego <math>\displaystyle 0<m<n</math> zachodzi <math>\displaystyle R^m\subset T</math>. Weźmy dowolną parę <math>\displaystyle (a,c)\in R^n</math>. Ponieważ <math>\displaystyle n>1</math>, to <math>\displaystyle R^n= R^{n-1} \circ R</math>. Oznacza to, że istnieje element <math>\displaystyle b\in X</math> taki, że <math>\displaystyle (a,b)\in R</math> oraz <math>\displaystyle (b,c)\in R^{n-1}</math>. Z założenia indukcyjnego wynika, że <math>\displaystyle (a,b)\in T</math> oraz <math>\displaystyle (b,c)\in T</math>. Ponieważ <math>\displaystyle T</math> jest przechodnia to <math>\displaystyle (a,c)\in T</math>. Wobec dowolności wyboru pary <math>\displaystyle (a,c)</math> otrzymujemy <math>\displaystyle R^n \subset T</math>.

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

Pokażemy teraz, że istnieje zbiór <math>\displaystyle X</math> taki, że klasa relacji spójnych na zbiorze <math>\displaystyle X</math> i
klasa relacji symetrycznych na zbiorze <math>\displaystyle X</math> nie są domknięte na przecięcia. W obliczu
Twierdzenia 4.17 (patrz [[#twierdzenie_4_17|Twierdzenie 4.17.]]) będzie to oznaczało, że nie wszystkie relacje mają
domknięcia  w tych klasach. Niech <math>\displaystyle X=\{0,1\}</math>.
# Relacje <math>\displaystyle \{(0,1),(0,0),(1,1)\}, \{(1,0),(0,0),(1,1)\}</math> są spójne na <math>\displaystyle X</math>, a ich przecięcie, czyli zbiór <math>\displaystyle \{(0,0),(1,1)\}</math>, nie jest.
# Relacja <math>\displaystyle X^2</math> nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na <math>\displaystyle X</math> nie jest domknięta na przecięcia.

</div></div>

{{cwiczenie|4.19||

Dla relacji <math>\displaystyle R</math> niech <math>\displaystyle R^\alpha</math>, <math>\displaystyle R^\beta</math>, <math>\displaystyle R^\gamma</math> oznaczają odpowiednio zwrotne, symetryczne, przechodnie domknięcie relacji <math>\displaystyle R</math>. Czy prawdą jest, że:
# dla dowolnej relacji <math>\displaystyle R</math> relacja <math>\displaystyle ((R^\alpha)^\beta)^\gamma</math> jest relacją równoważności,
# dla dowolnej relacji <math>\displaystyle R</math> zachodzi

<center><math>\displaystyle ((R^\alpha)^\beta)^\gamma =((R^\gamma)^\beta)^\alpha.
</math></center>

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

}}

<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none">  
1. Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze <math>\displaystyle X</math>. Z definicji zwrotności mamy, <math>\displaystyle R</math> jest zwrotna wtedy i tylko wtedy gdy <math>\displaystyle R\supset 1_X</math>. W definicji domknięcia 4.15 (patrz [[#definicja_4_15|Definicja 4.15.]]) punkt pierwszy mówi, że jeśli <math>\displaystyle S</math> jest domknięciem to <math>\displaystyle S\supset R</math>. Wobec tego konieczne jest, aby <math>\displaystyle S\supset 1_X</math>. 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 <math>\displaystyle R^\alpha</math> jest zwrotna, to również zwrotna musi być <math>\displaystyle ((R^\alpha)^\beta)^\gamma</math>. Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia 4.18 (patrz [[#cwiczenie_4_18|ćwiczenie 4.18.]]). Można łatwo pokazać indukcyjnie, że dla dowolnego <math>\displaystyle n\in N\setminus\{0\}</math> mamy <math>\displaystyle (R^n)^{-1}=(R^{-1})^n</math>. Dla relacji symetrycznych dostajemy więc <math>\displaystyle (R^n)^{-1}=R^n</math>. Wobec tego mamy:

<center><math>\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\}\},
</math></center>

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

</div></div>