Na tym wykładzie omówimy raz jeszcze iloczyn kartezjański zbiorów, relacje, dziedzinę, przeciwdziedzinę i składanie relacji, relację odwrotną, pewne własności relacji (zwrotność, przechodniość etc).
Przypomnijmy z poprzedniego wykładu, że parą uporządkowaną \((a,b)\) nazywamy zbiór \(\{\{a\},\{a,b\}\}\). Jednym z pierwszych matematyków, którzy podali formalną definicję pary był Kazimierz Kuratowski.
Przypomnijmy, że iloczynem kartezjańskim zbiorów \(X\) i \(Y\) nazywamy zbiór
\[X\times Y:=\{(x,y): x\in X,y\in Y\}.\]
Nazwa „iloczyn kartezjański” pochodzi od francuskiego matematyka, René Descartesa, którego spolszczone nazwisko to Kartezjusz1.
Poniższe stwierdzenie podaje pewne własności iloczynu kartezjańskiego.
Stwierdzenie 46. Niech \(X,Y,X_1,X_2,Y_1,Y_2\) będą zbiorami.
1. \((X_1\cup X_2)\times Y=(X_1\times Y)\cup (X_2\times Y)\).
2. \(X\times (Y_1\cup Y_2)=(X\times Y_1)\cup ( X\times Y_2)\).
3. \((X_1\setminus X_2)\times Y=(X_1\times Y)\setminus (X_2\times Y)\).
4. \((X_1\cap X_2)\times (Y_1\cap Y_2)=(X_1\cap Y_1)\times (X_2\cap Y_2)\).
5. Jeśli \(X_1,X_2,Y_1,Y_2\) są niepuste, to \((X_1\times Y_1=X_2\times Y_2) \iff (X_1=X_2\wedge Y_1=Y_2)\).
Dowód. Dla każdego z przypadków \(1\)–\(4\) wykażemy, że para \((a,b)\) należy do lewej strony równości wtedy i tylko wtedy gdy należy do prawej. Podczas dowodu korzystamy z odpowiednich praw dla działań logicznych.
ad 1. \((a,b)\in (X_1\cup X_2)\times Y)\iff a\in (X_1\cup X_2)\wedge (b\in Y)\iff (a\in X_1\vee a\in X_2)\wedge (b\in Y)\stackrel {{\textrm {\tiny \ref {stw-tautologie}.9}} }{\iff } (a\in X_1\wedge b\in Y)\vee (a\in X_2\wedge b\in Y)\iff (a,b)\in X_1\times Y\vee (a,b)\in X_2\times Y\iff (a,b)\in (X_1\times Y)\cup (X_2\times Y).\)
ad 2. \((a,b)\in X\times (Y_1\cup Y_2)\iff (a\in X)\wedge (b\in Y_1\cup Y_2)\iff (a\in X)\wedge (b\in Y_1\vee b\in Y_2) \stackrel {{\textrm {\tiny \ref {stw-tautologie}.9}} }{\iff }(a\in X\wedge b\in Y_1)\vee (a\in X\wedge b\in Y_2)\iff (a,b)\in (X\times Y_1)\cup ( X\times Y_2).\)
ad 3. \((a,b)\in (X_1\setminus X_2)\times Y\iff (a\in X_1\setminus X_2)\wedge b\in Y\iff (a\in X_1\wedge \neg (a\in X_2))\wedge b\in Y\iff (a\in X_1 \wedge b\in Y)\wedge (\neg (a\in X_2))\stackrel {*}{\iff } ((a\in X_1 \wedge b\in Y)\wedge (\neg (a\in X_2)))\vee (a\in X_1\wedge b\in Y \wedge \neg (b\in Y)) \stackrel {{\textrm {\tiny \ref {stw-tautologie}.9}} }{\iff } a\in X_1\wedge b\in Y \wedge (\neg (a\in X_2)\vee \neg (b\in Y)) \iff (a,b)\in X_1\times Y\wedge \neg ((a,b)\in X_2\times Y)\iff (a,b)\in (X_1\times Y)\setminus (X_2\times Y)\), gdzie równoważność \(*\) wynika z faktu, że zdanie \((a\in X_1\wedge b\in Y \wedge \neg (b\in Y)) \) jest zawsze fałszywe.
ad 4. \((a,b)\in (X_1\cap X_2)\times (Y_1\cap Y_2)\iff (a\in X_1\cap X_2)\wedge (b\in Y_1\cap Y_2)\iff (a\in X_1\wedge a\in X_2)\wedge (b\in Y_1\wedge b\in Y_2)\iff (a\in X_1\wedge b\in Y_1)\wedge (a\in X_2\wedge b\in Y_2)\iff (a,b)\in X_1\times Y_1\wedge (a,b)\in X_2\times Y_2\iff (a,b)\in (X_1\cap Y_1)\times (X_2\cap Y_2)\).
ad 5. Wynikanie \((\Longleftarrow )\) jest oczywiste. Wynikanie \((\Longrightarrow )\): Skoro oba iloczyny kartezjańskie są równe (i niepuste) to \((a,b)\in X_1\times Y_1 \iff (a,b)\in X_2\times Y_2\) czyli \(a\in X_1 \wedge b\in Y_1 \iff a\in X_2 \wedge b\in Y_2\) czyli \(a\in X_1\iff a\in X_2 \) oraz \(b\in Y_1\iff b\in Y_2\), a stąd mamy żądaną równość zbiorów.
Zauważmy, że pisząc „czyli” powyżej, korzystamy z wynikania (w dwie strony) \(((p\wedge q)\lra (r\wedge s))\lra ((p\lra s)\wedge (q\lra r))\), które zachodzi, gdy wszystkie zdania są prawdziwe. Tu właśnie wykorzystujemy fakt, że zbiory są niepuste, zatem np. \(a\in X_1\) jest zdaniem prawdziwym. □
Zdefiniujemy teraz pojęcie ogólniejsze niż pojęcie pary – pojęcie \(s\)-ki uporządkowanej. Podamy definicję rekurencyjną (choć formalnie ten sposób definiowania pojawi się później na wykładzie).
Definicja 47 (\(s\)-ka uporządkowana). Niech \(s\in \mathbb {N}, s\geq 2\) i niech dane będą elementy \(a_1,\dots ,a_s\) (niekoniecznie różne) pewnego zbioru \(A\). Dla \(s=2\) \(s\)-ka uporządkowana jest parą uporządkowaną \((a_1,a_2)\). Załóżmy, że mamy zdefiniowaną \((s-1)\)-tkę uporządkowaną \((a_1,\dots , a_{s-1})\) dla pewnego \(s>2\). Wtedy \(s\)-kę uporządkowaną definiujemy jako \((a_1,\dots ,a_s):= ((a_1,\dots ,a_{s-1}),a_s)\).
Niech teraz \(X_1,\dots ,X_s\) będą zbiorami.
Uwaga 49. Jeśli wszystkie zbiory \(X_1,\dots ,X_s\) są równe pewnemu zbiorowi \(X\) to stosujemy
zapis \(\underbrace {X\times \cdots \times X}_\text {$s$ razy} =X^s\).
Zapis ten jest zapewne wszystkim znany w przypadku \(\mathbb {R}^2=\mathbb {R}\times \mathbb {R}\) albo \(\mathbb {R}^3=\mathbb {R}\times \mathbb {R}\times \mathbb {R}\).
Gdy mamy indeksowaną rodzinę zbiorów, możemy wprowadzić pojęcie uogólnionego iloczynu kartezjańskiego.
Definicja 50. Niech \(\{ F_t, t\in T\}\) będzie indeksowaną rodziną zbiorów, niech \(Y=\bigcup _{t\in T}F_t\). Uogólniony iloczyn kartezjański definiujemy następująco:
\[\prod _{t\in T}F_t:=\{f:T\to Y : f(t)\in F_t \}.\]
Uwaga 51. Łatwo zauważyć, że gdy zbiór \(T\) jest zbiorem \(\{1,\dots , s\}\)
powyższa definicja jest równoważna z Definicją 48.
Weźmy w szczególności \(T=\{1,2\}\) i niech \(F_1,F_2\subset Y\) i weźmy funkcje \(f:\{1,2\}\to Y\) spełniające warunek \(f(1)\in F_1, f(2)\in F_2\). Elementy iloczynu kartezjańskiego \((a_1,a_2)\in F_1\times
F_2\) możemy traktować jako pary \((a_1,a_2)\), gdzie \(a_1\in F_1, a_2\in F_2\) lub też jako funkcje \(f: T\to Y\) spełniające warunek \(a_1:=f(1)\in F_1, a_2:=f(2)\in F_2\).
Przejdziemy teraz do definicji relacji. Niech dane będą zbiory \(X_1\), \(X_2, \dots , X_m\).
Definicja 52. Relacją (dwuargumentową) nazywamy dowolny podzbiór \(R\) iloczynu kartezjańskiego \(X_1\times
X_2\).
Podzbiór iloczynu kartezjańskiego \(m\) zbiorów \(X_1\times \dots \times X_m\) nazywamy relacją \(m\)-argumentową.
Dla relacji dwuargumentowej \(R\) i pary \((x_1,x_2)\in R\) stosujemy też zapis \(x_1\relR x_2\). Mówimy wtedy, że \(x_1\) jest w relacji \(R\) z \(x_2\). Relacje oznaczamy też literami \(S\),
\(T\) albo jako \(R_1,R_2,\dots \).
Przykład 53.
\(\bullet \) Niech \(X_1=X_2=\mathbb {R}\). Określamy podzbiór \(S\subset \mathbb {R}^2\) następująco: \(S=\{(x,y)\in \mathbb {R}^2: x^2+y^2=2 \}\). Jak widać, \(x\) jest w relacji \(S\) z \(y\) wtedy i tylko wtedy, gdy punkt \((x,y)\) leży na okręgu o promieniu \(\sqrt {2}\), zobacz Rysunek 4.1.
\(\bullet \) Niech \(X_1=X_2=\mathbb {N}\). Określamy podzbiór \(R\subset \mathbb {N}^2 \) następująco: \(R=\{(x,y)\in \mathbb {N}^2: x|y \}\), gdzie zapis \(x|y\) oznacza, że \(x\) dzieli \(y\). Mamy wówczas \(2\relR 4\) ale \((4,2)\notin R\), tak samo \((5,12)\notin R\).
\(\bullet \) Niech \(X_1=X_2=\mathbb {R}\). Określamy podzbiór \(S\subset \mathbb {R}^2\) następująco: \(S=\{(x,y)\in \mathbb {R}^2: y-x^2\geq 0 \}\). Para \((x,y) \) jest w relacji \(R\) gdy punkt \((x,y)\) leży na wykresie albo nad wykresem paraboli \(y=x^2\) (środkowy rysunek).
\(\bullet \) Zbiór z prawej na Rysunku 4.1 także przedstawia relację w \(\mathbb {R}^2\).
\(\bullet \) Czytelnikowi znane są też zapewne relacje równoległości prostych albo podobieństwa trójkątów, omówimy je dokładniej na dalszych wykładach.
Rysunek 4.1:
Definicja 54 (Dziedzina i przeciwdziedzina relacji). Dziedziną relacji \(R\subset X_1\times X_2\) nazywamy zbiór
\[\Dom _R:=\{x_1\in X_1:\exists _{x_2\in X_2} \ x_1\relR x_2\}.\]
Przeciwdziedziną relacji \(R\subset X_1\times X_2\) nazywamy zbiór
\[\Dom ^*_R:=\{x_2\in X_2:\exists _{x_1\in X_1} \ x_1\relR x_2\}.\]
Przykład 55. Niech \(X_1=\{2,3,5\}, X_2=\{4,6,7\}\). Niech \(x\relR y\iff x|y\). Wówczas \(R=\{(2,4),(2,6),(3,6)\}\), \(\Dom _R=\{2,3\}\), \(\Dom ^*_R=\{4,6\}\).
Zdefiniujemy teraz złożenie relacji, i wykażemy, że składanie relacji jest działaniem łącznym. Niech zatem \(X_1,X_2,X_3\) będą zbiorami, niech \(R_1\subset X_1\times X_2\) i \(R_2\subset X_2\times X_3\).
Definicja 57. Złożeniem relacji \(R_1\) z relacją \(R_2\) nazywamy relację \(R_2\circ R_1\subset X_1\times X_3\), zdefiniowaną jako zbiór
\[R_2\circ R_1:=\{(x_1,x_3)\in X_1\times X_3 : \exists _{x_2\in X_2} \ (x_1,x_2)\in R_1 \wedge (x_2,x_3)\in R_2\}.\]
Warto zwrócić uwagę na kolejność zapisu składanych relacji i fakt, że niektórych podręcznikach \(R_2\circ R_1\) nazywa się złożeniem \(R_2\) z \(R_1\).
Przykład 58. Rozpatrzmy następującą, dość szczególną, sytuację. Niech \(X_1=X_2=X_3=\mathbb {R}\), niech \(R_1=R_2=R\), gdzie \(R=\{(x,y)\in \mathbb {R}^2: y=x^2 \}\). Wtedy \(R\circ R=\{ (x,z)\in \mathbb {R}^2: \exists _y : x\relR y \wedge y\relR z\}\), co oznacza, że \((x,z)\in R\circ R\) jeśli istnieje \(y\) takie, że \(y=x^2\) oraz \(z=y^2\), a stąd mamy, że \((x,z)\in R\circ R\) wtedy i tylko wtedy gdy \(z=x^4\).
Więcej o składaniu relacji powiemy przy okazji składania funkcji.
Teraz wykażemy następujące stwierdzenie, mówiące, że składanie relacji jest łączne. Warto to twierdzenie zapamiętać, bo mówi w szczególności, że składanie funkcji jest działaniem łącznym. Przydaje się także na Algebrze Liniowej, jako jedna z możliwości wykazania łączności mnożenia macierzy.
Dowód. Niech \((x_1,x_4)\in (R_3\circ R_2)\circ R_1\). Mamy, wykorzystując definicję złożenia następujący ciąg równoważności:
\((x_1,x_4)\in (R_3\circ R_2)\circ R_1\iff \exists _{x_2\in X_2} : (x_1,x_2)\in R_1 \wedge (x_2,x_4)\in R_3\circ R_2 \iff \exists _{x_2\in X_2} : (x_1,x_2)\in R_1 \wedge \exists _{x_3\in X_3} (x_2,x_3)\in
R_2\wedge (x_3,x_4)\in R_3\iff \exists _{x_3\in X_3} (x_3,x_4)\in R_3\wedge \exists _{x_2\in X_2} (x_1,x_2)\in R_1\wedge (x_2,x_3)\in R_2\iff \exists _{x_3\in X_3} (x_3,x_4)\in R_3\wedge (x_1,x_3)\in R_2\circ
R_1\iff (x_1,x_4)\in R_3\circ (R_2\circ R_1). \)
□
Dla danej relacji \(R\subset X_1\times X_2\) wprowadzimy pojęcie relacji odwrotnej.
Przykład 61. Niech \(X_1=X_2=\mathbb {R}.\)
1. Niech \(x\relR y\iff y=x+2\). Wówczas \(R^{-1}=\{ (y,x): y=x+2\}=\{(x+2,x),x\in \mathbb {R}\}=\{ (x,x-2)\in \mathbb {R}^2\}\).
2. Niech \(x\relR y\iff y=x^2\). Wówczas \(R^{-1}=\{ (y,x): y=x^2\}=\{(x^2,x),x\in \mathbb {R}\}=\{ (x,\pm \sqrt {x}): x\geq 0\}\).
Skupimy się teraz na sytuacji gdy relacja \(R\) jest podzbiorem \(X\times X\).
Przykład 63. Relacja podzielności w liczbach naturalnych (\(X=\mathbb {N},x\relR y\iff
x|y\)) jest relacją zwrotną bo każda liczba naturalna dzieli samą siebie (liczby naturalne rozważamy bez zera).
Relacja równoległości prostych na płaszczyźnie (dwie proste są w relacji jeśli są do siebie równoległe, czyli albo nie mają punktów wspólnych albo mają wszystkie punkty wspólne) jest relacją zwrotną (bo każda prosta jest równoległa
do siebie).
Relacja „\(<\)” dla liczb rzeczywistych nie jest relacją zwrotną.
Przykład 65.
Relacja „\(<\)” dla liczb rzeczywistych (\(x\relR y \iff x<y\)) jest relacją przeciwzwrotną.
Przykład 67.
Relacja równoległości prostych na płaszczyźnie jest relacją symetryczną.
Przykład 69.
Relacja „\(<\)” dla liczb rzeczywistych jest relacją antysymetryczną.
Przykład 71. Relacja podzielności w liczbach naturalnych jest relacją słabo antysymetryczną bo
jeśli \(x|y \wedge y|x\) to mamy \(x=y\) (ćwiczenie).
Relacja „\(\leq \)” dla liczb rzeczywistych (\(x\relR y \iff x\leq y\)) jest relacją słabo antysymetryczną (bo \(x\leq y \wedge y\leq x \lra x=y\)).
Warto zauważyć, że relacja „\(<\)” dla liczb rzeczywistych jest też relacją słabo antysymetryczną, bo warunek \(x\relR y\wedge y\relR x\) jest zawsze fałszywy, zatem implikacja \((x\relR y\wedge y\relR
x)\lra x=y\) jest prawdziwa. Analogiczne rozumowanie pozwala ogólnie wykazać, że relacja antysymetryczna jest też słabo antysymetryczna.
Przykład 73. Relacja podzielności w liczbach naturalnych jest relacją przechodnią (bo łatwo
sprawdzić (ćwiczenie), że jeśli \(x|y \wedge y|z\) to \(x|z\).)
Relacja równoległości prostych na płaszczyźnie jest relacją przechodnią
Przykład 75. Spójność relacji oznacza, że każde dwa elementy zbioru \(X\) są ze
sobą w relacji, ewentualnie są sobie równe.
Relacja podzielności w liczbach naturalnych nie jest relacją spójną (wystarczy np. rozważyć elementy \(5\) i \(7\).)
Relacja \(< \) w \(\mathbb {R}\) jest relacją spójną (dla każdych dwóch liczb rzeczywistych \(x,y\) albo \(x<y\) albo \(y<x\) albo \(y=x\)).
1 René Descartes (1596–1650), francuski filozof, matematyk i fizyk.