Iloczyn kartezjański i relacje

Para uporządkowana

Para uporządkowana



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

Definicja 1.1.

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

\( \displaystyle \{ \{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 1.2.

Dla dowolnych zbiorów \( \displaystyle a,b,c,d \) zachodzi:

\( \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 \( \displaystyle (a,b) \) i \( \displaystyle (c,d) \) będą równe. Ponieważ \( \displaystyle \{a\} \in (a,b) \), więc \( \displaystyle \{a\} \in (c,d) \). Mamy zatem \( \displaystyle \{a\} = \{c\} \) lub \( \displaystyle \{a\} = \{c,d\} \). W pierwszym przypadku \( \displaystyle a=c \), ale w drugim również jest tak, mamy bowiem, że \( \displaystyle c \in \{a\} \). Pierwszą część twierdzenia mamy za sobą, bo już wiemy, że pierwsze współrzędne równych par są równe.

\( \displaystyle (a,b) = (a,d). \)

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

Ćwiczenie 1.3

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

\( \displaystyle \bigcap \bigcap x= a. \)

Ćwiczenie 1.4

Udowodnij, że dla dowolnej pary uporządkowanej \( \displaystyle x \) zbiór

\( \displaystyle \bigcap \bigcap (\mathcal{P}(x) \setminus \mathcal{P}(\emptyset)) \)

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

Ćwiczenie 1.5

Pokaż, że z każdej pary \( \displaystyle x \) można otrzymać jej drugą współrzędną, posługując się jedynie parą \( \displaystyle x \), mnogościowymi operacjami \( \displaystyle \bigcup, \bigcap, \cup,\cap,\setminus,\mathcal{P}() \) oraz stałą \( \displaystyle \emptyset \).


Iloczyn kartezjański

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ótkie wprowadzenie. Otóż niech \( \displaystyle x\in X \) oraz \( \displaystyle y \in Y \). Łatwo zauważyć, że zarówno \( \displaystyle \{x,y\} \), jak i \( \displaystyle \{x\} \) są podzbiorami \( \displaystyle X \cup Y \). Zatem \( \displaystyle \{x,y\} \in \mathcal{P} (X \cup Y) \) oraz \( \displaystyle \{x\} \in \mathcal{P} (X \cup Y) \). Więc \( \displaystyle \{\{x\},\{x,y\}\} \subseteq \mathcal{P} (X \cup Y) \), co daje, że \( \displaystyle (x,y) \in \mathcal{P} (\mathcal{P} (X \cup Y)) \).

Istnienie i konstrukcja iloczynu kartezjańskiego zostało dokładnie omówione w dodatkowym rozdziale "Iloczyn kartezjański i aksjomat wyróżniania". Proponuję przestudiowanie dodatkowego rozdziału dopiero po zapoznaniu się z rozdziałami wcześniejszymi, pomimo braku precyzji w następnej definicji.

Definicja 2.1.

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

\( \displaystyle \{z\in \mathcal{P}( \mathcal{P}( x \cup y)): \exists_{a \in x} \exists_{b \in y} \;\; (a,b) =z\}. \)

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

Ćwiczenie 2.2

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

\( \displaystyle \begin{align*} x \times \emptyset & = \emptyset \quad \mbox{(2.1)} \\ x \times (y \cup z) & = (x \times y) \cup (x \times z) \quad \mbox{(2.2)} \\ x \times (y \cap z) & = (x \times y) \cap (x \times z) \quad \mbox{(2.3)} \\ x \times (y \setminus z) & = (x \times y) \setminus (x \times z) \quad \mbox{(2.4)} \end{align*} \)

Ćwiczenie 2.3

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

\( \displaystyle \begin{align*} x \subset y & \hspace {0.1mm} \Rightarrow & (x \times z) \subset (y \times z) \quad \mbox{(2.5)} \\ x \subset y & \hspace {0.1mm} \Rightarrow & (z \times x) \subset (z \times y) \quad \mbox{(2.6)} \end{align*} \)

Ćwiczenie 2.4

Sprawdź, czy dla dowolnych zbiorów \( \displaystyle A,B,C \), prawdziwa jest następująca implikacja:

\( \displaystyle A\times B = A\times C \Rightarrow B=C \)

Relacje

Relacje



Definicja 3.1.

Relacją nazywamy każdy podzbiór iloczynu \( \displaystyle x \times y \).

Operacje na relacjach:

Definicja 3.2.

Niech \( \displaystyle R \subset A \times B \) oraz \( \displaystyle S \subset B \times C \).

\( \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 3.3

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

\( \displaystyle \begin{array}{rllll} T \circ ( S \circ R ) & = & (T \circ S)\circ R \quad \mbox{(3.1)} \\ (S \circ R )^{-1} & = & R^{-1} \circ S^{-1} \quad \mbox{(3.2)} \\ R & \subset & R_L \times R_P \quad \mbox{(3.3)} \\ (S \circ R)_L & \subset & R_L \quad \mbox{(3.4)} \\ (S \circ R)_P & \subset & S_P \quad \mbox{(3.5)} \\ (R^{-1} )_L & = & R_P \quad \mbox{(3.6)} \end{array} \)

Ćwiczenie 3.4

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

\( \displaystyle \begin{array}{rlllll} (R \cup S )^{-1} & = & R^{-1} \cup S^{-1} \quad \mbox{(3.7)} \\ (R \cap S )^{-1} & = & R^{-1} \cap S^{-1} \quad \mbox{(3.8)} \\ (R^{-1})^{-1} & = & R \quad \mbox{(3.9)} \\ (R \cup S ) \circ T & = & (R \circ T) \cup (S \circ T) \quad \mbox{(3.10)} \\ (R \cap S ) \circ T & \subset & (R \circ T) \cap (S \circ T) \quad \mbox{(3.11)}\end{array} \)

Ćwiczenie 3.5

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

\( \displaystyle (R \cap S ) \circ T = (R \circ T) \cap (S \circ T). \)

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

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

Ćwiczenie 3.6

Udowodnij, że zbiór \( \displaystyle A \) jest relacją wtedy i tylko wtedy, gdy

\( \displaystyle A \subset (\bigcup \bigcup A) \times (\bigcup \bigcup A). \)

Relacje równoważności

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 "Konstrukcje liczbowe, liczby całkowite, wymierne, konstrukcja Cantora liczb rzeczywistych: działania i porządek", w którym zaprzęgniemy relacje abstrakcji do definiowania liczb.

Rozpoczynamy rozdział od koniecznej definicji.

Definicja 4.1.

Dla zbioru \( \displaystyle X \) definiujemy relację \( \displaystyle 1_X \subset X \times X \) jako \( \displaystyle \{ z \in X \times X : \exists_{x\in X} \;\; (x,x)=z \} \).

Definicja 4.2.

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

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

Ćwiczenie 4.3

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

  • \( \displaystyle \forall_{ x\in X} (x,x) \in R \),
  • \( \displaystyle \forall_{ x,y \in X} (x,y) \in R arrow (y,x) \in R \),
  • \( \displaystyle \forall_{ x,y,z\in X} (x,y)\in R \wedge (y,z) \in R arrow (x,z)\in R \).

Definicja 4.4.

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

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

Definicja 4.5.

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

Twierdzenie 4.6.

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

  1. \( \displaystyle [x]_R \cap [y]_R \neq \emptyset \),
  2. \( \displaystyle [x]_R = [y]_R \),
  3. \( \displaystyle (x,y) \in R \).

Dowód

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

Niech \( \displaystyle \kappa \neq \emptyset \) będzie pewną rodziną (zbiorem) relacji równoważności o tym samym polu \( \displaystyle X \). Mamy że:

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

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

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

Rozkłady zbiorów

Definicja 4.8.

Niech \( \displaystyle X \neq \emptyset \). Rodzinę \( \displaystyle r \in \mathcal{P} ( \mathcal{P} (X)) \) nazywamy rozkładem zbioru \( \displaystyle X \), gdy:

  1. \( \displaystyle \forall_{C \in r} \;\; C \neq \emptyset \),
  2. \( \displaystyle \bigcup r =X \),
  3. \( \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 4.9.

Dla relacji równoważności \( \displaystyle R \) o polu \( \displaystyle X \) zbiór \( \displaystyle X/R \) jest rozkładem \( \displaystyle X \).

Dowód

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

Definicja 4.10.

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

\( \displaystyle (x,y) \in R_r \) wtw \( \displaystyle \exists_{C\in r} \;\; x \in C \; \hspace {0.1mm} \wedge \; y\in C. \)

Lemat 4.11.

Dla rozkładu \( \displaystyle r \in \mathcal{P} ( \mathcal{P} (X)) \) relacja \( \displaystyle R_r \) jest:

  1. równoważnością,
  2. \( \displaystyle X/{R_r} = r. \)

Dowód

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

Ćwiczenie 4.12

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

\( \displaystyle (A,B)\in R \Leftrightarrow A\frac{.}{} B \subset Y. \)

(\( \displaystyle A\frac{.}{}B \) oznacza różnicę symetryczną zbiorów, czyli \( \displaystyle A\frac{.}{} B = (A\setminus B)\cup (B \setminus A) \)). Udowodnij, że relacja \( \displaystyle R \) jest relacją równoważności.


Ćwiczenie 4.13

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

\( \displaystyle \forall_{x\in X}( [x]_R \subset [x]_S \vee [x]_R \supset [x]_S). \quad \mbox{(4.1)} \)

Podaj przykłady relacji równoważności \( \displaystyle R,S \) takich, że \( \displaystyle R\cup S \) jest relacją równoważności oraz \( \displaystyle R ⊈ S \) i \( \displaystyle S ⊈ R \).


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.

Definicja 4.14.

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

  1. \( \displaystyle X^2 \in \alpha, \)
  2. jeżeli \( \displaystyle \emptyset \neq \alpha ' \subset \alpha \) to \( \displaystyle \bigcap \alpha ' \in \alpha. \)

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

Definicja 4.15.

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

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

Lemat 4.16.

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 \( \displaystyle (3) \) wzajemnie by się zawierały.

Twierdzenie 4.17.

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

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

Dowód

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

Ćwiczenie 4.18

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

Pokazać, stosując twierdzenie 4.17, że nie istnieje domknięcie spójne ani antysymetryczne. (Relacja \( \displaystyle R \) jest spójna, gdy \( \displaystyle \forall x,y (x,y) \in R \hspace {0.1mm} \vee (y,x)\in R \). Relacja \( \displaystyle R \) jest antysymetryczna, gdy z faktu, że \( \displaystyle (x,y) \in R \) oraz \( \displaystyle (y,x) \in R \), da się pokazać, że \( \displaystyle x=y \)).

Ćwiczenie 4.19

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

  1. dla dowolnej relacji \( \displaystyle R \) relacja \( \displaystyle ((R^\alpha)^\beta)^\gamma \) jest relacją równoważności,
  2. dla dowolnej relacji \( \displaystyle R \) zachodzi

\( \displaystyle ((R^\alpha)^\beta)^\gamma =((R^\gamma)^\beta)^\alpha. \)

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

Iloczyn kartezjański i podobne konstrukcje

Iloczyn kartezjański i podobne konstrukcje


W definicji iloczynu kartezjańskiego (patrz Wykład 5: "Para uporządkowana, iloczyn kartezjański, relacje, domykanie relacji, relacja równoważności, rozkłady zbiorów" Definicja 2.1) 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 5.1.

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

Dowód

Ustalmy dwa dowolne zbiory \( \displaystyle x \) i \( \displaystyle y \). Jeśli \( \displaystyle x=\emptyset \) lub \( \displaystyle y=\emptyset \), to \( \displaystyle x\times y = \emptyset \) istnieje na podstawie aksjomatu zbioru pustego. W przeciwnym przypadku \( \displaystyle x\cup y \) jest zbiorem jednoelementowym \( \displaystyle \{z\} \), to \( \displaystyle x\times y=\{\{\{z\}\}\} \) istnieje na podstawie aksjomatu pary. W dalszej części dowodu zakładamy, że zbiory \( \displaystyle x \) i \( \displaystyle y \) są niepuste i że \( \displaystyle 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ą:

\( \displaystyle \begin{align*} A & =\{z\in\mathcal{P}(x)\,|\, \exists w\; z =\{w\}\}, \\ B & =\{z\in\mathcal{P}(x\cup y)\,|\, \exists w \exists v\; (w \neq v \land z=\{v,w\})\}, \\ C & =\{z\in\mathcal{P}(\mathcal{P}(y))\,|\, \exists v\; z=\{\{v\}\}=(v,v)\}. \end{align*} \)

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

\( \displaystyle \begin{align*} D_0 & =\{z\in\mathcal{P}(A\cup B)\,|\, \exists w \exists v\; w\neq v \land z=\{\{w\},\{w,v\}\}=(w,v)\}, \end{align*} \)

w którym to zbiorze mamy pewność, że \( \displaystyle w \) jest elementem \( \displaystyle x \). Kontynuujemy, definiując:

\( \displaystyle \begin{align*} D_0' & =\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(v,v)\}\}, \end{align*} \)

gdzie mamy pewność, że \( \displaystyle w \) jest elementem \( \displaystyle x \), a \( \displaystyle v \) elementem \( \displaystyle y \) oraz:

\( \displaystyle \begin{align*} D_0'' & =\{z\in\mathcal{P}(D_0\cup C)\,|\, \exists w \exists v\; w\neq v \land z=\{(w,v),(w,w )\}\}, \end{align*} \)

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

\( \displaystyle \begin{align*} x\times y & =\{z\in\bigcup D_0' \,|\, \exists w \exists v\; w\neq v \land z=(w,v)\}\cup \{z\in\bigcup D_0'' \,|\, \exists w\; z=(w,w)\}. \end{align*} \)

Twierdzenie 5.2.

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

Dowód

Zbiór \( \displaystyle \pi_1(z) \) istnieje na podstawie aksjomatów ZF i jest równy:

\( \displaystyle \pi_1(z) = \bigcup\{w\in\bigcup z\,|\, \exists u\; w=\{u\}\}. \)

W tej chwili jesteśmy gotowi dowieść własność zapowiedzianą w Wykładzie 4 (patrz Wykład 4: "Teoria mnogości ZFC. Operacje na zbiorach"). Dla dowolnej formuły \( \displaystyle \varphi' \) nieposiadającej zmiennych wolnych innych niż \( \displaystyle z' \) i \( \displaystyle x_1' \), następująca formuła jest prawdą:

\( \displaystyle \forall x_1' \forall x' \exists y' \forall z'\; z'\in y' \iff (z'\in x' \land \varphi'). \)

Aby dowieść tę własność, ustalmy dowolną formułę \( \displaystyle \varphi' \) i dowolny zbiór \( \displaystyle x_1' \). Stosujemy aksjomat wyróżniania do \( \displaystyle x=x\times \{x_1'\} \) (który istnieje na mocy Twierdzenia 5.1 i do formuły

\( \displaystyle \exists z' \exists x_1'\; z=(z',x_1')\land\varphi', \)

otrzymując zbiór \( \displaystyle y \). Wymagany zbiór \( \displaystyle y' \) istnieje na mocy Twierdzenia 5.2 i jest równy \( \displaystyle \pi_1(y) \).

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