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

{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 $x$ oraz $y$ będą zbiorami. Przez parę uporządkowaną $(x,y)$ rozumiemy zbiór

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \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 } a,b,c,d$zachodzi:$

(a,b) = (c,d) a=c {0.1mm} b= d

Parser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod|[Uzupelnij]|| 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)Parser nie mógł rozpoznać (błąd składni): {\displaystyle będą równe. Ponieważ } a (a,b)Parser nie mógł rozpoznać (błąd składni): {\displaystyle więc } a (c,d)$.Mamyzatem$a= c lub $\left\{a\right\}=\{c,d\}\mathrm{\$}.Wpierwszymprzypadku$a=cParser nie mógł rozpoznać (błąd składni): {\displaystyle ale w drugim również jest tak, mamy bowiem, że } c 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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle (a,b)=\left\{\left\{a\right\}\\right\}\$. Zatem } a
right= aa,d
right co daje, że Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{a,d\right\}\=\left\{a\right\}\$ a zatem } d=a$.Wprzeciwnymprzypadkugdy$a bParser nie mógł rozpoznać (błąd składni): {\displaystyle mamy, że } a,b aa,d
right. Daje to dwie możliwości albo Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{a,b\right\}\ = \left\{a\right\}\$ co nie może mieć miejsca bo mielibyśmy, że } a=bParser nie mógł rozpoznać (błąd składni): {\displaystyle , albo zaś } a,b= a,d. To drugie prowadzi do naszej tezy $b=d$. }}

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

1. 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$

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 \bigcap \bigcap ( \kPs(x) \setminus \mathcal{P}(\emptyset)) = \{a\} }

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 \bigcup, \bigcap, \cup,\cap,\setminus,\kPs} oraz stałą $\mathrm{\varnothing }$.

Wskazówka:

1. Rozważ najpierw pary różnych elementów.

1. 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\}\mathrm{\$}jaki$x są podzbiorami $X\cup Y$. Zatem $\{x,y\}\in {𝒫}(X\cup Y)$ oraz $\left\{x\right\}\in {𝒫}(X\cup Y)$. Więc Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{\left\{x\right\}\,\left\{x,y\right\}\\right\}\ \subseteq \mathcal{P} (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

Parser nie mógł rozpoznać (błąd składni): {\displaystyle \left\{z\in \mathcal{P}( \mathcal{P}( x \cup y)): \exists_{a \in x} \exists_{b \in y} \;\; (a,b) =z\right\}\ }

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

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

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

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).$

x =
z {P}({P}(x z)): _{a x} _{b } (a,b)=z=
z {P}({P}(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)

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 „\alignedx”): {\displaystyle \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}

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

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 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 } R^{-1} := (y,x) B A : (x,y) R

$R_L:=\{x\in A:{\mathrm{\exists }}_{y\in B}(x,y)\in R\}\mathrm{\$}$R_P := y B : _{x A} (x,y) R

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 „\alignedT”): {\displaystyle \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}

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

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 \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 $\wedge$ w miejsce $\vee$.

(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)

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 }$.

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

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

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 Parser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \left\{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z \right\}\$. \enddefn \begindefn Relację } R X XParser nie mógł rozpoznać (błąd składni): {\displaystyle nazywamy relacją równoważnością o polu } XParser nie mógł rozpoznać (błąd składni): {\displaystyle jeżeli: * zawiera relacje } 1_X Parser nie mógł rozpoznać (błąd składni): {\displaystyle (zwrotność } R$)*$R^{-1} R$(symetria$R$)*$R R RParser nie mógł rozpoznać (błąd składni): {\displaystyle (przechodniość } RParser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle ) \enddefn \beginCwiczenie Pokazać, że definicje zwrotności, symetryczności i przechodniości relacji o polu } XParser nie mógł rozpoznać (błąd składni): {\displaystyle są odpowiednio równoważne następującym własnościom: * } _{ x X} (x,x) R$*$_{ x,y X} (x,y) R (y,x) R$*$_{ x,y,z X} (x,y) R (y,z) R (x,z) RParser nie mógł rozpoznać (błąd składni): {\displaystyle \textbf{Rozwiązanie: }Ćwiczenie jest elementarne. \endCwiczenie \begindefn Niech } RParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie relacją równoważności o polu } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Klasą równoważności elementu } x XParser nie mógł rozpoznać (błąd składni): {\displaystyle jest zbiór }

[x]_R := y X : (x,y) R

Parser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \enddefn \begindefn Zbiór klas równoważności relacji } RParser nie mógł rozpoznać (błąd składni): {\displaystyle będący elementem zbioru } {P}

( {P} (X X))$oznaczamyprzez$X/RParser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle . \enddefn {{twierdzenie|[Uzupelnij]|| Niech } RParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie relacją równoważności o polu } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Następujące warunki są równoważne # } [x]_R [y]_R Parser nie mógł rozpoznać (błąd składni): {\displaystyle # } [x]_R = [y]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle # } (x,y) RParser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod|[Uzupelnij]|| Pokażemy, że } (1) (2)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Niech wspólny element dwóch klas } [x]_R$oraz$[y]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle nazywa się } zParser nie mógł rozpoznać (błąd składni): {\displaystyle . Ze względu na pełną symetrię tezy wystarczy pokazać, że } [x]_R [y]_R$.Niechzatem$p [x]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Mamy więc } (x,p) RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Z założenia jest również } (y,z) R$oraz$(x,z) R$.Zsymetriiotrzymujemy$(z,x) R$.Zatem$(y,z) R$i$(z,x) R$i$(x,p) RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Natychmiast z przechodniości otrzymujemy, że } (y,p) RParser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ Pokażemy, że } (2) (3)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ze zwrotności mamy, że } y [y]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle co z założenia } (2)$daje$y [x]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle a to tłumaczy się na } (x,y) RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Pokażemy, że } (3) (1)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Wystarczy pokazać, że wspólnym elementem klas } [x]_R$oraz$[y]_R$jest$yParser nie mógł rozpoznać (błąd składni): {\displaystyle . Dla pierwszej z nich wynika to z założenia } (3)Parser nie mógł rozpoznać (błąd składni): {\displaystyle a dla drugiej ze zwrotności } RParser nie mógł rozpoznać (błąd składni): {\displaystyle . }} 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 } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Mamy że: # jest relacją równoważności o polu } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . # } [x]_{ } = [x]_R : R

}}

Dowód [Uzupelnij]

$(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 Parser nie mógł rozpoznać (błąd składni): {\displaystyle y\in\bigcap \left\{[x]_R : R\in \kappa\right\}\$. }} W szczególności przecięcie wszystkich relacji równoważności o polu } X$daje$1_XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Jest ona najsilniejszą relacją równoważności. Najsłabszą jest } X^2Parser nie mógł rozpoznać (błąd składni): {\displaystyle . ===Rozkłady zbiorów=== \begindefn Niech } X Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Rodzinę } r {P} ( {P} (X))Parser nie mógł rozpoznać (błąd składni): {\displaystyle nazywamy rozkładem zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle gdy # } _{C r} C Parser nie mógł rozpoznać (błąd składni): {\displaystyle # } r =XParser nie mógł rozpoznać (błąd składni): {\displaystyle # } (C r {0.1mm} D r {0.1mm} C D ){0.1mm} C D =Parser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \enddefn {{lemat|[Uzupelnij]|| Dla relacji równoważności } R$opolu$XParser nie mógł rozpoznać (błąd składni): {\displaystyle zbiór } X/RParser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozkładem } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . }} {{dowod|[Uzupelnij]|| } (1)Parser nie mógł rozpoznać (błąd składni): {\displaystyle Każda klasa jest niepusta bo zawiera element, który ją wyznacza. } (2) X/R XParser nie mógł rozpoznać (błąd składni): {\displaystyle bo każda klasa jest podzbiorem } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Odwrotnie każdy } x [x]_R X/R$.$(3)Parser nie mógł rozpoznać (błąd składni): {\displaystyle Dwie klasy gdy są rożne muszą być rozłączne co udowodniliśmy w twierdzeniu [[##thm:rownowaznosc|Uzupelnic thm:rownowaznosc|]]. }} \begindefn Niech } rParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie rozkładem zbioru } X$.Definiujemyrelacje$R_r

X XParser nie mógł rozpoznać (błąd składni): {\displaystyle następująco: }

(x,y) R_r wtw _{C r} x C {0.1mm} y C

Parser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \enddefn {{lemat|[Uzupelnij]|| Dla rozkładu } r {P} ( {P}

(X))$relacja$R_rParser nie mógł rozpoznać (błąd składni): {\displaystyle jest: # równoważnością # } X/{R_r} = rParser nie mógł rozpoznać (błąd składni): {\displaystyle }} {{dowod|[Uzupelnij]|| } (1)$Relacja$R_rParser nie mógł rozpoznać (błąd składni): {\displaystyle jest zwrotna każdy bowiem } x XParser nie mógł rozpoznać (błąd składni): {\displaystyle musi leżeć w pewnym zbiorze } CParser nie mógł rozpoznać (błąd składni): {\displaystyle rozkładu } r$.Symetria$R_rParser nie mógł rozpoznać (błąd składni): {\displaystyle nie wymaga dowodu. Przechodniość } R_r$.Niech$(x,y)

R_r$i$(y,z) R_rParser nie mógł rozpoznać (błąd składni): {\displaystyle . Istnieją zatem dwa zbiory } C$i$DParser nie mógł rozpoznać (błąd składni): {\displaystyle rozkładu } rParser nie mógł rozpoznać (błąd składni): {\displaystyle takie, że } x,y C$oraz$y,z DParser nie mógł rozpoznać (błąd składni): {\displaystyle . Przecięcie } C$i$DParser nie mógł rozpoznać (błąd składni): {\displaystyle jest więc niepuste zatem } C=DParser nie mógł rozpoznać (błąd składni): {\displaystyle co daje tezę } (x,z) R_rParser nie mógł rozpoznać (błąd składni): {\displaystyle .\\ } (2)$Inkluzjawprawo.Niech$C X/{R_r}$.Klasa$C$jestzatemwyznaczonaprzezpewienelement$xParser nie mógł rozpoznać (błąd składni): {\displaystyle taki, że } C= [x]_{R_r}$.Niech$D rParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie zbiorem rozkładu } rParser nie mógł rozpoznać (błąd składni): {\displaystyle do którego należy } xParser nie mógł rozpoznać (błąd składni): {\displaystyle . Łatwo wykazać, że } C=D$.Inkluzjawlewo.Niech$C r$.$C$jestniepustywiecistnieje$x C$.Klasa$[x]_{R_r} =CParser nie mógł rozpoznać (błąd składni): {\displaystyle . }} \beginCwiczenie Niech } XParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie niepustym zbiorem, oraz niech } Y XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Zdefiniujemy relację } R {P}(X) {P}(X)Parser nie mógł rozpoznać (błąd składni): {\displaystyle następująco: dla dowolnych zbiorów } A,B X$mamy$

(A,B) R A{.}{} B Y.

$(${.}{}Parser nie mógł rozpoznać (błąd składni): {\displaystyle oznacza różnicę symetryczną zbiorów, czyli } A{.}{} B = (A B) (B A)Parser nie mógł rozpoznać (błąd składni): {\displaystyle ) Udowodnij, że relacja } RParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności. \textbf{Wskazówka: } Najtrudniej jest pokazać przechodniość. Udowodnij, że } A {.}{} C (B{.}{} C) (A{.}{} B)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Dobrym punktem wyjścia jest naszkicowanie wszystkich przecięć zbiorów } A,B,CParser nie mógł rozpoznać (błąd składni): {\displaystyle . \textbf{Rozwiązanie: }Pokażemy po kolei zwrotność, przechodniość i symetryczność. # Dla każdego } A X$mamy$A{.}{} A= YParser nie mógł rozpoznać (błąd składni): {\displaystyle , a więc relacja } RParser nie mógł rozpoznać (błąd składni): {\displaystyle jest zwrotna. # Ponieważ dla dowolnych zbiorów } A{.}{} B= B{.}{} A$to$(A,B) R$wtedyitylkowtedygdy$(B,A) R$.Wobectegorelacja$RParser nie mógł rozpoznać (błąd składni): {\displaystyle jest symetryczna. # Weźmy zbiory } A,B,C XParser nie mógł rozpoznać (błąd składni): {\displaystyle , takie że } (A,B), (B,C) RParser nie mógł rozpoznać (nieznana funkcja „\beginalign”): {\displaystyle . 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 } R$mamy$(B{.}{} C) Y$oraz$ (A{.}{} B) YParser nie mógł rozpoznać (błąd składni): {\displaystyle to ich suma też jest podzbiorem } YParser nie mógł rozpoznać (błąd składni): {\displaystyle i konsekwencji również } A{.}{} C YParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oznacza to, że } (A,C) RParser nie mógł rozpoznać (błąd składni): {\displaystyle , a więc relacja } RParser nie mógł rozpoznać (nieznana funkcja „\endCwiczenie”): {\displaystyle jest przechodnia. \endCwiczenie \beginCwiczenie Udowodnij, że dla relacji równoważności } R,S$nazbiorze$X$,relacja$R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności wtedy i tylko wtedy gdy }

_{x X}( [x]_R [x]_S [x]_R [x]_S).

Parser nie mógł rozpoznać (błąd składni): {\displaystyle Podaj przykłady relacji równoważności } R,SParser nie mógł rozpoznać (błąd składni): {\displaystyle takich, że } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności oraz } R S$i$S RParser nie mógł rozpoznać (błąd składni): {\displaystyle . \textbf{Wskazówka: } Przyjrzyj się dokładnie rodzinie zbiorów } A=[x]_R [x]_S : x XParser nie mógł rozpoznać (błąd składni): {\displaystyle . \textbf{Rozwiązanie: }Zaczniemy od pokazania, że formuła } Uzupelnic eq:klasyInkluzje|Parser nie mógł rozpoznać (błąd składni): {\displaystyle implikuje, że relacja } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności. Pokażemy, że rodzina } A=[x]_R [x]_S :

x XParser nie mógł rozpoznać (błąd składni): {\displaystyle tworzy rozkład zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oczywiście, dla każdego elementu } x X$mamy$[x]_R [x]_S $oraz$x [x]_R [x]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle . Wystarczy więc pokazać, że zbiory w rodzinie } AParser nie mógł rozpoznać (błąd składni): {\displaystyle są rozłączne. Weźmy dowolne dwa elementy rodziny } AParser nie mógł rozpoznać (błąd składni): {\displaystyle i przypuśćmy, że ich przecięcie jest niepuste. Niech to będą zbiory odpowiadające elementom } x,y XParser nie mógł rozpoznać (błąd składni): {\displaystyle a więc } [x]_R [x]_S$oraz$[y]_R [y]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle . Skoro te zbiory mają niepuste przecięcie to istnieje } z ([x]_R [x]_S) ([y]_R [y]_S)Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Ponieważ } z [x]_R [x]_S$to$z [x]_R z [x]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle co jest równoważne } x [z]_R x [z]_S$.Podobnerozumowaniedla$z$daje$y [z]_R y [z]_S$.Wobecczegodostajemy$x,y [z]_R [z]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle ponieważ jednak zgodnie z formułą [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jedna z tych klas jest nadzbiorem drugiej, to } x,y [z]_R$lub$x,y [z]_S$.Wprzypadku,gdy$[z]_R [z]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle dostajemy również z [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] } [z]_R=[x]_R [x]_S$oraz$[z]_R=[y]_R [y]_S$wobecczegootrzymujemy$[x]_R [x]_S =[z]_R=[y]_R [y]_S$.Drugiprzypadekjestanalogiczny.Wobecczegorodzina$AParser nie mógł rozpoznać (błąd składni): {\displaystyle jest rozkładem zbioru } XParser nie mógł rozpoznać (błąd składni): {\displaystyle . Wystarczy teraz przekonać się że } (a,b) R S$wtedyitylkowtedy,gdy$a [b]_R [b]_SParser nie mógł rozpoznać (błąd składni): {\displaystyle , aby udowodnić, że jest to rzeczywiście rozkład generowany przez relację } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle . Weźmy dowolne } a,b XParser nie mógł rozpoznać (nieznana funkcja „\beginalign”): {\displaystyle 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 } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle 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 } x XParser nie mógł rozpoznać (błąd składni): {\displaystyle dla którego } [x]_R [x]_S$oraz$[x]_R [x]_S$.Wobectegoistnieje$y [x]_R [x]_S$oraz$z [x]_S [x]_RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Oznacza to, że } (y,x) R S$oraz$(x,z) S R$.Skoro$R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności to } (z,y) R SParser nie mógł rozpoznać (błąd składni): {\displaystyle . Przypuśćmy, że } (z,y) R$.Wtedy$(z,y),(y,x) R$wobecczego$(z,x) RParser nie mógł rozpoznać (błąd składni): {\displaystyle co jest sprzeczne z tym że } (x,z) S RParser nie mógł rozpoznać (błąd składni): {\displaystyle ponieważ relacja } RParser nie mógł rozpoznać (błąd składni): {\displaystyle jest symetryczna. Analogiczną sprzeczność otrzymujemy dla } (z,x) SParser nie mógł rozpoznać (błąd składni): {\displaystyle . 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 } R,SParser nie mógł rozpoznać (błąd składni): {\displaystyle takich, że } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności oraz } R S$i$S RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Polem relacji będzie zbiór } X=0,1,2,3$.Relacje$R,SParser nie mógł rozpoznać (błąd składni): {\displaystyle określimy poprzez wyznaczane przez nie rozkłady odpowiednio } r,sParser nie mógł rozpoznać (nieznana funkcja „\beginalign”): {\displaystyle : \beginalign* r=\{\{0\},\{1\}, \{2,3\}\}\\ s=\{\{0,1\}, \{2\},\{3\}\}. \endalign* Łatwo sprawdzić, że } R S$i$S RParser nie mógł rozpoznać (błąd składni): {\displaystyle , gdyż } (2,3) R S$oraz$(0,1) S RParser nie mógł rozpoznać (błąd składni): {\displaystyle . Z rozkładów } r,sParser nie mógł rozpoznać (błąd składni): {\displaystyle łatwo wynika, że formuła [[##eq:klasyInkluzje|Uzupelnic eq:klasyInkluzje|]] jest prawdziwa dla tych relacji, wobec czego } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle jest relacją równoważności. Wyznaczany przez nią rozkład to } 0,1,2,3Parser nie mógł rozpoznać (nieznana funkcja „\endCwiczenie”): {\displaystyle . \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 } X$,czyliniech$ {P} ( {P} (X^2))Parser nie mógł rozpoznać (błąd składni): {\displaystyle . Rodzina jest zamknięta na przecięcia gdy # } X^2 Parser nie mógł rozpoznać (błąd składni): {\displaystyle # jeżeli } ' $to$ ' Parser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \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 } S X^2Parser nie mógł rozpoznać (błąd składni): {\displaystyle jest domknięciem relacji } R X^2Parser nie mógł rozpoznać (błąd składni): {\displaystyle w klasie (zbiorze) relacji gdy: # } R SParser nie mógł rozpoznać (błąd składni): {\displaystyle # } S Parser nie mógł rozpoznać (błąd składni): {\displaystyle # dla każdej relacji } TParser nie mógł rozpoznać (błąd składni): {\displaystyle jeżeli } R T$oraz$T $to$S TParser nie mógł rozpoznać (nieznana funkcja „\enddefn”): {\displaystyle \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 } (3)Parser nie mógł rozpoznać (błąd składni): {\displaystyle 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]|| } (1) (2)$.Niech$RParser nie mógł rozpoznać (błąd składni): {\displaystyle będzie relacją. Utwórzmy zbiór relacji } '$jako$ S{P} (X^2) : R S {0.1mm} S . 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$.

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

1. 1. $1_X\subset R\cup 1_X$, a więc jest zwrotna

1. 1. 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$.

1. 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}$

1. 1. $(R\cup R^{-1}{)}^{-1}=R^{-1}\cup (R^{-1}{)}^{-1}=R^{-1}\cup R=R\cup R^{-1}$, a więc jest symetryczna

1. 1. 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 {ℛ}$

1. 1. 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$.

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

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 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 [Uzupelnij]

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 [Uzupelnij]

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)

Twierdzenie [Uzupelnij]

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 [Uzupelnij]

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 }$.