Niech [math]a,b[/math] będą dowolnymi elementami (zbiorami). Przez parę uporządkowaną [math]\left( a,b\right)[/math] rozumiemy zbiór [math]\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}.[/math]
Uwaga: [math]\left( a,a\right) =\left\{ \left\{ a\right\},\left\{ a,a\right\} \right\}=\left\{ \left\{ a\right\},\left\{ a \right\}\right\}=\left\{ \left\{ a\right\} \right\}.[/math]
Parę uporządkowaną można też zdefiniować w inny sposób. Chodzi jednak o to, by dla takich par spełniona była własność zapowiedziana w pierwszym rozdziale, która mówi, że jeśli jedna para uporządkowana różni się od drugiej pary, choć na pierwszej czy choć na drugiej współrzędnej, to te pary uporządkowane są różne. A więc pokażemy, że przy naszej definicji pary uporządkowanej, zachodzi:
Twierdzenie 1. Dla dowolnych [math]a,b,c,d[/math], mamy:
[math]\left( a,b\right)=\left( c,d\right) \Longleftrightarrow \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}\Longleftrightarrow a=c \wedge b=d.[/math]
Oczywiście pierwsza równoważność to tylko zastosowanie definicji, interesuje nas druga równoważność, a w zasadzie implikacja [math]\Longrightarrow[/math].
Dowód: Załóżmy zatem, że [math]\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}.[/math]
Mamy [math]\left\{ a\right\} \in \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}[/math], więc [math]\left\{ a\right\} \in \left\{ \left\{ c\right\},\left\{ c,d\right\} \right\}[/math], a więc [math]\left\{ a\right\}=\left\{ c\right\}[/math] lub [math]\left\{ a\right\}=\left\{ c,d\right\}[/math]. W pierwszym przypadku [math]a=c[/math], ale w drugim również jest tak, mamy bowiem, z zasady równości zbiorów , że [math]c \in \left\{a\right\}[/math], a więc [math]c=a[/math]. Wiemy już, ze pierwsze współrzędne równych par są równe:
[math]\left( a,b\right)=\left( a,d\right)[/math]
Dalej przeprowadzimy dowód przez rozważenie przypadków.
Jeżeli [math]a=b[/math], to [math]\left( a,b\right)=\left( a,a\right)=\left\{ \left\{ a\right\} \right\}[/math], zatem [math]\left( a,d\right)=\left( a,b\right)=\left\{ \left\{ a\right\} \right\}[/math], więc ponieważ [math]\left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\} =\left\{ \left\{ a\right\} \right\}[/math], to z zasady równości zbiorów [math]\left\{ a,d\right\} \in \left\{ \left\{ a\right\} \right\}[/math], a więc [math]\left\{ a,d\right\}=\left\{ a\right\}[/math] , i dalej podobnie [math]d=a=b[/math], czyli [math]d=b[/math], co należało pokazać.
W przeciwnym przypadku, gdy [math]a \neq b[/math], to wtedy [math]\left( a,b\right)=\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\}[/math]. Ponieważ [math]\left\{ a,b\right\} \in \left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}[/math], więc [math]\left\{ a,b\right\} \in \left( a,d\right)=\left\{ \left\{ a\right\},\left\{ a,d\right\} \right\}[/math]. Daje to dwie możliwości: albo [math]\left\{ a,b\right\}=\left\{ a\right\}[/math], co prowadzi do [math]b=a[/math]-sprzeczność. Musi więc zajść drugi przypadek [math]\left\{ a,b\right\} =\left\{ a,d\right\}[/math], co daje [math]b\in \left\{ a,d\right\}[/math], i ponieważ [math]b \neq a[/math] to [math]b=d[/math], co należało pokazać.
Dowód [math]\Longleftarrow[/math] jest oczywisty, teza wynika wprost z założeń i zasady równości zbiorów.[math]\square[/math]
Ćwiczenie 2. Dla każdej pary uporządkowanej [math]x=\left( a,b\right)[/math], udowodnij, że [math]\bigcap\bigcap x=a.[/math]
To ćwiczenie ma bardziej charakter formalny. Przypomnijmy bowiem, że jedynymi przez nas rozważanymi obiektami (bytami) są zbiory. Wobec czego para uporządkowana [math]x=\left( a,b\right)[/math] jest zbiorem ( patrz definicja na początku tego rozdziału), jest to zbiór złożony ze zbiorów, bo elementy zbiorów są również zbiorami, więc możemy utworzyć iloczyn rodziny [math]x=\left( a,b\right)[/math], otrzymując zbiór [math]\bigcap x[/math]- znowu zbiór złożony ze zbiorów, i wtedy iloczyn takiej rodziny zbiorów [math]\bigcap\mathbb{A}[/math], gdzie [math]\mathbb{A}=\bigcap x[/math] ma być równe zbiorowi [math]a[/math] ( współrzędne par uporządkowanych są również zbiorami).
Rozwiązanie: [math]\bigcap \left(x=\left( a,b\right) =\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}\right)=\bigcap\left\{ \left\{ a\right\},\left\{ a,b\right\} \right\}=\left\{ a\right\} \cap \left\{ a,b\right\}=\left\{ a\right\}.[/math]
Zatem [math]\bigcap\bigcap x=\bigcap\left\{ a\right\}=a.[/math]
Pojęcie pary uporządkowanej jest potrzebne do wprowadzenia iloczynu kartezjańskiego, a potem relacji.
Iloczyn kartezjański
Iloczynem kartezjańskim zbiorów [math]X,Y[/math], to zbiór [math] X\times Y=\left\{\left( x,y\right)\Bigl| \ x\in X, y\in Y\right\}.[/math]
Czyli jest to zbiór wszystkich par uporządkowanych elementów kolejnych zbiorów [math]X,Y[/math]. Np. [math]\left( 1,2\right) ,\left( 2,2\right),\left( 2,1\right) \in \left[ 0,2\right] \times \left[ 1,2\right].[/math] Graficzną ilustracją iloczynu kartezjańskiego jest prostokąt- zobacz ilustracje obok. Na ogół [math]X\times Y\neq Y\times X[/math]- aby się o tym przekonać wyznacz np. [math]\left[ 0,1\right] \times \left[ 0,2\right][/math] i [math]\left[ 0,2\right] \times \left[ 0,1\right].[/math]
Podstawowe własności iloczynu kartezjańskiego:
Twierdzenie 1.1. Dla dowolnych zbiorów [math]X,Y,Z[/math]:
[math]1. \ X\times\left\{ \right\} =\left\{ \right\} =\left\{ \right\} \times X. \\
2. \ X\times\left( Y\cup Z\right)=\left( X\times Y\right) \cup \left( X\times Z\right), \ \ \left( X\cup Y\right)\times Z=\left( X\times Z\right) \cup \left( Y\times Z\right). \\
3. \ X\times\left( Y\cap Z\right)=\left( X\times Y\right) \cap \left( X\times Z\right). \\
4. \ X\times\left( Y\setminus Z\right)=\left( X\times Y\right) \setminus \left( X\times Z\right). [/math]
Dowód:
1. Nie wprost. Gdyby iloczyn kartezjański [math]X\times\left\{ \right\}[/math] byłby niepusty, to istniałaby para [math]\left( x,a\right) \in X\times\left\{ \right\}[/math], a więc wtedy [math]x\in X[/math] i [math]a\in\left\{ \right\}[/math], a zbiór pusty nie posiada elementów, a [math]a[/math] świadczy o tym, że posiada- sprzeczność. Dowód drugiej równości jest analogiczny. [math]\square[/math]
Nim przejdziemy do dalszych dowodów. potrzebny będzie nam następujący prosty fakt: dla dowolnych [math]a,b[/math] oraz dowolnych zbiorów [math]A,B[/math], mamy:
[math]\left( a,b\right) \in A\times B \Longleftrightarrow a\in A \wedge b\in B.[/math]
Wynika to z definicji iloczynu kartezjańskiego. Jedyne, co wymaga krótkiego uzasadnienia, to wynikanie [math]\Longrightarrow.[/math]
Jeżeli [math]\left( a,b\right) \in A\times B [/math], to [math]\left( a,b\right)=\left( c,d\right)[/math], gdzie [math]c\in A, d\in B[/math]. Wtedy jednak z twierdzenia 1, mamy [math]a=c\in A[/math] i [math]b=d\in B[/math], czyli [math]a\in A[/math] i [math]b\in B[/math].
Przechodzimy do dowodu punktu 2.
Ponieważ obydwa zbiory są zbiorami par uporządkowanych, więc wykażemy, że dowolna para należy do jednego zbioru wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę [math]\left( a,b\right)[/math], wtedy na podstawie wprowadzonej własności i definicji sumy dwóch zbiorów:
[math] (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 \left( X\times Y\right) \cup \left( X\times Z\right). [/math]
Zatem, (patrz komentarz początek) [math]X\times\left( Y\cup Z\right)=\left( X\times Y\right) \cup \left( X\times Z\right).[/math] Dowód drugiej równości jest analogiczny. [math]\square[/math]
3. Ponieważ obydwa zbiory są zbiorami par uporządkowanych, więc znowu wykażemy, że dowolna para należy do jednego zbioru wtedy i tylko wtedy, gdy należy do drugiego. Weźmy dowolną parę [math](a,b)[/math], wtedy:
[math] (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 \left( X\times Y\right) \cap \left( X\times Z\right),[/math]
co należało otrzymać.
4. Na tej samej zasadzie co poprzednio, weźmy dowolną parę [math](a,b)[/math]. Wtedy:
[math] (a,b) \in (X \times Y) \setminus (X \times Z) \Leftrightarrow (a,b) \in (X \times Y)\wedge (a,b) \notin (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\wedge b\notin Z)\Leftrightarrow\\ a\in X \wedge (b\in Y \setminus Z) \Leftrightarrow (a,b) \in X \times (Y \setminus Z), [/math]
co należało otrzymać. Dowód jest zakończony. [math]\square[/math]
Fakt 1.2. Dla dowolnych zbiorów [math]A,B,C,D[/math], mamy:
[math]A\subset B \wedge C\subset D \Longrightarrow A\times C\subset B\times D.[/math]
Czyli jeden iloczyn kartezjański [math]A\times C[/math] będzie się zawierać w drugim iloczynie kartezjańskim [math]B\times D[/math], jeśli tylko ten mniejszy (pod względem inkluzji) iloczyn kartezjański ma mniejsze odpowiednie składowe- czyli gdy zbiór [math]A[/math] mniejszy jest od [math]B[/math], i [math]C[/math] mniejszy jest od [math]D[/math]- to wtedy iloczyn kartezjański mniejszych zbiorów jest mniejszy od odpowiedniego mu iloczynu kartezjańskiego większych zbiorów (mniejszy,większy należy rozumieć jako słabo mniejszy,słabo większy- dopuszczamy równość zbiorów).
Dowód: Zakładamy, że [math]A\subset B[/math] i [math]C\subset D[/math], chcemy pokazać, że [math]A\times C\subset B\times D.[/math] Niech [math]\left( x,y\right)\in A\times C.[/math] Zatem [math]x[/math] należy do zbioru [math]A[/math], [math]y[/math] należy do [math]C[/math]. Ponieważ z założenia [math]A\subset B[/math], to [math]x[/math] należy do [math]B[/math]. Podobnie, ponieważ [math]C\subset D[/math], to [math]y[/math] należy do [math]D[/math]. Z tych dwóch ostatnich wniosków otrzymujemy, że [math]\left( x,y\right)\in B\times D.[/math] Zatem [math]A\times C\subset B\times D.\square[/math]
Szczególnym przypadkiem powyższego twierdzenia, jest fakt, że dla dowolnych zbiorów [math]A,B,C[/math], mamy:
[math]A\subset B \Longrightarrow A\times C\subset B\times C.[/math]
Aby to udowodnić, weźmy dowolne zbiory [math]A,B,C[/math], takie, że [math]A\subset B[/math]. Stosujemy ten Fakt 1.2. do tych samych zbiorów, i zbioru [math]D=C[/math]. Ponieważ mamy, że [math]A\subset B[/math], i [math]C\subset D=C[/math], to stosując ten fakt dostajemy, że [math]A\times C\subset B\times C.\square[/math]
Podobnie szczególnym przypadkiem tego Faktu 1.2., jest fakt, że dla dowolnych zbiorów [math]A,B,C[/math], mamy:
[math]A\subset B \Longrightarrow C\times A\subset C\times B.[/math]
Dokładana konstrukcja iloczynu kartezjańskiego została omówiona w dodatku dla dociekliwych Dla dociekliwych, gdzie została przedstawiona konstrukcja zgodna z aksjomatem wycinania.
Nim przejdziemy dalej do tematu relacji odnotujmy jeszcze zapomniane dwa proste fakty. Pierwszy mówi, że dla dowolnych zbiorów [math]A,B.C,D,[/math] mamy:
[math]A\subset B \wedge C\subset D \Longrightarrow A\cup C\subset B\cup D.[/math]
Czyli, że suma większych zbiorów (pod względem inkluzji) jest większa. Prosty dowód (trzeba tylko rozważyć dwa przypadki ze względu na przynależność do sumy) pozostawiamy czytelnikowi.
Drugi prosty fakt jest podobny- dotyczy tylko iloczynu. Dla dowolnych zbiorów [math]A,B.C,D,[/math] mamy:
[math]A\subset B \wedge C\subset D \Longrightarrow A\cap C\subset B\cap D.[/math]
Czyli iloczyn większych zbiorów jest większy. Dowód czytelnikowi nie nastręczy trudności.
Relacje
Podstawowym pojęciem (i fundamentalnym) teorii mnogości jest pojęcie relacji.
Niech [math]X,Y[/math] będą zbiorami. Relacją między zbiorami [math]X[/math] a [math]Y[/math], nazywamy każdy podzbiór [math]R\subset X\times Y.[/math]
Czyli tworzymy najpierw iloczyn kartezjański [math]X\times Y[/math], każdy podzbiór tego zbioru to przykład relacji między [math]X[/math] a [math]Y[/math]. Zobacz ilustrację obok.
Ważne relacje:
[math]\emptyset-[/math] relacja pusta( zbiór pusty jest podzbiorem każdego zbioru).
[math]X\times Y[/math]- relacja pełna (każdy zbiór jest podzbiorem swoim własnym, więc również spełnia to iloczyn [math]X\times Y[/math]).
Relacją w zbiorze [math]X[/math] , nazywamy każdy podzbiór [math]R\subset X\times X.[/math]
Przykładem znowu może być relacja pusta, relacja totalna [math]X\times X[/math], ale również:
[math]I_{X}=\left\{ \left( x,y\right) \in X\times X\Bigl| \ \ x=y\right\}.[/math] Relacja identyczności- dwa elementy są w relacji gdy są identyczne, równe.
Gdy [math]\left( x,y\right) \in R[/math], gdzie [math]x\in X, y\in Y[/math], to mówimy, że elementy [math]x,y[/math] są ze sobą w relacji [math]R[/math]. Zapisujemy to też jako: [math]x(R)y[/math]. Też dla innych oznaczeń relacji- jeśli oznaczymy relację przez np. [math]\sim[/math], to fakt, że elementy [math]x,y[/math] są ze sobą w relacji [math]\sim[/math], zapiszemy jako: [math]x\sim y[/math].
Suma, iloczyn i różnica relacji
Na relacjach można wykonywać działania mnogościowe. I tak, dla relacji [math]R,S\subset X\times Y,[/math] relacja [math]R\cup S[/math], to taka relacja, że dwa elementy [math]x,y[/math] są ze sobą w relacji [math]R\cup S[/math], jeśli tylko są ze sobą w relacji [math]R[/math], oraz wtedy, jeśli tylko są ze sobą w relacji [math]S[/math]. Czyli [math]\left( x,y\right) \in R\cup S\Longleftrightarrow \left( x,y\right) \in R\vee \left( x,y\right) \in S[/math].
Podobnie, dla relacji [math]R,S\subset X\times Y,[/math] relacja [math]R\cap S[/math], to taka relacja, że dwa elementy [math]x,y[/math] są ze sobą w relacji [math]R\cap S[/math], jeśli są ze sobą w relacji [math]R[/math], oraz równocześnie są ze sobą w relacji [math]S[/math]. Czyli [math]\left( x,y\right) \in R\cap S\Longleftrightarrow \left( x,y\right) \in R\wedge \left( x,y\right) \in S.[/math]
Podobnie, różnica relacji [math]R,S[/math]- relacja [math]R\setminus S[/math], to taka relacja, że dwa elementy są ze sobą w relacji [math]R\setminus S[/math], gdy są ze sobą w relacji [math]R[/math] i nie są ze sobą w relacji [math]S[/math], tzn. [math]\left( x,y\right) \in R\setminus S\Longleftrightarrow \left( x,y\right) \in R\wedge \left( x,y\right) \not\in S.[/math]
Ilustracja tych operacji jest podobna do ilustracji działań mnogościowych na zbiorach- zobacz ilustrację obok. Różnica polega na tym, że mamy wprowadzoną strukturę iloczynu kartezjańskiego, i na punkty patrzymy nie na jako zwykłe elementy, tylko jak na pary uporządkowane.
Co więcej, niech [math]\mathbb{A}[/math] będzie pewną rodziną relacji z [math]X[/math] do [math]Y[/math]. Wtedy [math]\bigcup \mathbb{A}[/math]- suma rodziny relacji z [math]X[/math] do [math]Y[/math], a więc suma rodziny podzbiorów [math]X\times Y[/math] jest podzbiorem [math]X\times Y[/math], a więc jest relacją z [math]X[/math] do [math]Y[/math]. Stąd mamy ważne:
Twierdzenie 2.1. Suma dowolnej rodziny relacji z [math]X[/math] do [math]Y[/math] jest relacją z [math]X[/math] do [math]Y[/math].
Dla takiej relacji, mamy: [math]\left( x,y\right) \in \bigcup \mathbb{A}\Longleftrightarrow \left( x,y\right) \in R[/math], dla pewnej relacji [math]R\in\mathbb{A}.[/math]
Tzn. dwa elementy są ze sobą w relacji [math]\bigcup \mathbb{A}[/math], gdy są z sobą w relacji [math]R[/math], dla pewnej relacji [math]R[/math] z rodziny relacji [math]\mathbb{A}.[/math]
Podobnie możemy określić iloczyn rodziny relacji. Dla niepustej rodziny [math]\mathbb{A}[/math] relacji z [math]X[/math] do [math]Y[/math], relacja [math]\bigcap \mathbb{A}[/math], to taka relacja, że dwa elementy są ze sobą w relacji [math]\bigcap \mathbb{A}[/math], gdy są z sobą w relacji [math]R[/math], dla każdej relacji [math]R\in\mathbb{A}.[/math]
Określimy podstawowe operacje na relacjach.
Niech [math]R \subset X \times Y.[/math] Lewą dziedziną relacji [math]R[/math] nazywamy zbiór [math]R _{L}:[/math]
[math]R _{L}=\left\{ x\in X\Bigl| \ \ \bigvee\limits_{y\in Y} \left( x,y\right) \in R \right\} \subset X.[/math]
Natomiast prawą dziedziną relacji [math]R[/math] nazywamy zbiór [math]R _{P}:[/math]
[math]R _{P}=\left\{ y\in Y\Bigl| \ \ \bigvee\limits_{x\in X} \left( x,y\right) \in R \right\} \subset Y.[/math]
Zbiór [math]R _{L}[/math]- jest to zbiór tych [math]x[/math]-ów, gdzie jest przynajmniej jeden [math]y[/math], że elementy [math]x,y[/math] są ze sobą w relacji [math]R[/math]. Mówiąc prościej, jest to zbiór lewych współrzędnych par tej relacji [math]R[/math]. Analogicznie, zbiór [math]R _{P}[/math]- jest to zbiór prawych współrzędnych par tej relacji [math]R[/math]. Możemy powiedzieć, że zbiór [math]R _{L}[/math] jest rzutem relacji [math]R[/math] na oś [math]x[/math], a zbiór [math]R _{P}[/math] jest rzutem relacji [math]R[/math] na oś [math]y[/math]. Zobacz ilustrację obok.
Przykład. Niech [math]X=\left\{ 1,2,3\right\}, Y=\left\{ 1,2\right\}, R=\left\{ \left( 1,1\right),\left( 1,2\right),\left( 2,2\right) \right\}.[/math] Wtedy [math]R _{L}=\left\{ 1,2\right\} [/math], [math]R _{P}=\left\{ 1,2\right\}=Y.[/math]
Poniżej podaje prosty, lecz ciekawy fakt:
Fakt 2.2. Dla dowolnej relacji [math]R \subset X \times Y,[/math] mamy: [math]R \subset R _{L} \times R _{P}.[/math]
Dowód:
Niech [math]\left( x,y\right) \in R.[/math] Mamy oczywiście [math]x\in X, y\in Y[/math]. Ponieważ [math]\left( x,y\right) \in R[/math], to [math]x[/math] jest lewą współrzędną pary z relacji [math]R[/math], a więc [math]x\in R _{L}.[/math] Podobnie ponieważ [math]y[/math] jest prawą współrzędną pary z relacji [math]R[/math], to [math]y\in R _{P}[/math]. Ponieważ [math]x\in R _{L}[/math] i [math]y\in R _{P}[/math], to [math]\left( x,y\right) \in R _{L} \times R _{P},[/math] i [math]R \subset R _{L} \times R _{P}.\square[/math]
Relacja odwrotna- powstaje poprzez symetrię względem przekątnej
Niech [math]R\subset X\times Y[/math]. Relację odwrotną do relacji [math]R[/math] nazywamy relację [math]R^{-1}\subset Y\times X[/math], określoną jako:
[math]R^{-1}=\left\{ \left( y,x\right) \in Y\times X \Bigl| \ \ \left( x,y\right) \in R \right\}.[/math]
Tzn. element [math]y[/math] jest w relacji z elementem [math]x[/math] w relacji [math]R^{-1}[/math], gdy [math]x[/math] jest w relacji z [math]y[/math]( czyli na odwrót) w relacji [math]R.[/math] Gdy X=Y, to możemy relację odwrotną zilustrować- zobacz obok rysunek.
Przykład. Niech [math]X=\left\{ a,b.c \right\}.[/math] Niech [math]R\subset X\times X[/math], będzie dana jako: [math]R= \left\{ \left( a,a\right),\left( a,b\right),\left( a,c\right),\left( b,b\right)\right\} .[/math] Wtedy [math]R^{-1} = \left\{ \left( a,a\right),\left( b,a\right),\left( c,a\right),\left( b,b\right) \right\}.[/math]
Fakt 2.3. Niech [math]X,Y[/math] będą dowolnymi ustalonymi zbiorami, oraz niech [math]R,S\subset X\times Y[/math] będą dowolnymi relacjami. Pokażemy własności tych relacji:
[math]1. \ \left( R\cup S\right) ^{-1}=R ^{-1} \cup S ^{-1}. \\[/math]
[math]2. \ \left( R\cap S\right) ^{-1}=R ^{-1} \cap S ^{-1}. \\[/math]
[math]3. \ \left( R\setminus S\right) ^{-1}=R ^{-1} \setminus S ^{-1}. \\[/math]
[math]4. \ \left( R^{-1}\right) ^{-1}=R . \\[/math]
Czyli relacją odwrotną do sumy relacji jest suma relacji odwrotnych, podobnie dla iloczynu i różnicy.
Dowód:
Niech [math]x\in X, y\in Y.[/math] Wtedy:
[math]1. \ \ \left( y,x\right) \in \left( R\cup S\right) ^{-1} \Leftrightarrow \left( x,y\right) \in R\cup S \Leftrightarrow \left( x,y\right) \in R \vee \left( x,y\right) \in S \Leftrightarrow \left( y,x\right) \in R ^{-1} \vee \left( y,x\right) \in S ^{-1} \Leftrightarrow \left( y,x\right) \in R ^{-1} \cup S ^{-1}.[/math] Zatem [math]\left( R\cup S\right) ^{-1}=R ^{-1} \cup S ^{-1}.[/math]
2. Dowód jest analogiczny do poprzedniego.
[math]3. \ \ \left( y,x\right) \in \left( R\setminus S\right) ^{-1} \Leftrightarrow \left( x,y\right) \in R\setminus S \Leftrightarrow \left( x,y\right) \in R \wedge \left( x,y\right) \notin S \Leftrightarrow \left( y,x\right) \in R ^{-1} \wedge \left( y,x\right) \notin S ^{-1} \Leftrightarrow \left( y,x\right) \in R ^{-1} \setminus S ^{-1}.[/math] Zatem [math]\left( R\setminus S\right) ^{-1}=R ^{-1} \setminus S ^{-1}.[/math]
[math]4. \ \ \left( x,y\right) \in \left( R^{-1}\right) ^{-1} \Leftrightarrow \left( y,x\right) \in R^{-1} \Leftrightarrow \left( x,y\right) \in R.[/math] Zatem [math]\left( R^{-1}\right) ^{-1}=R .\square[/math]
Na koniec tego podrozdziału wprowadzamy pojęcie relacji zwrotnej.
Relację [math]R \subset X\times X[/math] nazywamy zwrotną, gdy dla dowolnego [math]x\in X[/math] zachodzi [math]\left( x,x\right) \in R.[/math]
Relacja w zbiorze [math]X[/math] jest więc zwrotna, gdy każdy element [math]x\in X[/math] jest w relacji z samym sobą. Przykład: [math]X=\left\{ 0,1\right\}[/math]. Relacja [math]R=\left\{ \left( 0,0\right),\left( 1,1\right) ,\left( 0,1\right) \right\}[/math] jest zwrotna. Inny przykład: [math]X=\left\{ 0,1,2\right\}[/math], relacja [math]R=\left\{ \left( 0,0\right),\left( 1,1\right),\left( 1,2\right) \right\}[/math] nie jest zwrotna, bo [math]\left( 2,2\right) \not\in R.[/math]
Poniżej podaje prosty fakt.
Fakt 2.4. Relacja [math]R \subset X\times X[/math] jest zwrotna, wtedy i tylko wtedy, gdy [math]R \supset I_{X}[/math]. Zobacz ilustrację obok. A więc relacja jest zwrotna, gdy zawiera przekątną- identyczność na zbiorze [math]X[/math].
Dowód: [math]\Longrightarrow[/math] Niech relacja [math]R \subset X\times X[/math] będzie zwrotna. Niech [math]\left( x,y\right) \in I_{X}[/math]. Ponieważ jest to relacja identyczności, to [math]x=y[/math]. A ponieważ [math]R[/math] jest zwrotna, to [math]\left( x,y\right)=\left( x,x\right) \in R.[/math] A więc [math]R \supset I_{X}[/math].
[math]\Longleftarrow[/math] Załóżmy, że [math]R \supset I_{X}[/math]. Niech [math]x\in X.[/math] Wtedy [math]\left( x,x\right) \in I_{X}[/math], a ponieważ [math]R \supset I_{X}[/math], to [math]\left( x,x\right) \in R.[/math] Wobec dowolności [math]x\in X[/math] oznacza to, że [math]R[/math] jest zwrotna.[math]\square[/math]
Domknięcia relacji
