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

Uwaga: przekonwertowane latex2mediawiki; prawdopodobnie trzeba wprowadzi� poprawki

Zawartość wykładu: Para uporządkowana, iloczyn kartezjański, relacje, relacje równoważności, rozkłady zbiorów, domykanie relacji, rozdział dla dociekliwych.

Para uporządkowana

Bardzo często będziemy chcieli mieć do czynienia ze zbiorem, który niesie w sobie informacje o dwóch innych zbiorach, informacje tak udatnie 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.

Niech $x$ oraz $y$ będą zbiorami. Przez parę uporządkowaną $(x,y)$ rozumiemy zbiór

$\{\left\{x\right\},\{x,y\}\}$

Parę uporządkowaną można zdefiniować inaczej na wiele sposobów. Chodzi jednak o to aby ze zbioru który jest parą można było odzyskać jednoznacznie każdą z jego składowych. Tak więc moglibyśmy zaakceptować każdą inną inną definicję pod warunkiem, że będzie spełnione następujące twierdzenie:

Twierdzenie

Dla dowolnych zbiorów $a,b,c,d$ zachodzi:

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (a,b) = (c,d) \Leftrightarrow a=c \hspace*{0.1mm} \wedge b= d}

Dowód

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

$(a,b)=(a,d)$

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

Ćwiczenie

Dla każdej pary $x=(a,b)$ udowodnij, że

$\bigcap \bigcap x=a.$

Rozwiązanie

Rozważymy dwa przypadki.

1. Jeśli $a=b$ to $x=\{\{a\}\}$ i wtedy $\bigcap \bigcap x=a$.
2. Jeśli $a\ne b$ to $x=\{\{a\},\{a,b\}\}$ a więc

$\bigcap x=\bigcap \{\{a\},\{a,b\}\}=\{a\}\cap \{a,b\}=\{a\}$

skąd otrzymujemy

$\bigcap \bigcap x=a$

Ćwiczenie

Udowodnij, że dla dowolnej pary uporządkowanej $x$ zbiór

$\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))$

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

Rozwiązanie

Jeśli $x$ jest parą to istnieją zbiory $a,b$ takie, że $x=(a,b)$.

1. Przypuśćmy, że $a\ne b$. Wtedy $x=\{\{a\},\{a,b\}\}$ i ${𝒫}(x)=\{\mathrm{\varnothing },\{\{a\}\},\{\{a,b\}\},x\}$. Ponieważ ${𝒫}(\mathrm{\varnothing })=\{\mathrm{\varnothing }\}$

to ${𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })=\{\{\{a\}\},\{\{a,b\}\},x\}$ a wtedy

$\bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing }$

gdyż przecinany zbiór zawiera elementy rozłączne $\{\{a\}\},\{\{a,b\}\}$. Wobec tego również

$\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing }$

1. W przypadku, gdy $a=b$ otrzymujemy $x=\{\{a\}\}$ a więc ${𝒫}(x)=\{\mathrm{\varnothing },\{\{a\}\}\}$ i wtedy ${𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })=\{\{\{a\}\}\}$ skąd otrzymujemy

Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcap \bigcap ( \kPs(x) \setminus \mathcal{P}(\emptyset)) = \{a\} }

Ćwiczenie

Pokaż, że z każdej pary $x$ można otrzymać jej drugą współrzędną posługując się jedynie parą $x$, mnogościowymi operacjami Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcup, \bigcap, \cup,\cap,\setminus,\kPs} oraz stałą $\mathrm{\varnothing }$.

1. Rozważ najpierw pary różnych elementów.
2. Wykorzystaj zbiór z Ćwiczenia Uzupelnic ex:paraPS|

Rozwiązanie

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

$\bigcup (\bigcup x\setminus \bigcap x)=b.$

Ponieważ $a\ne b$ to $x=\{\{a\},\{a,b\}\}$ i wtedy

$\bigcup (\bigcup x\setminus \bigcap x)=\bigcup (\{a,b\}\setminus \{a\})=\bigcup \{b\}=b.$

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

$\bigcup (\bigcup x\setminus \bigcap x)=\bigcup (\{a\}\setminus \{a\})=\bigcup \mathrm{\varnothing }=\mathrm{\varnothing }.$

Musimy więc jeszcze trochę popracować. Wykorzystajmy ćwiczenie Uzupelnic ex:paraPS|, niech nowy wzór będzie postaci

$\bigcup (\bigcup x\setminus \bigcap x)\cup \bigcap \bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing })).$

Dla par o różnych elementach dodana część wzoru jest zbiorem pustym, więc ta sytuacja jest analogiczna do Uzupelnic eq:cwiczeniePara2wsp1|, skąd otrzymujemy że tak zdefiniowany zbiór jest równy $b$.

Dla par o równych elementach, pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu Uzupelnic ex:paraPS| pokazaliśmy że w takim przypadku mamy $\bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\{b\}$ jeśli $b$ jest współrzędną pary $x$. Wobec tego

$\bigcup (\bigcup x\setminus \bigcap x)\cup \bigcap \bigcap \bigcap ({𝒫}(x)\setminus {𝒫}(\mathrm{\varnothing }))=\mathrm{\varnothing }\cup \bigcap \{b\}=b.$

Iloczyn kartezjański

Zanim wprowadzimy definicję zbioru wszystkich par uporządkowanych elementów dwóch zbiorów (zwanego dalej iloczynem kartezjańskim) należy nam się krótka dyskusja. Otóż niech $x\in X$ oraz $y\in Y$. Łatwo zauważyć, że zarówno $\{x,y\}$ jak i $\left\{x\right\}$ są podzbiorami $X\cup Y$. Zatem $\{x,y\}\in {𝒫}(X\cup Y)$ oraz $\left\{x\right\}\in {𝒫}(X\cup Y)$. Więc $\{\left\{x\right\},\{x,y\}\}\subseteq {𝒫}(X\cup Y)$ co daje, że $(x,y)\in {𝒫}({𝒫}(X\cup Y))$.

Istnienie i konstrukcja iloczynu kartezjańskiego zostało dokładnie omówione w dodatkowym rozdziale Uzupelnic konstukcja_marcina| znajdującym się na końcu. Proponuje przestudiowanie dodatkowego rozdziału dopiero po zapoznaniu się z rozdziałami wcześniejszymi pomimo braku precyzji w następnej definicji.

Niech $x,y$ będą zbiorami. Iloczynem kartezjańskim (produktem) $x\times y$ nazywamy zbiór

$\{z\in {𝒫}({𝒫}(x\cup y)):{\mathrm{\exists }}_{a\in x}{\mathrm{\exists }}_{b\in y}(a,b)=z\}$

Będziemy używać specjalnej notacji $x^2$ na zbiór $x\times x$.

Ćwiczenie

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

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

Rozwiązanie

Z definicji iloczynu kartezjańskiego, oraz twierdzenia Uzupelnic para-up_tw| łatwo wynika następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów $a,b,x,y$ zachodzi

$(a,b)\in x\times y\iff (a\in x\wedge b\in y).$

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

Ponieważ $b\in \mathrm{\varnothing }$ jest zawsze fałszem to powyższy zbiór jest pusty.

1. Ponieważ obydwa zbiory są zbiorami par więc wykażemy że dowolna para należy do jednego

wtedy i tylko wtedy gdy należy do drugiego. Weźmy dowolną parę $(a,b)$ wtedy

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

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

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

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

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

Ćwiczenie

Produkt kartezjański $\times$ jest monotoniczny ze względu na każdą współrzędną osobno to znaczy:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x \subset y & \hspace*{0.1mm} \Rightarrow & (x \times z) \subset (y \times z) \\ x \subset y & \hspace*{0.1mm} \Rightarrow & (z \times x) \subset (z \times y) \endaligned}

Rozwiązanie

Ćwiczenie jest elementarne.

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

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

Stąd $(x\times z)\subset (y\times z)$.

1. Dla dowolnych zbiorów $x\subset y$ mamy $x\cup y=y$. Z poprzedniego

ćwiczenia otrzymujemy

$z\times y=z\times (x\cup y)=(z\times x)\cup (z\times y)\supset (z\times x).$

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

Ćwiczenie

Sprawdź, czy dla dowolnych zbiorów $A,B,C$, prawdziwa jest następująca implikacja

$A\times B=A\times C\Rightarrow B=C$

Rozwiązanie

Nie. Na przykład gdy $A=\mathrm{\varnothing }$ to dla dowolnych zbiorów $B,C$ mamy

$\mathrm{\varnothing }\times B=\mathrm{\varnothing }=\mathrm{\varnothing }\times C.$

Biorąc różne zbiory $B,C$ otrzymamy kontrprzykład dla badanej implikacji.

Relacje

Relacją nazywamy każdy podzbiór iloczynu $x\times y$

Operacje na relacjach:

Niech $R\subset A\times B$ oraz $S\subset B\times C$.

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle S \circ R  := \left\{(x,z)\in A \times C : \exists_{y\in B} (x,y)\in R \hspace*{0.1mm} \wedge (y,z)\in S \right\}\displaystyle R^{-1} := \left\{(y,x)\in B \times A : \;\; (x,y)\in R \right\}\displaystyle R_L := \left\{x\in A : \exists_{y\in B} \;\; (x,y) \in R\right\}\displaystyle R_P := \left\{y\in B : \exists_{x\in A} \;\; (x,y) \in R\right\}}

Ćwiczenie

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned T \circ ( S \circ R ) &= (T \circ S)\circ R \\ (S \circ R )^{-1} &= R^{-1} \circ S^{-1} \\ R & \subset & R_L \times R_P \\ (S \circ R)_L & \subset & R_L \\ (S \circ R)_P & \subset & S_P \\ (R^{-1} )_L &= R_P \endaligned}

Rozwiązanie

Ćwiczenie jest elementarne.

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

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

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

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

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

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

Ćwiczenie

Niech relacja $R\subset B\times C,S\subset B\times C$ oraz $T\subset A\times B$. Pokaż własności:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (R \cup S )^{-1} &= R^{-1} \cup S^{-1} \\ (R \cap S )^{-1} &= R^{-1} \cap S^{-1} \\ (R^{-1})^{-1} &= R \\ (R \cup S ) \circ T &= (R \circ T) \cup (S \circ T)\\ (R \cap S ) \circ T & \subset & (R \circ T) \cap (S \circ T) \endaligned}

Rozwiązanie

Ćwiczenie jest elementarne. W poniższych punktach (1-4) pokażemy, że dowolna para należy do zbioru po lewej stronie odpowiedniej równości wtedy i tylko wtedy gdy należy do prawej. W punkcie 5, pokazujemy jedynie implikację w prawą stronę, gdyż mamy udowodnić inkluzję.

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

1. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć $\cap$ w miejsce $\cup$ oraz $\wedge$ w miejsce $\vee$.

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

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

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

Ćwiczenie

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

$(R\cap S)\circ T=(R\circ T)\cap (S\circ T)$

Rozwiązanie

Niech $R=\{(1,3)\},S=\{(2,3)\},T=\{(0,1),(0,2)\}$ wtedy

1. $R\cap S=\mathrm{\varnothing }$ więc $(R\cap S)\circ T=\mathrm{\varnothing }$.
2. $T\circ R=\{(0,3)\}$ i $T\circ S=\{0,3\}$ a więc

$(R\circ T)\cap (S\circ T)=\{0,3\}$

Ćwiczenie

Udowodnij, że zbiór $A$ jest relacją wtedy i tylko wtedy gdy

$A\subset (\bigcup \bigcup A)\times (\bigcup \bigcup A)$

Rozwiązanie

Pokażemy najpierw, że dla każdej relacji $R$ mamy

$\bigcup \bigcup R=R_L\cup R_P.$

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

Pokażemy teraz prawdziwość inkluzji $\supset$ w równaniu Uzupelnic eq:cwiczenieBCBC|. Weźmy dowolny element $a\in R_L$ wtedy istnieje element $b\in R_P$ taki, że $(a,b)\in R$, a więc $\{(a,b)\}\subset R$. Stąd otrzymujemy

$\bigcup \bigcup \{(a,b)\}\subset \bigcup \bigcup R.$

Ponieważ $\bigcup \bigcup \{(a,b)\}=\bigcup \{\{a\},\{a,b\}\}=\{a,b\}$ to otrzymujemy $\{a,b\}\subset R$, a więc $a\in R$. Analogiczne rozumowanie można przeprowadzić dla elementu $b\in R_P$. Zakończyliśmy więc dowód równości Uzupelnic eq:cwiczenieBCBC|.

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

$A\subset A_L\times A_P\subset (A_L\cup A_P)\times (A_L\cup A_P)=(\bigcup \bigcup A)\times (\bigcup \bigcup A)$

Relacje równoważności

W tym podrozdziale poznamy ważną klasę (zbiór) relacji zwaną klasą relacji równoważności(w innych podręcznikach mogą się państwo spotkać z nazwą relacja abstrakcji). Relacje takie będą służyły do definiowania pojęć abstrakcyjnych o czym przekonamy się w wielu miejscach tego i innych wykładów. Bardzo dobrym ćwiczeniem pokazującym abstrakcyjne metody definiowania pojęć będzie wykład $8$ w którym zaprzęgniemy relacje abstrakcji do definiowania liczb.

Rozpoczynamy rozdział od koniecznej definicji.

Dla zbioru $X$ definiujemy relację $1_X\subset X\times X$ jako $\{z\in X\times X:{\mathrm{\exists }}_{x\in X}(x,x)=z\}$.

Relację $R\subset X\times X$ nazywamy relacją równoważnością o polu $X$ jeżeli:

• zawiera relacje $1_X$ (zwrotność $R$)
• $R^{-1}\subset R$ (symetria $R$)
• $R\circ R\subset R$ (przechodniość $R$)

Ćwiczenie

Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu $X$ są odpowiednio równoważne następującym własnościom:

• ${\mathrm{\forall }}_{x\in X}(x,x)\in R$
• ${\mathrm{\forall }}_{x,y\in X}(x,y)\in R\to (y,x)\in R$
• ${\mathrm{\forall }}_{x,y,z\in X}(x,y)\in R\wedge (y,z)\in R\to (x,z)\in R$

Rozwiązanie

Ćwiczenie jest elementarne.

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

$[x{]}_R:=\{y\in X:(x,y)\in R\}$

Zbiór klas równoważności relacji $R$ będący elementem zbioru ${𝒫}({𝒫}(X\times X))$ oznaczamy przez $X/R$.

Twierdzenie

Niech $R$ będzie relacją równoważności o polu $X$. Następujące warunki są równoważne

1. $[x{]}_R\cap [y{]}_R\ne \mathrm{\varnothing }$
2. $[x{]}_R=[y{]}_R$
3. $(x,y)\in R$

Dowód

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

W następnym twierdzeniu zobaczymy jak rodzina relacji równoważności jest odporna na przecinanie. Pokażemy mianowicie, że przecięcie dowolnej liczby relacji równoważności jest nadal relacją równoważności.

Twierdzenie

Niech $\kappa \ne \mathrm{\varnothing }$ będzie pewną rodziną (zbiorem) relacji równoważności o tym samym polu $X$. Mamy że:

1. $\bigcap \kappa$ jest relacją równoważności o polu $X$.
2. $[x{]}_{\bigcap \kappa }=\bigcap \{[x{]}_R:R\in \kappa \}$

Dowód

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

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

Rozkłady zbiorów

Niech $X\ne \mathrm{\varnothing }$. Rodzinę $r\in {𝒫}({𝒫}(X))$ nazywamy rozkładem zbioru $X$ gdy

1. ${\mathrm{\forall }}_{C\in r}C\ne \mathrm{\varnothing }$
2. $\bigcup r=X$
3. Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle (C \in r \hspace*{0.1mm} \wedge D \in r \hspace*{0.1mm} \wedge C \neq D )\hspace*{0.1mm} \Rightarrow C\cap D =\emptyset}

Lemat

Dla relacji równoważności $R$ o polu $X$ zbiór $X/R$ jest rozkładem

$X$.

Dowód

$(1)$ Każda klasa jest niepusta bo zawiera element, który ją wyznacza. $(2)\bigcup X/R\subseteq X$ bo każda klasa jest podzbiorem $X$. Odwrotnie każdy $x\in [x{]}_R\in X/R$. $(3)$ Dwie klasy gdy są rożne muszą być rozłączne co udowodniliśmy w twierdzeniu Uzupelnic thm:rownowaznosc|.

Niech $r$ będzie rozkładem zbioru $X$. Definiujemy relacje $R_r\subset X\times X$ następująco:

$(x,y)\in R_r$ wtw Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \exists_{C\in r} \;\; x \in C \; \hspace*{0.1mm} \wedge \; y\in C }

Lemat

Dla rozkładu $r\in {𝒫}({𝒫}(X))$ relacja $R_r$ jest:

1. równoważnością
2. $X/R_r=r$

Dowód

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

Ćwiczenie

Niech $X$ będzie niepustym zbiorem, oraz niech $Y\subset X$. Zdefiniujemy relację $R\subset {𝒫}(X)\times {𝒫}(X)$ następująco: dla dowolnych zbiorów $A,B\subset X$ mamy

$(A,B)\in R\iff A\frac{.}{}B\subset Y.$

($\frac{.}{}$ oznacza różnicę symetryczną zbiorów, czyli $A\frac{.}{}B=(A\setminus B)\cup (B\setminus A)$) Udowodnij, że relacja $R$ jest relacją równoważności. Najtrudniej jest pokazać przechodniość. Udowodnij, że $A\frac{.}{}C\subset (B\frac{.}{}C)\cup (A\frac{.}{}B)$. Dobrym punktem wyjścia jest naszkicowanie wszystkich przecięć zbiorów $A,B,C$.

Rozwiązanie

Pokażemy po kolei zwrotność, przechodniość i symetryczność.

1. Dla każdego $A\subset X$ mamy $A\frac{.}{}A=\mathrm{\varnothing }\subset Y$, a więc relacja $R$ jest zwrotna.
2. Ponieważ dla dowolnych zbiorów $A\frac{.}{}B=B\frac{.}{}A$ to $(A,B)\in R$ wtedy i tylko wtedy gdy $(B,A)\in R$. Wobec tego relacja $R$ jest symetryczna.
3. Weźmy zbiory $A,B,C\subset X$, takie że $(A,B),(B,C)\in R$. Wtedy

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned A \frac{.}{} C= (A\setminus C) \cup (C\setminus A) =\\ (((A\cap B) \cup (A\setminus B))\setminus C) \cup (((C\cap B) \cup (C\setminus B))\setminus A) =\\ ((A\cap B)\setminus C) \cup ((A\setminus B)\setminus C) \cup ((C\cap B)\setminus A) \cup ((C\setminus B)\setminus A) \subset\\ (B\setminus C) \cup (A\setminus B) \cup (B\setminus A) \cup (C\setminus B)=\\ (B\frac{.}{} C) \cup (A\frac{.}{} B). \endaligned}

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

Ćwiczenie

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

${\mathrm{\forall }}_{x\in X}([x{]}_R\subset [x{]}_S\vee [x{]}_R\supset [x{]}_S).$

Podaj przykłady relacji równoważności $R,S$ takich, że $R\cup S$ jest relacją równoważności oraz $R⊈S$ i $S⊈R$. Przyjrzyj się dokładnie rodzinie zbiorów $A=\{[x{]}_R\cup [x{]}_S:x\in X\}$.

Rozwiązanie

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

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned (a,b)\in R\cup S \Leftrightarrow (a,b)\in R \vee (a,b)\in S \Leftrightarrow a\in[b]_R \vee a\in [b]_S \Leftrightarrow a \in [b]_R \cup [b]_S. \endaligned}

Pokażemy teraz, że jeśli $R\cup S$ jest relacją równoważności to musi być spełniona formuła Uzupelnic eq:klasyInkluzje|. Dla dowodu nie wprost przypuśćmy, że nie jest spełniona. Oznacza to, że istnieje element $x\in X$ dla którego $[x{]}_R⊈[x{]}_S$ oraz $[x{]}_R⊉[x{]}_S$. Wobec tego istnieje $y\in [x{]}_R\setminus [x{]}_S$ oraz $z\in [x{]}_S\setminus [x{]}_R$. Oznacza to, że $(y,x)\in R\setminus S$ oraz $(x,z)\in S\setminus R$. Skoro $R\cup S$ jest relacją równoważności to $(z,y)\in R\cup S$. Przypuśćmy, że $(z,y)\in R$. Wtedy $(z,y),(y,x)\in R$ wobec czego $(z,x)\in R$ co jest sprzeczne z tym że $(x,z)\in S\setminus R$ ponieważ relacja $R$ jest symetryczna. Analogiczną sprzeczność otrzymujemy dla $(z,x)\in S$. Obie możliwości prowadzą do sprzeczności, a więc formuła Uzupelnic eq:klasyInkluzje| musi być spełniona.

Na koniec podajemy przykład relacji równoważności, równoważności $R,S$ takich, że $R\cup S$ jest relacją równoważności oraz $R⊈S$ i $S⊈R$. Polem relacji będzie zbiór $X=\{0,1,2,3\}$. Relacje $R,S$ określimy poprzez wyznaczane przez nie rozkłady odpowiednio $r,s$:

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

Łatwo sprawdzić, że $R⊈S$ i $S⊈R$, gdyż $(2,3)\in R\setminus S$ oraz $(0,1)\in S\setminus R$. Z rozkładów $r,s$ łatwo wynika, że formuła Uzupelnic eq:klasyInkluzje| jest prawdziwa dla tych relacji, wobec czego $R\cup S$ jest relacją równoważności. Wyznaczany przez nią rozkład to $\{\{0,1\},\{2,3\}\}$.

Domykanie relacji

W praktyce matematycznej często potrzebne jest rozważanie domknięć relacji ze względu na wiele przeróżnych własności. W podrozdziale tym dokonamy charakteryzacji domknięć. Pokażemy między innymi kiedy takie domykanie jest możliwe.

Niech $\alpha$ będzie rodziną relacji o polu $X$, czyli niech $\alpha \in {𝒫}({𝒫}(X^2))$. Rodzina $\alpha$ jest zamknięta na przecięcia gdy

1. $X^2\in \alpha$
2. jeżeli $\mathrm{\varnothing }\ne {\alpha }^{\prime }\subset \alpha$ to $\bigcap {\alpha }^{\prime }\in \alpha$

Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji. Definiujemy intuicyjnie najmniejszą relacje zawierającą daną należącą do klasy.

Relacja $S\subset X^2$ jest domknięciem relacji $R\subset X^2$ w klasie (zbiorze) relacji $\alpha$ gdy:

1. $R\subset S$
2. $S\in \alpha$
3. dla każdej relacji $T$ jeżeli $R\subset T$ oraz $T\in \alpha$ to $S\subset T$

Lemat

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

Dowód

Gdyby istniały dwa domknięcia pewnej relacji to ze względu na warunek $(3)$ wzajemnie by się zawierały.

Twierdzenie

Następujące warunki są równoważne:

1. Klasa relacji $\alpha$ jest domknięta na przecięcia.
2. Każda relacja ma domknięcie w klasie relacji $\alpha$.

Dowód

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

Ćwiczenie

Pokazać jak wyglądają domknięcia w klasie relacji, zwrotnych, symetrycznych i przechodnich.

Pokazać stosując twierdzenie Uzupelnic thm:domkniecie|, że nie istnieje domknięcie spójne ani antysymetryczne. (Relacja $R$ jest spójna gdy Parser nie mógł rozpoznać (błąd składni): {\displaystyle \displaystyle \forall x,y (x,y) \in R \hspace*{0.1mm} \vee (y,x)\in R} . Relacja $R$ jest antysymetryczna gdy z faktu, że $(x,y)\in R$ oraz $(y,x)\in R$ da się pokazać, że $x=y$)

Rozwiązanie

Ćwiczenie jest elementarne.

1. Pokażemy, że dla każdej relacji $R\in X^2$ jej domknięcie w klasie relacji zwrotnych na $X$ to $R\cup 1_X$.

Pokażemy po kolei, że spełnia warunki domknięcia.

1. 1. $R\subset R\cup 1_X$
   2. $1_X\subset R\cup 1_X$, a więc jest zwrotna
   3. weźmy dowolną zwrotną relację $T\supset R$. Ponieważ $T$ jest zwrotna to $T\supset 1_X$, a więc $T\supset R\cup 1_X$.
2. Pokażemy, że dla każdej relacji $R\in X^2$ jej domknięcie w klasie relacji symetrycznych na $X$ to $R\cup R^{-1}$.

Pokażemy po kolei, że spełnia warunki domknięcia.

1. 1. $R\subset R\cup R^{-1}$
   2. $(R\cup R^{-1}{)}^{-1}=R^{-1}\cup (R^{-1}{)}^{-1}=R^{-1}\cup R=R\cup R^{-1}$, a więc jest symetryczna
   3. weźmy dowolną symetryczną relację $T\supset R$. Ponieważ $T$ jest symetryczna to

$T\supset T^{-1}$. Skoro $T\supset R$ to $T^{-1}\supset R^{-1}$. Ponieważ $T\supset T^{-1}$ to $T\supset R\cup R^{-1}$.

1. Posługując się intuicyjnym pojęciem liczb naturalnych przedstawimy szkic konstrukcji przechodniego domknięcia,

pomimo że konstrukcja ta wyprzedza prezentowany materiał. Dla dowolnej liczby $n\in N\setminus \{0\}$ przez $R^n$ będziemy oznaczać $n$-krotne złożenie relacji $R$ z sobą (czyli $R^1=R$ oraz $R^{n+1}=R^n\circ R$ dla $n>1$). Zdefiniujmy rodzinę ${ℛ}$ jako zbiór wszystkich skończonych wielokrotnych złożeń relacji $R$ z sobą, czyli ${ℛ}=\{r\subset X^2:{\mathrm{\exists }}_{n\in N}(n\ne 0\wedge R^n=r)\}$. Do formalnego zdefiniowania rodziny ${ℛ}$ potrzebne są pojęcia liczb naturalnych, funkcji oraz definiowania przez indukcje, które zostaną przedstawione w następnych rozdziałach. Pokażemy teraz, że domknięcie relacji $R$ w klasie relacji przechodnich na $X$ to relacja $\bigcup {ℛ}$. Pokażemy po kolei, że spełnia warunki domknięcia.

1. 1. $R=R^1\subset \bigcup {ℛ}$
   2. Aby pokazać, że relacja $\bigcup {ℛ}$ jest przechodnia weźmy dowolne dwie pary $(a,b),(b,c)\in {ℛ}$.

Wtedy muszą istnieć liczby $n,m\in N$ takie, że $(a,b)\in R^n$ oraz $(b,c)\in R^m$. Wobec tego $(a,c)\in R^m\circ R^n$. Z łączności składania relacji wynika, że $R^m\circ R^n=R^{m+n}$. Wobec tego $(a,c)\in R^{m+n}\subset \bigcup {ℛ}$.

1. 1. Weźmy dowolną przechodnią relację $T$ taką, że $R\subset T$ pokażemy indukcyjnie, że dla każdego

$n\in N\setminus \{0\}$ mamy $R^n\subset T$.

1. 1. 1. Baza indukcji. Dla $n=1$ mamy $R^1=R$ a więc z założenia $R^1\subset T$.
      2. Krok indukcyjny. Weźmy dowolne $n\in N\setminus \{0,1\}$ i przypuśćmy, że dla każdego $0<m<n$

zachodzi $R^m\subset T$. Weźmy dowolną parę $(a,c)\in R^n$. Ponieważ $n>1$ to $R^n=R^{n-1}\circ R$. Oznacza to, że istnieje element $b\in X$ taki, że $(a,b)\in R$ oraz $(b,c)\in R^{n-1}$. Z założenia indukcyjnego wynika, że $(a,b)\in T$ oraz $(b,c)\in T$. Ponieważ $T$ jest przechodnia to $(a,c)\in T$. Wobec dowolności wyboru pary $(a,c)$ otrzymujemy $R^n\subset T$.

Skoro dla każdego $n\in N\setminus \{0\}$ mamy $R^n\subset T$ to również $\bigcup {ℛ}\subset T$.

Pokażemy teraz że istnieje zbiór $X$ taki, że klasa relacji spójnych na zbiorze $X$ i klasa relacji symetrycznych na zbiorze $X$ nie są domknięte na przecięcia. W obliczu twierdzenia Uzupelnic thm:domkniecie| będzie to oznaczało, że nie wszystkie relacje mają domknięcia w tych klasach. Niech $X=\{0,1\}$.

1. Relacje $\{(0,1),(0,0),(1,1)\},\{(1,0),(0,0),(1,1)\}$ są spójne na $X$, a ich

przecięcie czyli zbiór $\{(0,0),(1,1)\}$ nie jest.

1. Relacja $X^2$ nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na $X$

nie jest domknięta na przecięcia.

Ćwiczenie

Dla relacji $R$ niech $R^{\alpha }$, $R^{\beta }$, $R^{\gamma }$ oznaczają odpowiednio zwrotne, symetryczne, przechodnie domknięcie relacji $R$. Czy prawdą jest że:

1. dla dowolnej relacji $R$ relacja

$((R^{\alpha }{)}^{\beta }{)}^{\gamma }$ jest relacją równoważności

1. dla dowolnej relacji $R$ zachodzi

$((R^{\alpha }{)}^{\beta }{)}^{\gamma }=((R^{\gamma }{)}^{\beta }{)}^{\alpha }$

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

Rozwiązanie

1. Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze $X$. Z definicji zwrotności mamy

$R$ jest zwrotna wtedy i tylko wtedy gdy $R\supset 1_X$. W definicji domknięcia Uzupelnic defn:domkniecie| punkt pierwszy mówi, że jeśli $S$ jest domknięciem to $S\supset R$. Wobec tego konieczne jest aby $S\supset 1_X$. Zwróćmy uwagę, że powyższy argument działa dla dowolnych klas rodzin relacji domkniętych na przecięcia. Stąd otrzymujemy, że symetryczne domknięcie relacji zwrotnej jest zwrotne, i przechodnie domknięcie relacji zwrotnej jest zwrotne. Ponieważ relacja $R^{\alpha }$ jest zwrotna, to również zwrotna musi być $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$. Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia Uzupelnic ex:charakteryzacjeDomkniec|. Można łatwo pokazać indukcyjnie, że dla dowolnego Parser nie mógł rozpoznać (nieznana funkcja „\inN”): {\displaystyle \displaystyle n\inN\setminus\{0\}} mamy $(R^n{)}^{-1}=(R^{-1}{)}^n$. Dla relacji symetrycznych dostajemy więc $(R^n{)}^{-1}=R^n$. Wobec tego mamy

$(\bigcup \{R^n:n\in N\setminus \{0\}\}{)}^{-1}=\bigcup \{(R^n{)}^{-1}:n\in N\setminus \{0\}\}=\bigcup \{R^n:n\in N\setminus \{0\}\}$

a więc przechodnie domknięcie relacji symetrycznej jest symetryczne. Oznacza to, że relacja $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$ jest symetryczna. Wcześniej pokazaliśmy, że jest zwrotna. Ponieważ jest przechodnim domknięciem to jest też przechodnia. Wobec tego jest relacją równoważności.

1. Pokażemy relację $R$ dla której relacja $((R^{\gamma }{)}^{\beta }{)}^{\alpha }$ nie jest przechodnia. Ponieważ relacja $((R^{\alpha }{)}^{\beta }{)}^{\gamma }$

jest przechodnia, będzie to oznaczało że te relacje są różne. Niech $X=\{0,1,2\}$ oraz $R=\{(0,2),(1,2)\}$. Relacja $R$ jest przechodnia więc $R^{\gamma }=R$ jej symetryczne domknięcie to $(R^{\gamma }{)}^{\beta }=\{(0,2),(2,0),(1,2),(2,1)\}$. I po zwrotnym domknięciu otrzymujemy $((R^{\gamma }{)}^{\beta }{)}^{\alpha }=\{(0,2),(2,0),(1,2),(2,1),(0,0),(1,1),(2,2)\}$. Łatwo zauważyć, że otrzymana relacja nie jest przechodnia, gdyż $(0,2),(2,1)\in ((R^{\gamma }{)}^{\beta }{)}^{\alpha }$ podczas gdy $(0,1)\notin ((R^{\gamma }{)}^{\beta }{)}^{\alpha }$.

==Iloczyn kartezjański i podobne konstrukcje (rozdział dla dociekliwych)==

W definicji Uzupelnic iloczyn_kartezjanski| zaprezentowanej w rozdziale Uzupelnic section_iloczyn_kartezjanski| jest pewna nieścisłość. Konstrukcja iloczynu kartezjańskiego odwołuje się do aksjomatu wyróżniania w wersji nieuprawomocnionej. Konstrukcja którą zobaczą państwo w tym rozdziale usuwa tą poprzednią niedogodność.

Twierdzenie

Dla dowolnych dwóch zbiorów $x$ i $y$ istnieje zbiór $x\times y$ zawierający wszystkie pary postaci $(w,z)$ gdzie $w\in x$ i $z\in y$.

Dowód

Ustalmy dwa dowolne zbiory $x$ i $y$. Jeśli $x=\mathrm{\varnothing }$ lub $y=\mathrm{\varnothing }$ to $x\times y=\mathrm{\varnothing }$ istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku $x\cup y$ jest zbiorem jednoelementowym $\{z\}$ to $x\times y=\{\{\{z\}\}\}$ istnieje na podstawie aksjomatu pary. W dalszej częsci dowodu zakładamy że zbiory $x$ i $y$ są niepuste i że $x\cup y$ ma więcej niż jeden element. Na podstawie aksjomatu zbioru potęgowego, aksjomatu unii i aksjomatu wycinania następujące zbiory istnieją:

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned A &=\{z\in\mathcal{P}(x)\,|\, \exists w\; z =\{w\}\}, \\ B &=\{z\in\mathcal{P}(x\cup y)\,|\, \exists w \exists v\; (w \neq v \land z=\{v,w\})\},\\ C &=\{z\in\mathcal{P}(\mathcal{P}(y))\,|\, \exists v\; z=\{\{v\}\}=(v,v)\}. \endaligned}

Nasze założenia gwarantują, że żaden z powyższych zbiorów nie jest pusty. Kontynuując możemy stworzyć

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0 &=\{z\in\mathcal{P}(A\cup B)\,|\, \exists w \exists v\; w\neq v \land z=\{\{w\},\{w,v\}\}=(w,v)\}, \endaligned}

w którym to zbiorze mamy pewność, że $w$ jest elementem $x$. Kontynuujemy definiując

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0' &=\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(v,v)\}\}, \endaligned}

gdzie mamy pewność, że $w$ jest elementem $x$, a $v$ elementem $y$, oraz

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned D_0'' &=\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(w,w )\}\}, \endaligned}

gdzie mamy pewność, że $w\in A\cap B$. Kończąc

Parser nie mógł rozpoznać (nieznana funkcja „\aligned”): {\displaystyle \displaystyle \aligned x\times y &=\{z\in\bigcup D_0' \,|\, \exists w \exists v\; w\neq v \land z=(w,v)\}\cup \{z\in\bigcup D_0'' \,|\, \exists w\; z=(w,w)\}. \endaligned}

Twierdzenie

Jeśli $x,y$ i $z$ są zbiorami i $z\subseteq x\times y$ to zbiorem jest również ogół $v$ takich, że istnieje $w$ spełniające $(v,w)\in z$. Zbiór takich $v$ oznaczamy przez ${\pi }_1(z)$ i nazywamy projekcją na pierwszą współrzędną.

Dowód

Zbiór ${\pi }_1(z)$ istnieje na podstawie aksjomatów ZF i jest równy:

${\pi }_1(z)=\bigcup \{w\in \bigcup z|\mathrm{\exists }uw=\{u\}\}.$

W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykład. AKS Dla dowolnej formuły ${\phi }^{\prime }$ nie posiadającej zmiennych wolnych innych niż $z^{\prime }$ i ${x_1}^{\prime }$ następująca formuła jest prawdą

$\mathrm{\forall }{x_1}^{\prime }\mathrm{\forall }{x}^{\prime }\mathrm{\exists }{y}^{\prime }\mathrm{\forall }{z}^{\prime }{z}^{\prime }\in y^{\prime }⟺(z^{\prime }\in x^{\prime }\wedge {\phi }^{\prime }).$

Aby dowieść tą własność ustalmy dowolną formułę ${\phi }^{\prime }$ i dowolny zbiór ${x_1}^{\prime }$. Stosujemy aksjomat wyróżniania do $x=x\times \{{x_1}^{\prime }\}$ (który istnieje na mocy Twierdzenia Uzupelnic tw:produktistnieje|) i do formuły

$\mathrm{\exists }{z}^{\prime }\mathrm{\exists }{x_1}^{\prime }z=(z^{\prime },{x_1}^{\prime })\wedge {\phi }^{\prime }$

otrzymując zbiór $y$. Wymagany zbiór $y^{\prime }$ istnieje na mocy Twierdzenia Uzupelnic tw:pierwszaproj| i jest równy ${\pi }_1(y)$.

Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji z iloczynu kartezjańskiego. Aby otrzymać ${\pi }_2(z)$ stosujemy powyższe twierdzenie do ${x_1}^{\prime }=z$, $x=\bigcup \bigcup z$ i wyrażenia ${\phi }^{\prime }$ mówiącego $\mathrm{\exists }w(w,z^{\prime })\in {x_1}^{\prime }$.