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

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

$\{\{x\},\{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ż $\{a\}\in (a,b)$ więc $\{a\}\in (c,d)$. Mamy zatem $\{a\}=\{c\}$ lub $\{a\}=\{c,d\}$. W pierwszym przypadku $a=c$ ale w drugim również jest tak, mamy bowiem, że $c\in \{a\}$. 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)=\{\{a\}\}$. Zatem $\{\{a\}\}=\{\{a\},\{a,d\}\}$ co daje, że $\{a,d\}=\{a\}$ a zatem $d=a$. W przeciwnym przypadku gdy $a\ne b$ mamy, że $\{a,b\}\in \{\{a\},\{a,d\}\}$. Daje to dwie możliwości albo $\{a,b\}=\{a\}$ 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

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

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 Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \kPs{x}= \{\emptyset, \{\{a\}\}, \{\{a,b\}\},x \}} . Ponieważ Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \kPs{\emptyset}=\{\emptyset\}}

to Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \kPs{x} \setminus \kPs{\emptyset} =\{ \{\{a\}\}, \{\{a,b\}\},x \}} a wtedy

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

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

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

1. W przypadku, gdy $a=b$ otrzymujemy $x=\{\{a\}\}$ a więc Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \kPs{x}=\{\emptyset ,\{\{a\}\}\}} i wtedy Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \kPs{x} \setminus \kPs{\emptyset} =\{ \{\{a\}\} \}} skąd otrzymujemy

Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcap \bigcap ( \kPs(x) \setminus \kPs{\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

Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\kPs{x} \setminus \kPs{\emptyset}). }

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 Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcap \bigcap (\kPs{x} \setminus \kPs{\emptyset})=\{b\}} jeśli $b$ jest współrzędną pary $x$. Wobec tego

Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle \bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\kPs{x} \setminus \kPs{\emptyset})= \emptyset \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 $\{x\}$ są podzbiorami $X\cup Y$. Zatem $\{x,y\}\in {𝒫}(X\cup Y)$ oraz $\{x\}\in {𝒫}(X\cup Y)$. Więc $\{\{x\},\{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

Parser nie mógł rozpoznać (nieznana funkcja „\kIff”): {\displaystyle \displaystyle (a,b)\in x \times y \kIff (a\in x \kAnd b\in y). }

x =
z Szablon:X z: _{a x} _{b } (a,b)=z=
z Szablon:X z: _{a x} _{b}[ (b ) (a,b)=z]

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

(a,b) x (y z)
a x b (y z)
a x (b y b z)
(a x b y) (a x b z)
(a,b) x y (a,b) x z
(a,b) x y x z.

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

(a,b) x (y z)
a x b (y z)
a x (b y b z)
(a x b y) (a x b z)
(a,b) x y (a,b) x z
(a,b) x y x z.

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

(a,b) (x y) (x z)
a x b y (a x b z)
b y (a x (a x b z))
b y [(a x a x) (a x b z)]
b y (a x b z)
a x (b y z)
(a,b) x (y z)

Ć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

(a,b) x z
a x b z
a y b z
(a,b) y z.

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

Parser nie mógł rozpoznać (nieznana funkcja „\kImp”): {\displaystyle \displaystyle A\times B = A\times C \kImp 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  := \{ (x,z)\in A \times C : \exists_{y\in B} (x,y)\in R \hspace*{0.1mm} \wedge (y,z)\in S \} \displaystyle R^{-1} := \{ (y,x)\in B \times A : \;\; (x,y)\in R \} \displaystyle R_L := \{ x\in A : \exists_{y\in B} \;\; (x,y) \in R \} \displaystyle R_P := \{ y\in B : \exists_{x\in A} \;\; (x,y) \in R \} }

Ć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.

(x,z) T ( S R )
_{u} [(x,u) ( S R ) (u,z) T]
_{u} [_{v}( (x,v) R (v,u) S) (u,z) T]
_{u} _{v}[ (x,v) R (v,u) S (u,z) T]
_{v} _{u}[ (x,v) R ((v,u) S (u,z) T)]
_{v} [ (x,v) R _{u}((v,u) S (u,z) T)]
_{v} [ (x,v) R (v,z) T S]
(x,z) (T S) R

(x,z) (S R )^{-1}
(z,x) S R
_{y} [(z,y) R (y,x) S]
_{y} [(y,z) R^{-1} (x,y) S^{-1}]
(x,z) R^{-1} S^{-1}

(x,z) R
_{y} (x,u) R _{v} (v,y) R
x R_L y R_P
(x,y) R_L R_P

x (S R)_L
_{z} (x,z) S R
_{z} _{y} [(x,y) R (y,z) S ]
_{z} _{y} (x,y) R
_{y} (x,y) R
x R_L

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

x (R^{-1} )_L
_{y} (x,y) R^{-1}
_{y} (y,x) R
x R_P

Ć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ę.

(x,y) (R S)^{-1}
(y,x) (R S)
(y,x) R (y,x) S
(x,y) R^{-1} (x,y) S^{-1}
(x,y) R^{-1} S^{-1}

1. Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć $\cap$ w miejsce $\cup$ oraz Parser nie mógł rozpoznać (nieznana funkcja „\kAnd”): {\displaystyle \displaystyle \kAnd} w miejsce Parser nie mógł rozpoznać (nieznana funkcja „\kOr”): {\displaystyle \displaystyle \kOr} .

(x,y) (R^{-1})^{-1}
(y,x) R^{-1}
(x,y) R

(x,z) (R S ) T
_y [(x,y) T (y,z) (R S )]
_y [(x,y) T ((y,z) R (y,z) S ))]
_y [((x,y) T (y,z) R) ((x,y) T (y,z) S ))]
[_y ((x,y) T (y,z) R)] [_y ((x,y) T (y,z) S )]
(x,z) (R T) (x,z) (S T)
(x,z) (R T) (S T)

(x,z) (R S ) T
_y [(x,y) T (y,z) (R S )]
_y [(x,y) T ((y,z) R (y,z) S ))]
_y [((x,y) T (y,z) R) ((x,y) T (y,z) S ))]
[_y ((x,y) T (y,z) R)] [_y ((x,y) T (y,z) S )]
(x,z) (R T) (x,z) (S T)
(x,z) (R T) (S T)

Ć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ę Parser nie mógł rozpoznać (nieznana funkcja „\kPs”): {\displaystyle \displaystyle R \subset \kPs{X} \times \kPs{X}} następująco: dla dowolnych zbiorów $A,B\subset X$ mamy

Parser nie mógł rozpoznać (nieznana funkcja „\kIff”): {\displaystyle \displaystyle (A,B)\in R \kIff A\kRSym B \subset Y. }

(Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle \kRSym} oznacza różnicę symetryczną zbiorów, czyli Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle A\kRSym B = (A\setminus B)\cup (B \setminus A)} ) Udowodnij, że relacja $R$ jest relacją równoważności. Najtrudniej jest pokazać przechodniość. Udowodnij, że Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle A \kRSym C \subset (B\kRSym C) \cup (A\kRSym 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 Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle A\kRSym A= \emptyset \subset Y} , a więc relacja $R$ jest zwrotna.
2. Ponieważ dla dowolnych zbiorów Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle A\kRSym B= B\kRSym 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

A C= (A C) (C A) =
(((A B) (A B)) C) (((C B) (C B)) A) =
((A B) C) ((A B) C) ((C B) A) ((C B) A)
(B C) (A B) (B A) (C B)=
(B C) (A B).

Ponieważ z definicji relacji $R$ mamy Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle (B\kRSym C) \in Y} orazParser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle (A\kRSym B)\in Y} to ich suma też jest podzbiorem $Y$ i konsekwencji również Parser nie mógł rozpoznać (nieznana funkcja „\kRSym”): {\displaystyle \displaystyle A\kRSym 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

Parser nie mógł rozpoznać (nieznana funkcja „\kOr”): {\displaystyle \displaystyle \forall_{x\in X}( [x]_R \subset [x]_S \kOr [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 Parser nie mógł rozpoznać (nieznana funkcja „\kOr”): {\displaystyle \displaystyle z\in [x]_R \kOr z \in [x]_S} co jest równoważne Parser nie mógł rozpoznać (nieznana funkcja „\kOr”): {\displaystyle \displaystyle x\in [z]_R \kOr x \in [z]_S} . Podobne rozumowanie dla $z$ daje Parser nie mógł rozpoznać (nieznana funkcja „\kOr”): {\displaystyle \displaystyle y\in [z]_R \kOr 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

(a,b) R S (a,b) R (a,b) S a[b]_R a [b]_S a [b]_R [b]_S.

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$:

r=0,1, 2,3
s=0,1, 2,3.

Ł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 \{ S\in\mathcal{P} (X^2) : R\subset S \hspace*{0.1mm} \wedge S\in\alpha \} } . 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 Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle n\in \nNat \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ę Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \kRodz} jako zbiór wszystkich skończonych wielokrotnych złożeń relacji $R$ z sobą, czyli Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \kRodz=\{r\subset X^2 : \exists_{n\in \nNat} (n\neq 0 \kAnd R^n=r)\}} . Do formalnego zdefiniowania rodziny Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \kRodz} 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 Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \bigcup \kRodz} . Pokażemy po kolei, że spełnia warunki domknięcia.

1. 1. Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle R=R^1 \subset \bigcup \kRodz}
   2. Aby pokazać, że relacja Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \bigcup \kRodz} jest przechodnia weźmy dowolne dwie pary Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle (a,b),(b,c) \in \kRodz} .

Wtedy muszą istnieć liczby Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle n,m \in \nNat} 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 Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle (a,c)\in R^{m+n} \subset \bigcup \kRodz} .

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

Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle n\in \nNat\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 Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle n\in \nNat\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 Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle n\in \nNat\setminus \{0\}} mamy $R^n\subset T$ to również Parser nie mógł rozpoznać (nieznana funkcja „\kRodz”): {\displaystyle \displaystyle \bigcup \kRodz \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 „\nNat”): {\displaystyle \displaystyle n\in\nNat\setminus\{0\}} mamy $(R^n{)}^{-1}=(R^{-1}{)}^n$. Dla relacji symetrycznych dostajemy więc $(R^n{)}^{-1}=R^n$. Wobec tego mamy

Parser nie mógł rozpoznać (nieznana funkcja „\nNat”): {\displaystyle \displaystyle (\bigcup\{R^n:n\in \nNat \setminus \{0\}\})^{-1} = \bigcup\{(R^n)^{-1}:n\in \nNat \setminus \{0\}\}= \bigcup\{R^n:n\in \nNat \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ą:

A &=z{P}(x) w z =w,
B &=z{P}(x y) w v (w v z=v,w),
C &=z{P}({P}(y)) v z=v=(v,v).

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

D_0 &=z{P}(A B) w v w v z=w,w,v=(w,v),

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

D_0' &=z{P}(D_0 C) w v w v z=(w,v),(v,v),

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

D_0" &=z{P}(D_0 C) w v w v z=(w,v),(w,w ),

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

x y &=z D_0' w v w v z=(w,v) z D_0" w z=(w,w).

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:

Parser nie mógł rozpoznać (nieznana funkcja „\mpipe”): {\displaystyle \displaystyle \pi_1(z) = \bigcup\{w\in\bigcup z\mpipe \exists u\; w=\{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 }$.