4. Relacje#
4.1. Relacje binarne#
Narration
Niech \(X, Y\) będą ustalonymi zbiorami.
Definicja 4.1
Relacją binarną (dwuargumentową) między elementami zbioru \(X\) a elementami zbioru \(Y\) nazywamy dowolny podzbiór
Element \(x\in X\) jest w relacji \(R\) z elementem \(y\in Y\), gdy
Jeśli \(X=Y\), to mówimy, że relacja \(R\subseteq X\times X\) jest określona w zbiorze \(X .\)
Przykład 4.1
Relacja pusta w dowolnym zbiorze \(X\):
\[\emptyset \ \subseteq\ X \times X.\]Relacja pełna w dowolnym zbiorze \(X\):
\[F \ = \ X \times X.\]Relacja podzielności w zbiorze liczb \(\nn\):
\[\mid \ = \ \Set{(x,y)\in \nn\times \nn : \exists k\in \nn\ \ y=k\cdot x}.\]Dla ustalonego \(n\in \nn\), relacja przystawania modulo \(n\) w zbiorze \(\zz\):
\[\equiv_n \ = \ \Set{(z_1,z_2)\in \zz\times \zz : n\mid(z_1-z_2)}.\]Relacja równoważności formuł w zbiorze formuł rachunku zdań:
\[T \ = \ \Set{(\alpha,\beta)\in X\times X : \alpha \imply\beta \ \text{i}\ \beta \imply\alpha \ \text{są tautologiami}}.\]Relacja mniejszości w zbiorze \(\rr\):
\[\leq \ = \ \Set{(x,y)\in \rr\times \rr : x\leq y}.\]
4.2. Własności relacji#
Definicja 4.2
Relację \(R \subseteq X \times X\) nazywamy:
zwrotną, jeśli \(\forall x \in X \quad xRx\);
symetryczną, jeśli \(\forall x,y \in X \quad xRy \Rightarrow yRx\);
przechodnią, jeśli \(\forall x,y,z \in X \quad xRy \wedge yRz \Rightarrow xRz\);
antysymetryczną, jeśli \(\forall x,y \in X \quad xRy \wedge yRx \Rightarrow x=y .\)
Przykład 4.2
Relacje zwrotne: \(=,\ \leq,\ \mid,\ \subseteq .\)
Relacje symetryczne: \(=\), równoległość prostych na płaszczyźnie.
Relacje przechodnie: \(=,\ \leq,\ \subseteq,\ \mid .\)
Relacje antysymetryczne: \(\leq,\ \subseteq,\ \mid .\)
Ćwiczenie 4.1
Sprawdźmy, które z własności (zwrotność, symetria, przechodniość, antysymetria) ma relacja \(R\subseteq \rr\times\rr\) zadana wzorem
Rozwiązanie
Zwrotna: \(|x-x|=0\leq 1\) dla każdego \(x\in\rr\) – tak.
Symetryczna: \(|x-y|=|y-x|\), więc jeśli \(|x-y|\leq 1\) to i \(|y-x|\leq 1\) – tak.
Przechodnia: nie, np. \(0R1\) i \(1R2\), ale \(|0-2|=2 > 1\), więc \(\Negation(0R2) .\)
Antysymetryczna: nie, np. \(0R1\) i \(1R0\), choć \(0\neq 1 .\)
4.3. Relacja równoważności#
Definicja 4.3
Relację \(R \subseteq X \times X\) nazywamy relacją równoważności, jeśli jest zwrotna, symetryczna i przechodnia.
Przykład 4.3 (Przykłady relacji równoważności)
W dowolnym zbiorze \(X .\) Relacja pełna \(F=X \times X .\)
W zbiorze \(\zz\), relacja przystawania \(\equiv_n\) modulo \(n .\)
W zbiorze formuł rachunku zdań, relacja \(T .\)
W dowolnym zbiorze \(X .\) Relacja równości \(=\ \subseteq X\times X .\)
W zbiorze prostych na płaszczyźnie. Relacja równoległości prostych.
Ćwiczenie 4.2
Sprawdźmy, że relacje \(\equiv_n\) i \(T\) z Prz. 4.1 są relacjami równoważności.
Rozwiązanie
Relacja \(\equiv_n \ = \ \Set{(z_1,z_2)\in \zz\times \zz : n\mid(z_1-z_2)}\):
zwrotność: \(\forall x \in \zz \quad x-x = 0 = n \cdot 0 \implies n \mid (x-x) \implies x \equiv_n x\)
symetria: \(\forall x,y \in \zz \quad x \equiv_n y \implies n \mid (x-y) \implies x-y = nk \implies y-x = n(-k) \implies n \mid (y-x) \implies y \equiv_n x\)
przechodniość: \(\forall x,y,z \in \zz \quad (x \equiv_n y \wedge y \equiv_n z) \implies (n \mid (x-y) \wedge n \mid (y-z)) \implies x-z = (x-y)+(y-z) = nk+nm = n(k+m) \implies n \mid (x-z) \implies x \equiv_n z\)
Relacja \(T \ = \ \Set{(\alpha,\beta)\in X\times X : \alpha \imply\beta \ \text{i}\ \beta \imply\alpha \ \text{są tautologiami}}\):
zwrotność: \(\forall \alpha \in X \quad \alpha \imply \alpha\) jest prawem logiki (tautologią), zatem \(\alpha T \alpha\)
symetria: \(\forall \alpha,\beta \in X \quad \alpha T \beta \implies (\alpha \imply \beta \text{ oraz } \beta \imply \alpha \text{ są taut.}) \implies (\beta \imply \alpha \text{ oraz } \alpha \imply \beta \text{ są taut.}) \implies \beta T \alpha\)
przechodniość: \(\forall \alpha,\beta,\gamma \in X \quad (\alpha T \beta \wedge \beta T \gamma) \implies (\alpha \imply \beta, \beta \imply \alpha, \beta \imply \gamma, \gamma \imply \beta \text{ są taut.}) .\) Z przechodniości implikacji \([(p \imply q) \wedge (q \imply r)] \imply (p \imply r)\) wynika, że \(\alpha \imply \gamma\) oraz \(\gamma \imply \alpha\) są tautologiami, zatem \(\alpha T \gamma\)
W obu przypadkach zachodzą wszystkie trzy warunki, więc \(\equiv_n\) oraz \(T\) są relacjami równoważności.
4.3.1. Klasy abstrakcji i zbiór ilorazowy#
Narration
Niech \(R \subseteq X \times X\) będzie relacją równoważności i niech \(a\in X .\)
Definicja 4.4
Zbiór
nazywamy klasą abstrakcji elementu \(a\) (względem relacji \(R\)).
Element \(a\) nazywamy wtedy reprezentantem tej klasy.
Przykład 4.4
Dla relacji równoważności zdefiniowanych w Prz. 4.1.
\([a]_{=} = \Set{x \in X : x=a} = \Set{a} .\)
\([a]_F = \Set{x \in X : xFa} = X .\)
\([a]_{\equiv_n} = \Set{z \in \zz : z \equiv_n a} = \Set{z \in \zz : n\mid(z-a)}= \Set{a+k n : k \in \zz} .\)
\([\alpha\vee \Negation\alpha]_T\) – klasa dowolnej tautologii \(\alpha\vee\Negation\alpha\) względem relacji \(T\) z poprzedniego przykładu to zbiór wszystkich tautologii.
Definicja 4.5
Zbiór wszystkich klas abstrakcji relacji równoważności \(R\subseteq X\times X\)
nazywamy zbiorem ilorazowym relacji \(R .\)
Przykład 4.5
\(\zz_n := \zz/_{\equiv_n}=\Set{[0]_{\equiv_n},[1]_{\equiv_n},\ldots,[n-1]_{\equiv_n}} .\)
\(X/_F=\Set{[x]_F} = \Set{X}\) (dla relacji pełnej \(F\) – jedna klasa).
\(X/_==\Set{\Set{x} : x\in X}\) (dla relacji równości – klasy jednoelementowe).
Ćwiczenie 4.3
Sprawdźmy, że relacja
jest relacją równoważności w zbiorze \(\rr\), i znajdźmy jej klasy abstrakcji oraz zbiór ilorazowy \(\rr/_R .\)
Odpowiedź
Zwrotność, symetria i przechodniość wynikają natychmiast z odpowiednich własności równości liczb. Dla \(a\in \rr\) mamy
Zatem \(\rr/_R = \Set{\Set{-a,a} : a\geq 0}\) – każda klasa (poza \(\Set{0}\)) ma dokładnie dwóch reprezentantów.
Twierdzenie 4.1
Dla dowolnej relacji równoważności \(R\subseteq X\times X\) i dowolnych \(a,b\in X\):
\(a \in [a]_R\);
\([a]_R = [b]_R \ \vee\ [a]_R \cap [b]_R = \emptyset\)
\(\displaystyle\bigcup_{a \in X} [a]_R = X\)
\([a]_R = [b]_R \Leftrightarrow a R b .\)
4.3.2. Podział zbioru#
Definicja 4.6
Podziałem zbioru \(X\) nazywamy rodzinę \(\mathcal{A}=(A_i)_{i\in I}\) podzbiorów zbioru \(X\) taką, że:
\(\forall i \in I \quad A_i \subseteq X\)
\(\forall i \in I \quad A_i \neq \emptyset\)
\(\forall i,j \in I \quad i\neq j \Rightarrow A_i \cap A_j = \emptyset\)
\(\displaystyle\bigcup_{i \in I} A_i = X .\)
Przykład 4.6
\(L\) – zbiór ludzi, \(A_1\subseteq L\) – zbiór kobiet, \(A_2\subseteq L\) – zbiór mężczyzn; wówczas \((A_1,A_2)\) jest podziałem \(L .\)
\(\zz\) – zbiór liczb całkowitych, \(A_i=\Set{3z+i : z \in \zz}\), dla \(i\in I=\Set{0,1,2}\); wówczas \((A_i)_{i\in I}\) jest podziałem \(\zz .\)
\(\mathcal{X}=2^{\Set{1,\ldots,n}}\), \(A_k=\Set{Y\in \mathcal{X} : |Y|=k}\), dla \(k\in I=\Set{0,\ldots,n}\); wówczas \((A_k)_{k\in I}\) jest podziałem \(\mathcal{X} .\)
Twierdzenie 4.2
Niech \(X\neq \emptyset .\)
Jeżeli \(R\subseteq X\times X\) jest relacją równoważności, to zbiór ilorazowy \(X/_{R}\) jest podziałem zbioru \(X .\)
Jeżeli \(\mathcal{A}=(A_i)_{i\in I}\) jest podziałem zbioru \(X\), to relacja \(R_{\mathcal{A}}\subseteq X\times X\) określona warunkiem
\[xR_{\mathcal{A}} y \qlq \exists i\in I\ \ x,y\in A_i\]jest relacją równoważności.
Narration
Innymi słowy, podziały zbioru \(X\) i relacje równoważności na \(X\) to – z dokładnością do powyższego przyporządkowania – to samo pojęcie.
Uwaga 4.1
Ta obserwacja pozwala konstruować nowe zbiory liczbowe jako zbiory ilorazowe. Na przykład:
w zbiorze \(\nn\times\nn\) relacja
\[ (p,q)\sim(k,l) \qlq p+l=q+k \]jest relacją równoważności, a zbiór ilorazowy \((\nn\times\nn)/_\sim\) utożsamiamy ze zbiorem \(\zz\) (klasę pary \((p,q)\) oznaczamy jako różnicę \(p-q\))
w zbiorze \(\zz\times(\zz\setminus\Set{0})\) relacja
\[ (p,q)\,\varrho\,(k,l) \qlq p\cdot l=q\cdot k \]jest relacją równoważności, a zbiór ilorazowy utożsamiamy ze zbiorem \(\qq\) (klasę pary \((p,q)\) oznaczamy jako ułamek \(\frac p q\)).
4.4. Relacje porządkujące#
Definicja 4.7
Relację \(\preceq \subseteq P \times P\) nazywamy porządkiem częściowym, jeśli jest zwrotna, antysymetryczna i przechodnia.
Parę \((P,\preceq)\) nazywamy wtedy zbiorem częściowo uporządkowanym (posetem).
Jeżeli w \((P,\preceq)\), dla elementów \(x, y \in P\)
to mówimy, że \(x\) jest mniejszy od \(y\) lub poprzedza \(y\), a \(y\) jest większy od \(x\) lub następuje po \(y .\)
Przykład 4.7 (Przykłady posetów)
\((\rr, \leq)\)
\((2^{X}, \subseteq)\)
\((\nn, \mid)\)
\((\rr\times\rr,\preceq)\), gdzie
\[ (x,y)\preceq (a,b) \qlq x\leq a \wedge y\leq b \]– porządek produktowy.
\((\rr\times\rr,\preceq)\), gdzie
\[ (x,y)\preceq (a,b) \qlq x< a \vee (x=a \wedge y\leq b) \]– porządek leksykograficzny.
Ćwiczenie 4.4
Sprawdźmy, że relacje \(\leq\) i \(\mid\) z Prz. 4.1 są relacjami częściowego porządku.
Rozwiązanie
Relacja mniejszości \(\leq \ = \ \Set{(x,y)\in \mathbb{R} \times \mathbb{R} : x \leq y}\):
zwrotność: \(\forall x \in \mathbb{R} \quad x = x \implies x \leq x\)
antysymetria: \(\forall x,y \in \mathbb{R} \quad (x \leq y \wedge y \leq x) \implies x = y\) (wynika bezpośrednio z własności porządku liczb rzeczywistych)
przechodniość: \(\forall x,y,z \in \mathbb{R} \quad (x \leq y \wedge y \leq z) \implies x \leq z\)
Relacja podzielności \(\mid \ = \ \Set{(x,y)\in \mathbb{N} \times \mathbb{N} : \exists k\in \mathbb{N} \quad y = k \cdot x}\):
zwrotność: \(\forall x \in \mathbb{N} \quad x = 1 \cdot x \wedge 1 \in \mathbb{N} \implies x \mid x\)
antysymetria: \(\forall x,y \in \mathbb{N} \quad (x \mid y \wedge y \mid x) \implies (y = kx \wedge x = my) \implies x = m(kx) \implies x = (mk)x \implies mk = 1.\)
Ponieważ \(m,k \in \mathbb{N}\), to \(m=k=1\), zatem \(x = y\)
przechodniość: \(\forall x,y,z \in \mathbb{N} \quad (x \mid y \wedge y \mid z) \implies (y = kx \wedge z = my) \implies z = m(kx) = (mk)x .\) Ponieważ \(mk \in \mathbb{N}\), to \(x \mid z\)
W obu przypadkach zachodzą warunki zwrotności, antysymetrii i przechodniości, więc \(\leq\) oraz \(\mid\) są relacjami częściowego porządku.
Definicja 4.8
Elementy \(x,y\in P\) nazywamy porównywalnymi (ozn. \(x\sim y\)), jeśli
W przeciwnym przypadku nazywamy je nieporównywalnymi (ozn. \(x\parallel y\)).
4.4.1. Diagram Hassego#
Definicja 4.9
Diagramem Hassego nazywamy graficzną reprezentację zbioru częściowo uporządkowanego \((P,\preceq)\), w której:
wierzchołki grafu odpowiadają elementom zbioru \(P\)
jeśli \(x\neq y\) i \(x \preceq y\), to wierzchołek \(x\) rysujemy niżej niż wierzchołek \(y\)
dwa wierzchołki \(x\neq y\) łączymy krawędzią wtedy i tylko wtedy, gdy \(x\) bezpośrednio poprzedza \(y\), tzn.
\[x \preceq y \ \wedge\ \Negation\bigl(\exists z\ \ z\neq x \wedge z\neq y \wedge x \preceq z \preceq y\bigr).\]
Przykład 4.8
Poniższy diagram obrazuje pewien poset \(\Paren{\Set{1,2,3,4,5,6,7}, \preceq} .\)
Wynika z niego na przykład, że: \(2 \preceq 3 \preceq 8\), zaś \(7\) i \(8\) NIE są ze sobą w relacji – są elementami nieporównywalnymi.
4.4.2. Elementy wyróżnione#
Narration
Niech \((P,\preceq)\) będzie zbiorem częściowo uporządkowanym.
Definicja 4.10
Element \(a \in P\) nazywamy:
maksymalnym, jeśli \(\Negation\bigl(\exists x\in P\ \ a\neq x \wedge a\preceq x\bigr)\)
minimalnym, jeśli \(\Negation\bigl(\exists x\in P\ \ a\neq x \wedge x\preceq a\bigr)\)
największym, jeśli \(\forall x\in P \ \ x \preceq a\)
najmniejszym, jeśli \(\forall x\in P \ \ a \preceq x .\)
Uwaga 4.2
Jeśli w zbiorze \((P,\preceq)\) istnieje element największy (najmniejszy), to jest on jedynym elementem maksymalnym (minimalnym).
W zbiorze \((P,\preceq)\) istnieje co najwyżej jeden element największy i co najwyżej jeden element najmniejszy.
Przykład 4.9
W posecie opisanym diagramem w Prz. 4.8:
elementy minimalne to \(1\) i \(2\) – brak elementu najmniejszego (bo \(1\) i \(2\) są nieporównywalne)
elementy maksymalne to \(7\) i \(8\) – brak elementu największego.
W posecie \((\nn, \mid)\):
\(1\) jest elementem minimalnym i zarazem najmniejszym
nie ma elementów maksymalnych, a zatem największego.
W posecie \((\nn_2 = \nn\setminus\Set{1}, \mid)\):
każda liczba pierwsza jest elementem minimalnym, więc nie ma elementu najmniejszego
nie ma elementów maksymalnych, a zatem największego.
4.4.3. Ograniczenia i kresy#
Narration
Niech \((P,\preceq)\) będzie zbiorem częściowo uporządkowanym i niech \(X\subseteq P .\)
Definicja 4.11
Element \(a\in P\) jest ograniczeniem górnym zbioru \(X\), jeśli
Element \(b\in P\) jest ograniczeniem dolnym zbioru \(X\), jeśli
Zbiory wszystkich ograniczeń górnych i dolnych \(X\) oznaczamy odpowiednio
Element \(a\in P\) jest kresem górnym zbioru \(X\) (ozn. \(\sup X\)), jeśli jest elementem najmniejszym w zbiorze \((X^*,\preceq) .\)
Element \(a\in P\) jest kresem dolnym zbioru \(X\) (ozn. \(\inf X\)), jeśli jest elementem największym w zbiorze \((X_*,\preceq) .\)
Przykład 4.10
W posecie opisanym diagramem w Prz. 4.8:
\[\begin{split}\begin{aligned} \Set{3}^* & = \Set{3,7,8}, & \Set{3}_* & = \Set{1,2,3}, \\ \Set{4}^* & = \Set{4,6,7,8}, & \Set{4}_* & = \Set{1,4}. \end{aligned}\end{split}\]Dla \(X=\Set{3,4}\) mamy \(X^* = \Set{3,7,8}\cap\Set{4,6,7,8} = \Set{7,8} .\)
Ponieważ \(7\) i \(8\) są nieporównywalne, zbiór \((X^*,\preceq)\) nie ma elementu najmniejszego, więc \(\sup X\) nie istnieje.
Z drugiej strony \(X_* = \Set{1,2,3}\cap\Set{1,4} = \Set{1}\), a więc \(\inf X = 1\).
W posecie \((\nn,\mid)\), dla \(X=\Set{6,8,12}\), mamy \(\sup X = \mathrm{NWW}(6,8,12)=24\) oraz \(\inf X = \NWD(6,8,12)=2 .\)
W posecie \((2^{X},\subseteq)\), dla rodziny \(\mathcal{C}=\Set{A_i\subseteq X : i\in I}\), mamy
\[\sup \mathcal{C}=\bigcup_{i \in I}A_i, \qquad \inf \mathcal{C}=\bigcap_{i \in I}A_i.\]
Ćwiczenie 4.5
Korzystając z diagramu Hassego z poprzedniego punktu, znajdźmy \(\Set{4,5}^*\), \(\Set{4,5}_*\) oraz – o ile istnieją – \(\sup\Set{4,5}\) i \(\inf\Set{4,5} .\)
Odpowiedź
Ponieważ \(6\) jest najmniejszym elementem zbioru \(\Set{6,7,8}\) (bo \(6\preceq 7\) i \(6 \preceq 8\)), to \(\sup\Set{4,5}=6 .\) Zbiór \(\Set{4,5}_*=\Set{1}\) ma jeden element, więc \(\inf\Set{4,5}=1 .\)
4.4.4. Łańcuchy i antyłańcuchy#
Definicja 4.12
Podzbiór \(C \subseteq P\) nazywamy łańcuchem, jeśli
Podzbiór \(D \subseteq P\) nazywamy antyłańcuchem, jeśli
Przykład 4.11
W posecie opisanym diagramem w Prz. 4.8:
ciąg \(2\preceq 5\preceq 6 \preceq 7\) tworzy łańcuch
zbiór \(\Set{3,4,5}\) jest antyłańcuchem (elementy \(3,4,5\) są parami nieporównywalne).
Stwierdzenie 4.3
W skończonym, niepustym zbiorze częściowo uporządkowanym istnieje element maksymalny i element minimalny.
Narration
To dość oczywiste stwierdzenie przestaje być oczywisty dla zbiorów nieskończonych. Jego uogólnieniem jest poniższy, fundamentalny dla matematyki lemat.
Twierdzenie 4.4 (Lemat Kuratowskiego–Zorna)
Jeżeli \((P,\preceq)\) jest niepustym zbiorem częściowo uporządkowanym, w którym każdy łańcuch \(C\subseteq P\) ma ograniczenie górne (tzn. \(C^*\neq\emptyset\)), to w zbiorze \((P,\preceq)\) istnieje element maksymalny.
Analogicznie, jeśli każdy łańcuch ma ograniczenie dolne, to istnieje element minimalny.
Uwaga 4.3
Lemat Kuratowskiego–Zorna jest równoważny aksjomatowi wyboru (a więc sam bywa przyjmowany jako aksjomat teorii mnogości) – jego dowodu nie da się przeprowadzić bez odwołania się do niego lub równoważnego mu stwierdzenia.
Lemat ten jest podstawowym narzędziem dowodzenia istnienia obiektów maksymalnych, których nie potrafimy skonstruować jawnie – np. istnienia bazy w dowolnej przestrzeni wektorowej (także nieskończenie wymiarowej) czy istnienia ideału maksymalnego w pierścieniu z jedynką.
4.5. Funkcja jako relacja#
Uwaga 4.4
Funkcję \(f\colon X\to Y\) możemy formalnie utożsamić z relacją \(f\subseteq X\times Y\) spełniającą warunek
czyli relacją jednoznaczną (każdemu \(x\) odpowiada co najwyżej jeden \(y\)) i określoną na całym \(X\) (każdemu \(x\) odpowiada co najmniej jeden \(y\)).