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: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
następna edycja →
WizualnieWikikod
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
 
Rogoda (dyskusja | edycje)
1875 edycji
Nie podano opisu zmian
Linia 1: Linia 1:
{tw}{Twierdzenie}[section]
{fa}[tw]{Fakt}
{AZbioruPustego}{Aksjomat Zbioru Pustego}
{APary}{Aksjomat Pary}
{ASumy}{Aksjomat Sumy}


{}{0pt}
{}{0pt}
{}{0in}
{}{-0.5in}
{}{6.3in}
{}{9in}
{cwicz}[section]
{obra}[section]
{hint}
{thm}{Twierdzenie}[section]
{defn}[thm]{Definicja}
{Zadanie}[thm]{Zadanie}
{Uwaga}[thm]{Uwaga}
{Przykład}[thm]{Przykład}
{Rozwiązanie}[thm]{Rozwiązanie}
{Hint}[thm]{Hint}
{equation}{section}
{kuba_preamble1}
{kuba_preamble2}
0mm
2ex
{lem}[thm]{ Lemat  }
{mtw}[tw]{Meta twierdzenie}
{Cwiczenie}[thm]{Ćwiczenie}
''' Logika i teoria mnogości'''
'''Wykład 5'''
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 <math>x</math> oraz <math>y</math> będą
zbiorami. Przez parę uporządkowaną <math>(x,y)</math> rozumiemy zbiór
<center><math>\left\{ \left\{x\right\}\, \left\{x,y\right\}\\right\}\\]
\enddefn
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|[Uzupelnij]||
Dla dowolnych zbiorów </math>a,b,c,d<math> zachodzi:
</math></center>(a,b) <nowiki>=</nowiki> (c,d)  a<nowiki>=</nowiki>c {0.1mm}  b<nowiki>=</nowiki> d<center><math>
}}
{{dowod|[Uzupelnij]||
Dowód przeprowadzimy tylko ze strony lewej do prawej bo w
odwrotnym kierunku jest to fakt oczywisty.
Niech zatem dwie pary </math>(a,b)<math> i </math>(c,d)<math> będą równe. Ponieważ
</math>a  (a,b)<math> więc    </math>a  (c,d)<math>. Mamy zatem
</math>a<nowiki>=</nowiki> c lub  <math>\left\{a\right\}\ = \left\{c,d\right\}\$. W pierwszym
przypadku </math>a<nowiki>=</nowiki>c<math> ale w drugim również jest tak, mamy bowiem, że
</math>c  a. Pierwszą część twierdzenia mamy za sobą bo już wiemy,
że pierwsze współrzędne równych par są równe.
<center><math>(a,b) = (a,d) </math></center>
Następnie przeprowadzamy dowód przez przypadki. Jeżeli jest tak,
że <math>a=b</math> to <math>(a,b)=\left\{\left\{a\right\}\\right\}\$. Zatem </math>a<br>right<nowiki>=</nowiki>
aa,d<br>right co daje, że <math>\left\{a,d\right\}\=\left\{a\right\}\$ a zatem
</math>d<nowiki>=</nowiki>a<math>. W przeciwnym przypadku gdy </math>a  b<math> mamy, że </math>a,b
aa,d<br>right. Daje to dwie możliwości albo
<math>\left\{a,b\right\}\ = \left\{a\right\}\$ co nie może mieć miejsca bo mielibyśmy, że </math>a<nowiki>=</nowiki>b<math>,
albo zaś
</math>a,b<nowiki>=</nowiki> a,d. To drugie prowadzi do naszej tezy <math>b=d</math>.
}}
Dla każdej pary <math>x=(a,b)</math> udowodnij, że
<center><math>\bigcap \bigcap x= a.
</math></center>
'''Rozwiązanie: '''Rozważymy dwa przypadki.
# Jeśli <math>a=b</math> to <math>x=\{\{a\}\}</math> i wtedy <math>\bigcap \bigcap x= a</math>.
# Jeśli <math>a\neq b</math> to <math>x=\{\{a\},\{a,b\}\}</math> a więc
<center><math>\bigcap x= \bigcap \{\{a\},\{a,b\}\}=  \{a\} \cap \{a,b\}= \{a\}
</math></center>
skąd otrzymujemy
<center><math>\bigcap \bigcap x=a
</math></center>
Udowodnij, że dla dowolnej pary uporządkowanej <math>x</math> zbiór
<center><math>\bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset))
</math></center>
jest pusty gdy współrzędne par są różne, a w przeciwnym przypadku jest
zbiorem jednoelementowym zawierającym współrzędną pary <math>x</math>.
'''Rozwiązanie: '''Jeśli <math>x</math> jest parą to istnieją zbiory <math>a,b</math> takie, że <math>x=(a,b)</math>.
# Przypuśćmy, że <math>a\neq b</math>. Wtedy <math>x= \{\{a\}, \{a,b\}\}</math> i <math>\mathcal{P}(x)=
\{\emptyset, \{\{a\}\}, \{\{a,b\}\},x \}</math>. Ponieważ <math>\mathcal{P}(\emptyset)=\{\emptyset\}</math>
to <math>\mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\}, \{\{a,b\}\},x \}</math> a wtedy
<center><math>\bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset
</math></center>
gdyż przecinany zbiór zawiera elementy rozłączne <math>\{\{a\}\}, \{\{a,b\}\}</math>.  Wobec
tego również
<center><math>\bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) = \emptyset
</math></center>
# W przypadku, gdy <math>a=b</math> otrzymujemy <math>x=\{\{a\}\}</math> a więc <math>\mathcal{P}(x)=\{\emptyset ,\{\{a\}\}\}</math> i wtedy <math>\mathcal{P}(x) \setminus \mathcal{P}(\emptyset) =\{ \{\{a\}\} \}</math> skąd otrzymujemy
<center><math>\bigcap \bigcap ( \kPs(x) \setminus \mathcal{P}(\emptyset)) = \{a\}
</math></center>
Pokaż, że z każdej pary <math>x</math> można otrzymać jej drugą współrzędną posługując się
jedynie parą <math>x</math>, mnogościowymi operacjami <math>\bigcup, \bigcap, \cup,\cap,\setminus,\kPs</math> oraz stałą <math>\emptyset</math>.
'''Wskazówka:  '''
# Rozważ najpierw pary różnych elementów.
# Wykorzystaj zbiór z Ćwiczenia [[##ex:paraPS|Uzupelnic ex:paraPS|]]
'''Rozwiązanie: '''Rozważmy najpierw przypadek gdy para ma różne elementy. Zobaczymy, że dla  każdej takiej pary <math>x=(a,b)</math> mamy
<center><math>
\bigcup (\bigcup x \setminus \bigcap x) =b.
</math></center>
Ponieważ <math>a\neq b</math> to <math>x=\{\{a\}, \{a,b\}\}</math> i wtedy
<center><math>\bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a,b\} \setminus \{a\})=
\bigcup \{b\}= b.
</math></center>
Zobaczmy teraz jak proponowany wzór działa na parach o równych współrzędnych. Jeśli
<math>x=(a,a)</math> to <math>x =\{\{a\}\}</math> i wtedy
<center><math>\bigcup (\bigcup x \setminus \bigcap x)= \bigcup (\{a\} \setminus \{a\})= \bigcup
\emptyset= \emptyset.
</math></center>
Musimy więc jeszcze trochę popracować. Wykorzystajmy  ćwiczenie [[##ex:paraPS|Uzupelnic ex:paraPS|]],
niech nowy wzór będzie postaci
<center><math>\bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset)).
</math></center>
Dla par o różnych elementach dodana część wzoru jest zbiorem pustym, więc ta sytuacja
jest analogiczna do [[##eq:cwiczeniePara2wsp1|Uzupelnic eq:cwiczeniePara2wsp1|]], skąd otrzymujemy że  tak
zdefiniowany zbiór jest równy <math>b</math>.
Dla par o równych elementach, pierwsza część zbioru jest zbiorem pustym. W ćwiczeniu
[[##ex:paraPS|Uzupelnic ex:paraPS|]] pokazaliśmy że w takim przypadku mamy <math>\bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset))=\{b\}</math> jeśli <math>b</math> jest współrzędną pary <math>x</math>. Wobec tego
<center><math>\bigcup (\bigcup x \setminus \bigcap x) \cup \bigcap \bigcap \bigcap (\mathcal{P}(x)
\setminus \mathcal{P}(\emptyset))= \emptyset \cup \bigcap\{b\}=b.
</math></center>
==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 <math>x\in X</math> oraz <math>y \in Y</math>.
Łatwo zauważyć, że zarówno
<math>\left\{x,y\right\}\$ jak i </math>x są podzbiorami <math>X \cup Y</math>.
Zatem
<math>\left\{x,y\right\}\ \in \mathcal{P} (X \cup Y)</math> oraz <math>\left\{x\right\}\ \in \mathcal{P} (X \cup Y)</math>.
Więc <math>\left\{\left\{x\right\}\,\left\{x,y\right\}\\right\}\ \subseteq  \mathcal{P} (X \cup Y)</math> co daje,
że <math>(x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y))</math>.
Istnienie i konstrukcja iloczynu
kartezjańskiego zostało dokładnie omówione  w dodatkowym
rozdziale [[##konstukcja_marcina|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 <math>x,y</math> będą zbiorami. Iloczynem kartezjańskim (produktem)
<math>x \times y</math> nazywamy zbiór
<center><math>\left\{z\in \mathcal{P}( \mathcal{P}( x \cup y)): \exists_{a \in x} \exists_{b \in y}
\;\; (a,b) =z\right\}\
</math></center>
Będziemy używać specjalnej notacji <math>x^2</math> na zbiór <math>x \times x</math>.
Pokaż następujące elementarne własności iloczynu kartezjańskiego:
<center><math>\alignedx \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</math></center>
'''Rozwiązanie: '''Z definicji iloczynu kartezjańskiego, oraz twierdzenia [[##para-up_tw|Uzupelnic para-up_tw|]] łatwo wynika
następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów <math>a,b,x,y</math>
zachodzi
<center><math>(a,b)\in x \times y \Leftrightarrow (a\in x \wedge b\in y).
</math></center>
# 
x    <nowiki>=</nowiki><br>
z {P}({P}(x  z)): _{a x} _{b } (a,b)<nowiki>=</nowiki>z<nowiki>=</nowiki><br>
z {P}({P}(x  z)): _{a x} _{b}[ (b  )  (a,b)<nowiki>=</nowiki>z]
Ponieważ <math>b\in \emptyset</math> jest zawsze fałszem to powyższy zbiór jest pusty.
# 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ę <math>(a,b)</math> wtedy
(a,b) x  (y  z) <br>
a  x  b (y z) <br>
a x  (b y  b z) <br>
(a x  b y)  (a x  b z) <br>
(a,b)  x  y  (a,b) x  z <br>
(a,b)  x  y  x  z.
# Analogicznie do poprzedniego punktu, weźmy dowolną parę <math>(a,b)</math>, wtedy
(a,b) x  (y  z) <br>
a  x  b (y z) <br>
a x  (b y  b z) <br>
(a x  b y)  (a x  b z) <br>
(a,b)  x  y  (a,b) x  z <br>
(a,b)  x  y  x  z.
# Analogicznie do poprzednich punktów, weźmy dowolną parę <math>(a,b)</math>, wtedy
(a,b)  (x  y)  (x  z)  <br>
a x  b y  (a x  b z) <br>
b y  (a x  (a x  b z)) <br>
b y  [(a x  a x)  (a x  b z)] <br>
b y  (a x  b z) <br>
a x  (b y  z) <br>
(a,b)  x  (y  z)
Produkt kartezjański <math>\times</math> jest monotoniczny ze względu na każdą współrzędną
osobno to znaczy:
<center><math>\alignedx \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</math></center>
'''Rozwiązanie: '''Ćwiczenie jest elementarne.
# Niech <math>x,y</math> będą dowolnymi zbiorami takimi, że <math>x\subset y</math>. Wtedy dla dowolnej pary <math>(a,b)</math> mamy
(a,b) x z <br>
a x  b  z <br>
a y  b  z <br>
(a,b) y z.
Stąd <math>(x \times z) \subset  (y \times z)</math>.
# Dla dowolnych zbiorów <math>x\subset y</math> mamy <math>x \cup y =y</math>. Z poprzedniego
ćwiczenia otrzymujemy
<center><math>z \times y =z \times (x\cup y) =  (z \times x)\cup(z \times y) \supset (z \times x).
</math></center>
(Metoda z poprzedniego punktu podziała równie dobrze.)
Sprawdź, czy dla dowolnych zbiorów <math>A,B,C</math>, prawdziwa jest następująca implikacja
<center><math>A\times B = A\times C \Rightarrow B=C
</math></center>
'''Rozwiązanie: '''Nie. Na przykład gdy <math>A=\emptyset</math> to dla dowolnych zbiorów <math>B,C</math> mamy
<center><math>\emptyset \times B =\emptyset = \emptyset \times C.
</math></center>
Biorąc różne zbiory <math>B,C</math> otrzymamy kontrprzykład dla badanej implikacji.
==Relacje==
Relacją nazywamy każdy podzbiór iloczynu <math>x
\times y</math> 
===Operacje na relacjach:===
Niech <math>R \subset A \times B</math> oraz <math>S \subset B \times C</math>.
<math>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\}\$
\bigskip
</math>R^{-1} :<nowiki>=</nowiki> (y,x) B  A :  (x,y) R
<math>R_L := \left\{x\in A : \exists_{y\in B} \;\; (x,y) \in R\right\}\$
</math>R_P :<nowiki>=</nowiki> y B : _{x A}  (x,y)  R
Niech relacja  <math> R \subset A \times B,  S \subset B \times C</math> oraz
<math>T \subset C \times  D</math>. Pokazać elementarne własności operacji na relacjach:
<center><math>\alignedT \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</math></center>
'''Rozwiązanie: '''Ćwiczenie jest elementarne.
# 
(x,z) T  ( S  R ) <br>
_{u} [(x,u) ( S  R )  (u,z) T]<br>
_{u} [_{v}( (x,v)  R (v,u)  S)  (u,z) T]<br>
_{u} _{v}[ (x,v)  R (v,u)  S  (u,z) T]<br>
_{v} _{u}[ (x,v)  R ((v,u)  S  (u,z) T)]<br>
_{v} [ (x,v)  R _{u}((v,u)  S  (u,z) T)]<br>
_{v} [ (x,v)  R (v,z)  T  S]<br>
(x,z)  (T  S)  R <br>
# 
(x,z) (S  R )^{-1}  <br>
(z,x)  S R  <br>
_{y} [(z,y)  R  (y,x) S]  <br>
_{y} [(y,z)  R^{-1}  (x,y) S^{-1}]  <br>
(x,z)  R^{-1}  S^{-1} <br>
# 
(x,z) R  <br>
_{y} (x,u)  R  _{v} (v,y) R <br>
x R_L  y R_P  <br>
(x,y)  R_L  R_P
# 
x  (S  R)_L    <br>
_{z} (x,z) S R <br>
_{z} _{y} [(x,y) R  (y,z) S ]  <br>
_{z} _{y} (x,y) R  <br>
_{y} (x,y) R  <br>
x  R_L
# Dowód <math>(S \circ R)_P \subset  S_P </math> jest analogiczny do poprzedniego.
# 
x (R^{-1} )_L  <br>
_{y} (x,y) R^{-1} <br>
_{y} (y,x) R <br>
x  R_P
Niech relacja  <math> R \subset B \times C,  S \subset B \times C</math> oraz
<math>T \subset A \times  B</math>. Pokaż własności:
<center><math>\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</math></center>
'''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}  <br>
(y,x) (R S)  <br>
(y,x) R  (y,x)  S  <br>
(x,y) R^{-1}  (x,y)  S^{-1}  <br>
(x,y) R^{-1}  S^{-1}
# Dowód drugiej równości jest analogiczny do dowodu pierwszej, wystarczy użyć <math>\cap</math> w miejsce <math>\cup</math> oraz <math>\wedge</math> w miejsce <math>\vee</math>.
# 
(x,y) (R^{-1})^{-1}  <br>
(y,x) R^{-1}  <br>
(x,y) R
# 
(x,z) (R  S )  T  <br>
_y [(x,y)  T  (y,z) (R  S )] <br>
_y [(x,y)  T  ((y,z) R  (y,z) S ))] <br>
_y [((x,y)  T  (y,z) R)  ((x,y)  T  (y,z) S ))] <br>
[_y ((x,y)  T  (y,z) R)]  [_y ((x,y)  T  (y,z) S )] <br>
(x,z) (R  T)  (x,z) (S  T)  <br>
(x,z)  (R  T)  (S  T)
# 
(x,z) (R  S )  T  <br>
_y [(x,y)  T  (y,z) (R  S )] <br>
_y [(x,y)  T  ((y,z) R  (y,z) S ))] <br>
_y [((x,y)  T  (y,z) R)  ((x,y)  T  (y,z) S ))] <br>
[_y ((x,y)  T  (y,z) R)]  [_y ((x,y)  T  (y,z) S )] <br>
(x,z) (R  T)  (x,z) (S  T)  <br>
(x,z)  (R  T)  (S  T)
Podaj przykład relacji dla których poniższa równość nie jest prawdziwa.
<center><math>(R \cap  S ) \circ T =  (R \circ T) \cap (S  \circ T)
</math></center>
'''Rozwiązanie: '''Niech <math>R=\{(1,3)\}, S= \{(2,3)\}, T=\{(0,1),(0,2)\}</math> wtedy
# <math>R\cap S=\emptyset</math> więc      <math>(R\cap S)\circ T=\emptyset</math>.
# <math>T\circ R =\{(0,3)\}</math> i <math>T \circ S=\{0,3\}</math> a więc
<math>(R \circ T) \cap (S  \circ T) =\{0,3\}</math>
Udowodnij, że zbiór <math>A</math> jest relacją wtedy i tylko wtedy gdy
<center><math>A \subset (\bigcup \bigcup A) \times  (\bigcup \bigcup A)
</math></center>
'''Rozwiązanie: '''Pokażemy najpierw, że dla każdej relacji <math>R</math> mamy
<center><math>
\bigcup \bigcup R = R_L \cup R_P.
</math></center>
Zaczniemy od inkluzji <math>\subset</math>.Weźmy dowolny element <math>x \in \bigcup \bigcup R</math> wtedy
musi istnieć element <math>y\in \bigcup R</math> taki że <math>x\in y</math>. Skoro <math>y\in \bigcup R</math> to
musi istnieć para <math>(a,b) \in R</math> taka, że <math>y\in (a,b)</math>. Wobec tego z definicji pary
uporządkowanej <math>y=\{a\}</math> lub <math>y=\{a,b\}</math>. Ponieważ <math>x\in y</math> to <math>x=a</math> i wtedy <math>x\in
R_L</math> lub <math>x=b</math> i wtedy <math>x\in R_P</math>. Wobec tego <math>x\in R_L \cup R_P</math>.
Pokażemy teraz prawdziwość inkluzji <math>\supset</math> w równaniu [[##eq:cwiczenieBCBC|Uzupelnic eq:cwiczenieBCBC|]].
Weźmy dowolny element <math>a\in R_L</math> wtedy istnieje element <math>b\in R_P</math> taki, że <math>(a,b)\in
R</math>, a więc <math>\{(a,b)\} \subset R</math>. Stąd otrzymujemy
<center><math>\bigcup \bigcup \{(a,b)\} \subset \bigcup \bigcup R.
</math></center>
Ponieważ  <math>\bigcup \bigcup \{(a,b)\}= \bigcup \{\{a\},\{a,b\}\} = \{a,b\}</math> to
otrzymujemy <math>\{a,b\} \subset R</math>, a więc <math>a\in R</math>. Analogiczne rozumowanie można
przeprowadzić dla elementu <math>b\in R_P</math>. Zakończyliśmy więc dowód równości
[[##eq:cwiczenieBCBC|Uzupelnic eq:cwiczenieBCBC|]].
W temacie ćwiczenia implikacja w lewą stronę jest oczywista. Jeśli <math>A</math> jest zbiorem
to <math>\bigcup \bigcup A</math> jest zbiorem i <math>A</math> jest podzbiorem iloczynu kartezjańskiego
dwóch zbiorów więc musi być relacją. Dla implikacji w prawą stronę załóżmy, że <math>A</math>
jest relacją wtedy
<center><math>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)
</math></center>
== 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 <math>8</math> w którym
zaprzęgniemy relacje abstrakcji do definiowania liczb.
Rozpoczynamy rozdział od koniecznej definicji.
Dla zbioru <math>X</math> definiujemy relację <math>1_X \subset X \times X</math>
jako <math>\left\{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z  \right\}\$.
\enddefn
\begindefn
Relację </math>R  X  X<math> nazywamy relacją równoważnością o
polu </math>X<math> jeżeli:
* zawiera relacje </math>1_X <math> (zwrotność </math>R<math>)
* </math>R^{-1}  R<math> (symetria </math>R<math>)
* </math>R  R  R<math> (przechodniość </math>R<math>)
\enddefn
\beginCwiczenie
Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu </math>X<math>
są odpowiednio równoważne następującym własnościom:
* </math>_{ x X} (x,x)  R<math>
* </math>_{ x,y  X} (x,y)  R  (y,x)  R<math>
* </math>_{ x,y,z X} (x,y) R  (y,z)  R  (x,z) R<math>
\textbf{Rozwiązanie: }Ćwiczenie jest elementarne.
\endCwiczenie
\begindefn  Niech </math>R<math> będzie relacją równoważności o
polu </math>X<math>. Klasą równoważności elementu </math>x X<math> jest zbiór
</math></center>[x]_R :<nowiki>=</nowiki> y  X : (x,y)  R<center><math>
\enddefn 
\begindefn  Zbiór klas równoważności relacji </math>R<math> będący elementem zbioru </math>{P}
( {P} (X  X))<math> oznaczamy przez </math>X/R<math>. \enddefn 
{{twierdzenie|[Uzupelnij]||
Niech </math>R<math> będzie relacją równoważności o polu </math>X<math>. Następujące warunki są równoważne
# </math>[x]_R  [y]_R  <math>
# </math>[x]_R <nowiki>=</nowiki> [y]_R<math>
# </math>(x,y)  R<math>
}}
{{dowod|[Uzupelnij]||
Pokażemy, że </math>(1) (2)<math>. Niech wspólny element dwóch klas </math>[x]_R<math> oraz
</math>[y]_R<math> nazywa się </math>z<math>. Ze względu na pełną symetrię tezy wystarczy pokazać, że
</math>[x]_R  [y]_R<math>. Niech zatem </math>p [x]_R<math>. Mamy więc </math>(x,p)  R<math>. Z
założenia jest również
</math>(y,z)  R<math> oraz </math>(x,z)  R<math>. Z symetrii otrzymujemy </math>(z,x)
R<math>.
Zatem </math>(y,z)  R<math> i </math>(z,x)  R<math> i </math>(x,p)  R<math>.
Natychmiast z przechodniości otrzymujemy, że </math>(y,p)  R<math>.\\
Pokażemy, że </math>(2) (3)<math>. Ze zwrotności mamy, że
</math>y [y]_R<math> co z założenia </math>(2)<math> daje  </math>y [x]_R<math> a to tłumaczy
się na </math>(x,y)  R<math>.
Pokażemy, że </math>(3) (1)<math>.
Wystarczy pokazać, że wspólnym elementem klas </math>[x]_R<math> oraz </math>[y]_R<math>
jest </math>y<math>. Dla pierwszej z nich wynika to z założenia </math>(3)<math> a dla
drugiej ze zwrotności </math>R<math>.
}}
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|[Uzupelnij]||
Niech  będzie pewną rodziną
(zbiorem) relacji równoważności o tym samym polu </math>X<math>. Mamy że:
#  jest relacją równoważności o polu </math>X<math>.
# </math>[x]_{  } <nowiki>=</nowiki>  [x]_R : R
}}
{{dowod|[Uzupelnij]||
<math>(1)</math> Zwrotność <math>\bigcap \kappa </math> jest oczywista ponieważ <math>1_X </math> zawiera
się w każdej relacji rodziny <math>\kappa </math>. Symetria. Weźmy <math>(x,y)\in
\bigcap \kappa </math>. Dla każdej relacji <math>R\in\kappa</math> jest <math>(x,y)\in R
</math>. Z symetrii każdej <math>R</math> jest więc <math>(y,x)\in R </math> co daje <math>(y,x)\in
\bigcap \kappa </math>. Przechodniość. Niech <math>(x,y)\in \bigcap \kappa </math>
oraz <math>(y,z)\in \bigcap \kappa </math>. Dla każdej relacji <math>R\in\kappa</math>
jest więc <math>(x,y)\in R</math> i <math>(y,z)\in R</math>. Z przechodniości każdej
relacji <math>R</math> mamy, że <math>(x,z) \in R</math> co daje <math>(x,z)\in \bigcap \kappa
</math>.<br>
<math>(2)</math> Niech <math>y \in [x]_{ \bigcap \kappa }</math>. Mamy zatem, że
<math>(x,y) \in \bigcap \kappa</math> co daje <math>(x,y)\in R</math> dla każdej
relacji <math>R\in\kappa</math>. To zaś daje, że <math>y \in [x]_R</math> dla każdej <math>R \in \kappa</math> co
jest równoważne z <math>y\in\bigcap \left\{[x]_R : R\in \kappa\right\}\$.
}}
W szczególności przecięcie wszystkich relacji
równoważności o polu </math>X<math> daje </math>1_X<math>.  Jest ona najsilniejszą
relacją równoważności. Najsłabszą jest </math>X^2<math>.
===Rozkłady zbiorów===
\begindefn
Niech </math>X  <math>. Rodzinę
</math>r  {P} ( {P} (X))<math> nazywamy rozkładem zbioru </math>X<math> gdy
# </math>_{C  r}  C  <math>
# </math> r <nowiki>=</nowiki>X<math>
# </math>(C  r {0.1mm}  D  r {0.1mm}  C  D ){0.1mm}  C D <nowiki>=</nowiki><math>
\enddefn 
{{lemat|[Uzupelnij]||
Dla relacji równoważności </math>R<math> o polu </math>X<math> zbiór </math>X/R<math> jest rozkładem
</math>X<math>. }}
{{dowod|[Uzupelnij]||
</math>(1)<math> Każda klasa jest niepusta bo zawiera element, który ją
wyznacza.
</math>(2) X/R  X<math> bo każda klasa jest podzbiorem
</math>X<math>. Odwrotnie każdy </math>x  [x]_R  X/R<math>.
</math>(3)<math> Dwie klasy gdy są rożne muszą być rozłączne co udowodniliśmy
w twierdzeniu [[##thm:rownowaznosc|Uzupelnic thm:rownowaznosc|]].
}}
\begindefn  Niech </math>r<math> będzie rozkładem zbioru </math>X<math>. Definiujemy relacje </math>R_r
X  X<math> następująco:
</math></center>(x,y)  R_r  wtw  _{C r}  x  C  {0.1mm}    y C
<center><math>
\enddefn 
{{lemat|[Uzupelnij]||
Dla rozkładu </math>r  {P} ( {P}
(X))<math> relacja </math>R_r<math> jest:
# równoważnością
# </math>X/{R_r} <nowiki>=</nowiki> r<math>
}}
{{dowod|[Uzupelnij]||
</math>(1)<math> Relacja </math>R_r<math> jest zwrotna każdy bowiem </math>x X<math> musi leżeć w pewnym zbiorze
</math>C<math> rozkładu </math>r<math>. Symetria </math>R_r<math> nie wymaga dowodu. Przechodniość </math>R_r<math>. Niech </math>(x,y)
R_r<math> i </math>(y,z)  R_r<math>. Istnieją zatem dwa zbiory </math>C<math> i </math>D<math> rozkładu </math>r<math> takie,
że </math>x,y  C<math> oraz </math>y,z  D<math>. Przecięcie </math>C<math> i </math>D<math> jest więc niepuste zatem
</math>C<nowiki>=</nowiki>D<math> co daje tezę </math>(x,z)  R_r<math>.\\
</math>(2)<math> Inkluzja w prawo . Niech </math>C  X/{R_r}<math>. Klasa
</math>C<math> jest zatem wyznaczona przez pewien element </math>x<math> taki, że </math>C<nowiki>=</nowiki> [x]_{R_r}<math>.
Niech </math>D r<math> będzie zbiorem rozkładu </math>r<math> do którego należy </math>x<math>.
Łatwo wykazać, że </math>C<nowiki>=</nowiki>D<math>. Inkluzja w lewo .
Niech </math>C  r<math>. </math>C<math> jest niepusty wiec istnieje </math>x  C<math>. Klasa
</math>[x]_{R_r} <nowiki>=</nowiki>C<math>.
}}
\beginCwiczenie
Niech </math>X<math> będzie niepustym zbiorem, oraz niech </math>Y  X<math>. Zdefiniujemy relację </math>R  {P}(X)  {P}(X)<math> następująco:
dla dowolnych zbiorów </math>A,B  X<math> mamy
</math></center>(A,B) R  A{.}{} B  Y.
<center><math>
(</math>{.}{}<math> oznacza różnicę symetryczną zbiorów, czyli </math>A{.}{} B <nowiki>=</nowiki> (A B)
(B  A)<math>) Udowodnij, że relacja </math>R<math> jest relacją równoważności.
\textbf{Wskazówka:  }
Najtrudniej jest pokazać przechodniość. Udowodnij, że </math>A {.}{} C    (B{.}{} C)  (A{.}{} B)<math>. Dobrym punktem wyjścia
jest naszkicowanie wszystkich przecięć zbiorów </math>A,B,C<math>.
\textbf{Rozwiązanie: }Pokażemy po kolei zwrotność, przechodniość i symetryczność.
# Dla każdego </math>A X<math> mamy </math>A{.}{} A<nowiki>=</nowiki>  Y<math>, a więc relacja </math>R<math> jest zwrotna.
# Ponieważ dla dowolnych zbiorów </math>A{.}{} B<nowiki>=</nowiki> B{.}{} A<math> to </math>(A,B) R<math> wtedy i tylko wtedy gdy </math>(B,A) R<math>. Wobec tego relacja </math>R<math> jest symetryczna.
# Weźmy zbiory </math>A,B,C  X<math>, takie że </math>(A,B), (B,C)  R<math>. Wtedy
\beginalign*
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).
\endalign*
Ponieważ z definicji relacji </math>R<math> mamy  </math>(B{.}{} C)  Y<math> oraz</math> (A{.}{} B) Y<math> to ich suma też jest podzbiorem </math>Y<math>
i konsekwencji również </math>A{.}{} C  Y<math>. Oznacza to, że </math>(A,C) R<math>, a więc relacja </math>R<math> jest przechodnia.
\endCwiczenie
\beginCwiczenie
Udowodnij, że dla relacji równoważności </math>R,S<math> na zbiorze </math>X<math>, relacja </math>R S<math> jest relacją równoważności
wtedy i tylko wtedy gdy
</math></center>
_{x X}( [x]_R  [x]_S  [x]_R  [x]_S).
<center><math>
Podaj przykłady relacji równoważności </math>R,S<math> takich, że </math>R S<math> jest relacją
równoważności oraz </math>R S<math> i </math>S R<math>.
\textbf{Wskazówka:  }
Przyjrzyj się dokładnie rodzinie zbiorów </math>A<nowiki>=</nowiki>[x]_R  [x]_S : x X<math>.
\textbf{Rozwiązanie: }Zaczniemy od pokazania, że formuła </math>[[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]]<math> implikuje, że relacja
</math>R S<math> jest relacją równoważności. Pokażemy, że rodzina </math>A<nowiki>=</nowiki>[x]_R  [x]_S :
x X<math> tworzy rozkład zbioru </math>X<math>. Oczywiście, dla każdego elementu </math>x X<math> mamy
</math>[x]_R  [x]_S  <math> oraz </math>x [x]_R  [x]_S<math>. Wystarczy więc
pokazać, że zbiory w rodzinie </math>A<math> są rozłączne. Weźmy dowolne dwa elementy rodziny
</math>A<math> i przypuśćmy, że ich przecięcie jest niepuste. Niech to będą zbiory odpowiadające
elementom </math>x,y X<math> a więc </math>[x]_R  [x]_S<math> oraz </math>[y]_R  [y]_S<math>. Skoro te
zbiory mają niepuste przecięcie to istnieje </math>z ([x]_R  [x]_S) ([y]_R
[y]_S)<math>. Ponieważ </math>z [x]_R  [x]_S<math> to </math>z [x]_R  z  [x]_S<math> co jest
równoważne </math>x [z]_R  x  [z]_S<math>. Podobne rozumowanie dla </math>z<math> daje </math>y
[z]_R  y  [z]_S<math>. Wobec czego dostajemy </math>x,y  [z]_R  [z]_S<math> ponieważ
jednak zgodnie z formułą [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jedna z tych klas jest nadzbiorem
drugiej, to </math>x,y  [z]_R<math> lub  </math>x,y  [z]_S<math>. W przypadku, gdy </math>[z]_R
[z]_S<math> dostajemy również z [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] </math>[z]_R<nowiki>=</nowiki>[x]_R [x]_S<math> oraz
</math>[z]_R<nowiki>=</nowiki>[y]_R [y]_S<math> wobec czego otrzymujemy </math>[x]_R  [x]_S <nowiki>=</nowiki>[z]_R<nowiki>=</nowiki>[y]_R
[y]_S<math>. Drugi przypadek jest analogiczny. Wobec czego rodzina </math>A<math> jest rozkładem
zbioru </math>X<math>. Wystarczy teraz przekonać się że </math>(a,b) R S<math> wtedy i tylko wtedy,
gdy </math>a  [b]_R  [b]_S<math>, aby udowodnić, że jest to rzeczywiście rozkład
generowany przez relację </math>R S<math>. Weźmy dowolne </math>a,b  X<math> wtedy
\beginalign*
(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.
\endalign*
Pokażemy teraz, że jeśli </math>R S<math> jest relacją równoważności to musi być spełniona
formuła [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]]. Dla dowodu nie wprost przypuśćmy, że nie jest
spełniona. Oznacza to, że istnieje element </math>x X<math> dla którego </math>[x]_R
[x]_S<math> oraz </math>[x]_R  [x]_S<math>. Wobec tego istnieje </math>y [x]_R
[x]_S<math> oraz </math>z  [x]_S  [x]_R<math>. Oznacza to, że </math>(y,x) R S<math>
oraz </math>(x,z) S R<math>. Skoro </math>R S<math> jest relacją równoważności to </math>(z,y)
R S<math>. Przypuśćmy, że </math>(z,y) R<math>. Wtedy </math>(z,y),(y,x) R<math> wobec czego
</math>(z,x) R<math> co jest sprzeczne z tym że </math>(x,z) S R<math> ponieważ relacja </math>R<math>
jest symetryczna. Analogiczną sprzeczność otrzymujemy dla </math>(z,x) S<math>. Obie
możliwości prowadzą do sprzeczności, a więc formuła [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] musi być
spełniona.
Na koniec podajemy przykład relacji równoważności, równoważności </math>R,S<math> takich, że
</math>R S<math> jest relacją równoważności oraz </math>R S<math> i </math>S R<math>. Polem
relacji będzie zbiór </math>X<nowiki>=</nowiki>0,1,2,3<math>. Relacje </math>R,S<math> określimy poprzez wyznaczane
przez nie rozkłady odpowiednio </math>r,s<math>:
\beginalign*
r=\{\{0\},\{1\}, \{2,3\}\}\\
s=\{\{0,1\}, \{2\},\{3\}\}.
\endalign*
Łatwo sprawdzić, że </math>R S<math> i </math>S R<math>, gdyż </math>(2,3) R S<math>
oraz </math>(0,1) S R<math>. Z rozkładów </math>r,s<math> łatwo wynika, że formuła
[[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jest prawdziwa dla tych relacji, wobec czego </math>R S<math> jest
relacją równoważności. Wyznaczany przez nią rozkład to </math>0,1,2,3<math>.
\endCwiczenie
===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.
\begindefn
Niech  będzie rodziną relacji o polu
</math>X<math>, czyli niech </math>  {P} ( {P} (X^2))<math>.
Rodzina  jest zamknięta na przecięcia gdy
# </math>X^2  <math>
# jeżeli </math>  '  <math> to  </math>
'  <math>
\enddefn 
Poniżej podamy definicję domknięcia relacji w pewnej klasie (zbiorze) relacji.
Definiujemy intuicyjnie najmniejszą relacje zawierającą daną  należącą do klasy.
\begindefn
Relacja </math>S  X^2<math> jest domknięciem relacji </math>R  X^2<math> w klasie (zbiorze)
relacji  gdy:
# </math>R  S<math>
# </math>S  <math>
# dla każdej relacji </math>T<math> jeżeli </math>R  T<math> oraz </math>T  <math> to </math>S  T<math>
\enddefn 
{{lemat|[Uzupelnij]||
Domknięcie relacji (w dowolnej klasie) jeżeli istnieje to jest jedyne. }}
{{dowod|[Uzupelnij]||
Gdyby istniały dwa domknięcia pewnej relacji to ze względu na warunek </math>(3)<math> wzajemnie
by się zawierały.
}}
{{twierdzenie|[Uzupelnij]||
Następujące warunki są równoważne:
# Klasa relacji  jest domknięta na przecięcia.
# Każda relacja ma domknięcie w klasie relacji .
}}
{{dowod|[Uzupelnij]||
</math>(1)  (2)<math>. Niech </math>R<math> będzie relacją. Utwórzmy zbiór relacji </math> '<math>
jako </math> S{P} (X^2) : R S {0.1mm}  S . Takie <math>\alpha '</math> nie jest
puste bowiem relacja totalna <math>X^2</math> należy do <math>\alpha '</math>. Pokażmy, że <math>\bigcap \alpha
'</math> jest domknięciem <math>R</math> w <math>\alpha</math>. Istotnie <math>R\subset \bigcap \alpha '</math>. Z założenia
mamy też <math>\bigcap \alpha ' \in \alpha</math>. Minimalność <math>\bigcap \alpha '</math> stwierdzamy
przez: niech <math>R \subset S'</math> takie że <math>S' \in \alpha</math>.  Takie <math>S'</math> musi leżeć w
zbiorze <math>\alpha '</math> jest
więc <math>\bigcap \alpha ' \subset S' </math>.<br>
<math>(2) \rightarrow (1)</math>. Po pierwsze <math>X^2</math> leży w zbiorze <math>\alpha</math> bo wystarczy domknąć
<math>X^2</math>. Niech <math>\alpha '</math> będzie niepustym podzbiorem <math>\alpha</math>. Niech <math>S_0</math> będzie
domknięciem <math>\bigcap \alpha '</math> w <math>\alpha</math>. Wiemy, że dla dowolnej relacji <math>S'</math>  o ile
<math>\bigcap \alpha ' \subset S'</math> i <math>S'\in \alpha</math> to <math>S_0 \subset S'</math>. Połóżmy za <math>S'</math>
dowolny element z <math>\alpha '</math>. Założenia implikacji pozostają automatycznie spełnione,
jest więc tak, że <math>S_0 \subset S'</math> dla dowolnej <math>S'</math> wyjętej z <math>\alpha '</math>. W takim
razie <math>S_0 \subset \bigcap \alpha '</math>. Ponieważ mamy też <math>  \bigcap \alpha '\subset
S_0</math> bo <math>S_0</math> było domknięciem jest więc <math>\bigcap \alpha '= S_0</math> a to oznacza, że
<math>S_0 \in \alpha</math>.
}}
Pokazać jak wyglądają domknięcia w klasie relacji,
zwrotnych, symetrycznych i przechodnich.
Pokazać stosując twierdzenie [[##thm:domkniecie|Uzupelnic thm:domkniecie|]], że nie istnieje domknięcie spójne
ani antysymetryczne. (Relacja <math>R</math> jest spójna gdy <math>\forall x,y (x,y) \in R \hspace*{0.1mm} \vee
(y,x)\in R</math>. Relacja <math>R</math> jest antysymetryczna gdy z faktu, że <math>(x,y) \in R</math> oraz
<math>(y,x) \in R</math> da się pokazać, że <math>x=y</math>)
'''Rozwiązanie: '''Ćwiczenie jest elementarne.
# Pokażemy, że dla każdej relacji <math>R\in X^2</math> jej domknięcie w klasie relacji zwrotnych na <math>X</math> to <math>R\cup 1_X</math>.
Pokażemy po kolei, że spełnia warunki domknięcia.
## <math>R \subset R \cup 1_X</math>
## <math>1_X \subset R \cup 1_X</math>, a więc jest zwrotna
## weźmy dowolną zwrotną relację <math>T\supset R</math>. Ponieważ <math>T</math> jest zwrotna to <math>T\supset 1_X</math>, a więc <math>T\supset R \cup 1_X</math>.
# Pokażemy, że dla każdej relacji <math>R\in X^2</math> jej domknięcie w klasie relacji symetrycznych na <math>X</math> to <math>R\cup R^{-1}</math>.
Pokażemy po kolei, że spełnia warunki domknięcia.
## <math>R \subset R \cup R^{-1}</math>
## <math>(R \cup R^{-1})^{-1} = R^{-1} \cup (R^{-1})^{-1}= R^{-1} \cup R= R \cup R^{-1} </math>, a więc jest symetryczna
## weźmy dowolną symetryczną relację <math>T\supset R</math>. Ponieważ <math>T</math> jest symetryczna to
<math>T \supset T^{-1}</math>. Skoro <math>T \supset R</math> to <math>T^{-1} \supset R^{-1}</math>. Ponieważ <math>T \supset T^{-1}</math> to <math>T\supset R\cup R^{-1}</math>.
# 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 <math>n\in N \setminus\{0\}</math> przez <math>R^n</math>
będziemy oznaczać <math>n</math>-krotne złożenie relacji <math>R</math> z sobą (czyli <math>R^1=R</math> oraz <math>R^{n+1}= R^n \circ R</math> dla <math>n>1</math>).
Zdefiniujmy rodzinę <math>\mathcal{R}</math> jako zbiór wszystkich skończonych wielokrotnych złożeń
relacji <math>R</math> z sobą, czyli <math>\mathcal{R}=\{r\subset X^2 : \exists_{n\in N}  (n\neq 0
\wedge R^n=r)\}</math>. Do formalnego zdefiniowania rodziny <math>\mathcal{R}</math> 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 <math>R</math> w
klasie relacji przechodnich na <math>X</math> to relacja <math>\bigcup \mathcal{R}</math>.
Pokażemy po kolei, że spełnia warunki domknięcia.
## <math>R=R^1 \subset \bigcup \mathcal{R}</math>
## Aby pokazać, że relacja <math>\bigcup \mathcal{R}</math> jest przechodnia weźmy dowolne dwie pary <math>(a,b),(b,c) \in \mathcal{R}</math>.
Wtedy muszą istnieć liczby <math>n,m \in N</math> takie, że <math>(a,b)\in R^n</math> oraz <math>(b,c)\in R^m</math>. Wobec tego <math>(a,c)\in R^m \circ R^n</math>.
Z łączności składania relacji wynika, że <math>R^m \circ R^n= R^{m+n}</math>. Wobec tego <math>(a,c)\in R^{m+n} \subset \bigcup \mathcal{R}</math>.
## Weźmy dowolną przechodnią relację <math>T</math> taką, że <math>R\subset T</math> pokażemy indukcyjnie, że dla każdego
<math>n\in N\setminus \{0\}</math> mamy <math>R^n\subset T</math>.
### Baza indukcji. Dla <math>n=1</math> mamy <math>R^1=R</math> a więc z założenia <math>R^1\subset T</math>.
### Krok indukcyjny. Weźmy dowolne <math>n\in N\setminus \{0,1\}</math> i przypuśćmy, że dla każdego <math>0<m<n</math>
zachodzi <math>R^m\subset T</math>. Weźmy dowolną parę <math>(a,c)\in R^n</math>. Ponieważ <math>n>1</math> to <math>R^n= R^{n-1} \circ R</math>.
Oznacza to, że istnieje element <math>b\in X</math> taki, że <math>(a,b)\in R</math> oraz <math>(b,c)\in R^{n-1}</math>. Z założenia
indukcyjnego wynika, że <math>(a,b)\in T</math> oraz <math>(b,c)\in T</math>. Ponieważ <math>T</math> jest przechodnia to <math>(a,c)\in T</math>.
Wobec dowolności wyboru pary <math>(a,c)</math> otrzymujemy <math>R^n \subset T</math>.
Skoro dla każdego <math>n\in N\setminus \{0\}</math> mamy <math>R^n \subset T</math> to również <math>\bigcup \mathcal{R} \subset T</math>.
Pokażemy teraz że istnieje zbiór <math>X</math> taki, że klasa relacji spójnych na zbiorze <math>X</math> i
klasa relacji symetrycznych na zbiorze <math>X</math> nie są domknięte na przecięcia. W obliczu
twierdzenia [[##thm:domkniecie|Uzupelnic thm:domkniecie|]] będzie to oznaczało, że nie wszystkie relacje mają
domknięcia  w tych klasach. Niech <math>X=\{0,1\}</math>.
# Relacje <math>\{(0,1),(0,0),(1,1)\}, \{(1,0),(0,0),(1,1)\}</math> są spójne na <math>X</math>, a ich
przecięcie czyli zbiór <math>\{(0,0),(1,1)\}</math> nie jest.
# Relacja <math>X^2</math> nie jest antysymetryczna, a więc klasa relacji antysymetrycznych na <math>X</math>
nie jest domknięta na przecięcia.
Dla relacji <math>R</math> niech <math>R^\alpha</math>, <math>R^\beta</math>, <math>R^\gamma</math> oznaczają odpowiednio
zwrotne, symetryczne, przechodnie domknięcie relacji <math>R</math>. Czy
prawdą jest że:
# dla dowolnej relacji <math>R</math> relacja
<math>((R^\alpha)^\beta)^\gamma</math> jest relacją równoważności
# dla dowolnej relacji <math>R</math> zachodzi
<center><math>((R^\alpha)^\beta)^\gamma =((R^\gamma)^\beta)^\alpha
</math></center>
W każdym z powyższych przypadków proszę podać dowód lub
kontrprzykład.
'''Rozwiązanie: '''
# Zaczniemy od pokazania, że dowolne domknięcie relacji zwrotnej jest zwrotne. Rozważamy relacje na zbiorze <math>X</math>. Z definicji zwrotności mamy
<math>R</math> jest zwrotna wtedy i tylko wtedy gdy <math>R\supset 1_X</math>. W definicji domknięcia [[##defn:domkniecie|Uzupelnic defn:domkniecie|]] punkt pierwszy mówi, że jeśli <math>S</math> jest
domknięciem to <math>S\supset R</math>. Wobec tego konieczne jest aby <math>S\supset 1_X</math>. 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 <math>R^\alpha</math> jest zwrotna, to również zwrotna musi być <math>((R^\alpha)^\beta)^\gamma</math>.
Pokażemy teraz, że przechodnie domknięcie relacji symetrycznej jest symetryczne. Wykorzystamy charakteryzację domknięcia przechodniego z ćwiczenia
[[##ex:charakteryzacjeDomkniec|Uzupelnic ex:charakteryzacjeDomkniec|]]. Można łatwo pokazać indukcyjnie, że dla dowolnego <math>n\inN\setminus\{0\}</math> mamy <math>(R^n)^{-1}=(R^{-1})^n</math>.
Dla relacji symetrycznych dostajemy więc <math>(R^n)^{-1}=R^n</math>. Wobec tego mamy
<center><math>(\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\}\}
</math></center>
a więc przechodnie domknięcie relacji symetrycznej jest symetryczne. Oznacza to, że
relacja <math>((R^\alpha)^\beta)^\gamma</math> 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.
# Pokażemy relację <math>R</math> dla której relacja <math>((R^\gamma)^\beta)^\alpha</math> nie jest przechodnia. Ponieważ relacja <math>((R^\alpha)^\beta)^\gamma</math>
jest przechodnia, będzie to oznaczało że te relacje są różne. Niech <math>X=\{0,1,2\}</math> oraz <math>R=\{(0,2),(1,2)\}</math>. Relacja <math>R</math> jest przechodnia
więc <math>R^\gamma=R</math> jej symetryczne domknięcie to <math>(R^\gamma)^\beta=\{(0,2),(2,0),(1,2),(2,1)\}</math>. I po zwrotnym domknięciu otrzymujemy
<math>((R^\gamma)^\beta)^\alpha=\{(0,2),(2,0),(1,2),(2,1),(0,0),(1,1),(2,2)\}</math>. Łatwo zauważyć, że otrzymana relacja nie jest przechodnia,
gdyż <math>(0,2),(2,1)\in ((R^\gamma)^\beta)^\alpha</math> podczas gdy <math>(0,1)\notin ((R^\gamma)^\beta)^\alpha</math>.
==Iloczyn kartezjański i podobne konstrukcje (''rozdział dla
dociekliwych)''==
W definicji [[##iloczyn_kartezjanski|Uzupelnic iloczyn_kartezjanski|]] zaprezentowanej w rozdziale
[[##section_iloczyn_kartezjanski|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|[Uzupelnij]||
Dla dowolnych dwóch zbiorów <math>x</math> i <math>y</math> istnieje zbiór <math>x\times y</math> zawierający
wszystkie pary postaci <math>(w,z)</math> gdzie <math>w\in x</math> i <math>z\in y</math>.
}}
{{dowod|[Uzupelnij]||
Ustalmy dwa dowolne zbiory <math>x</math> i <math>y</math>. Jeśli <math>x=\emptyset</math> lub <math>y=\emptyset</math> to
<math>x\times y = \emptyset</math> istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym
przypadku <math>x\cup y</math> jest zbiorem jednoelementowym <math>\{z\}</math> to <math>x\times
y=\{\{\{z\}\}\}</math> istnieje na podstawie aksjomatu pary. W dalszej częsci dowodu
zakładamy że zbiory <math>x</math> i <math>y</math> są niepuste i że <math>x\cup y</math> ma więcej niż jeden element.
Na podstawie aksjomatu zbioru potęgowego, aksjomatu unii i aksjomatu wycinania
następujące zbiory istnieją:
A &<nowiki>=</nowiki>z{P}(x)|  w z <nowiki>=</nowiki>w, <br>
B &<nowiki>=</nowiki>z{P}(x y)|  w  v (w  v  z<nowiki>=</nowiki>v,w),<br>
C &<nowiki>=</nowiki>z{P}({P}(y))|  v z<nowiki>=</nowiki>v<nowiki>=</nowiki>(v,v).
Nasze założenia gwarantują, że żaden z powyższych zbiorów nie jest pusty. Kontynuując
możemy stworzyć
D_0 &<nowiki>=</nowiki>z{P}(A B)|  w  v w v
z<nowiki>=</nowiki>w,w,v<nowiki>=</nowiki>(w,v),
w którym to zbiorze mamy pewność, że <math>w</math> jest elementem <math>x</math>. Kontynuujemy definiując
D_0' &<nowiki>=</nowiki>z{P}(D_0 C)|  w  v w v
z<nowiki>=</nowiki>(w,v),(v,v),
gdzie mamy pewność, że <math>w</math> jest elementem <math>x</math>, a <math>v</math> elementem <math>y</math>, oraz
D_0" &<nowiki>=</nowiki>z{P}(D_0 C)|  w  v w v
z<nowiki>=</nowiki>(w,v),(w,w ),
gdzie mamy pewność, że <math>w\in A\cap B</math>. Kończąc
x y &<nowiki>=</nowiki>z D_0' |  w  v w v
z<nowiki>=</nowiki>(w,v) z D_0" |  w z<nowiki>=</nowiki>(w,w).
}}
{{twierdzenie|[Uzupelnij]||
Jeśli <math>x,y</math> i <math>z</math> są zbiorami i <math>z\subseteq x\times y</math> to zbiorem jest również ogół
<math>v</math> takich, że istnieje <math>w</math> spełniające <math>(v,w)\in z</math>. Zbiór takich <math>v</math> oznaczamy
przez <math>\pi_1(z)</math> i nazywamy projekcją na pierwszą współrzędną.
}}
{{dowod|[Uzupelnij]||
Zbiór <math>\pi_1(z)</math> istnieje na podstawie aksjomatów ZF i jest równy:
<center><math>\pi_1(z) = \bigcup\{w\in\bigcup z\,|\, \exists u\; w=\{u\}\}.
</math></center>
}}
W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykład. AKS Dla
dowolnej formuły <math>\varphi'</math> nie posiadającej zmiennych wolnych innych niż <math>z'</math> i
<math>x_1'</math> następująca formuła jest prawdą
<center><math>\forall x_1' \forall x' \exists y' \forall z'\; z'\in y' \iff (z'\in x' \land
\varphi').
</math></center>
Aby dowieść tą własność ustalmy dowolną formułę <math>\varphi'</math> i dowolny zbiór <math>x_1'</math>.
Stosujemy aksjomat wyróżniania do <math>x=x\times \{x_1'\}</math>&nbsp;(który istnieje na mocy
Twierdzenia&nbsp;[[##tw:produktistnieje|Uzupelnic tw:produktistnieje|]]) i do formuły
<center><math>\exists z' \exists x_1'\; z=(z',x_1')\land\varphi'
</math></center>
otrzymując zbiór <math>y</math>. Wymagany zbiór <math>y'</math> istnieje na mocy
Twierdzenia&nbsp;[[##tw:pierwszaproj|Uzupelnic tw:pierwszaproj|]] i jest równy <math>\pi_1(y)</math>.
Przykładem zastosowania powyższego twierdzenia może być otrzymanie drugiej projekcji
z iloczynu kartezjańskiego. Aby otrzymać <math>\pi_2(z)</math> stosujemy powyższe twierdzenie do
<math>x_1'=z</math>, <math>x=\bigcup\bigcup{z}</math> i wyrażenia <math>\varphi'</math> mówiącego <math>\exists w\;
(w,z')\in x_1'</math>.

Wersja z 18:12, 18 sie 2006

Źródło: „https://wazniak.mimuw.edu.pl/index.php?title=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&oldid=20518”