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*} \)

Rozwiązanie

Z definicji iloczynu kartezjańskiego oraz twierdzenia 1.2 w sposób oczywisty wynika następujący fakt, który wykorzystamy w dowodach. Dla dowolnych zbiorów \( \displaystyle a,b,x,y \) zachodzi

\( \displaystyle (a,b)\in x \times y \Leftrightarrow (a\in x \wedge b\in y). \)

\( \displaystyle \begin{align*} x \times \emptyset = \\ \{z\in \mathcal{P}(\mathcal{P}(x \cup z)): \exists_{a\in x} \exists_{b\in \emptyset} (a,b)=z\}= \\ \{z\in \mathcal{P}(\mathcal{P}(x \cup z)): \exists_{a\in x} \exists_{b}[ (b \in \emptyset) \wedge (a,b)=z]\} \end{align*} \)

Ponieważ \( \displaystyle b\in \emptyset \) jest zawsze fałszem, to powyższy zbiór jest pusty.

2. 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ę \( \displaystyle (a,b) \), wtedy

\( \displaystyle \begin{align*} (a,b)\in x \times (y \cup z) \Leftrightarrow \\ a \in x \wedge b\in (y\cup z) \Leftrightarrow \\ a\in x \wedge (b\in y \vee b\in z) \Leftrightarrow \\ (a\in x \wedge b\in y) \vee (a\in x \wedge b\in z) \Leftrightarrow \\ (a,b) \in x \times y \vee (a,b)\in x \times z \Leftrightarrow \\ (a,b) \in x \times y \cup x \times z. \end{align*} \)

3. Analogicznie do poprzedniego punktu, weźmy dowolną parę \( \displaystyle (a,b) \), wtedy

\( \displaystyle \begin{align*} (a,b)\in x \times (y \cap z) \Leftrightarrow \\ a \in x \wedge b\in (y\cap z) \Leftrightarrow \\ a\in x \wedge (b\in y \wedge b\in z) \Leftrightarrow \\ (a\in x \wedge b\in y) \wedge (a\in x \wedge b\in z) \Leftrightarrow \\ (a,b) \in x \times y \wedge (a,b)\in x \times z \Leftrightarrow \\ (a,b) \in x \times y \cap x \times z. \end{align*} \)

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

\( \displaystyle \begin{align*} (a,b) \in (x \times y) \setminus (x \times z) \Leftrightarrow \\ a\in x \wedge b\in y \wedge \neg(a\in x \wedge b\in z) \Leftrightarrow \\ b\in y \wedge (a\in x \wedge (a\notin x \vee b\notin z)) \Leftrightarrow \\ b\in y \wedge [(a\in x \wedge a\notin x) \vee (a\in x \wedge b\notin z)] \Leftrightarrow \\ b\in y \wedge (a\in x \wedge b\notin z) \Leftrightarrow \\ a\in x \wedge (b\in y \setminus z) \Leftrightarrow \\ (a,b) \in x \times (y \setminus z). \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*} \)

Rozwiązanie

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

\( \displaystyle \begin{align*} (a,b)\in x\times z \Leftrightarrow \\ a\in x \wedge b \in z \Rightarrow \\ a\in y \wedge b \in z \Leftrightarrow \\ (a,b)\in y\times z. \end{align*} \)

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

Dla dowolnych zbiorów \( \displaystyle x\subset y \) mamy \( \displaystyle x \cup y =y \). Z poprzedniego

ćwiczenia otrzymujemy

\( \displaystyle z \times y =z \times (x\cup y) = (z \times x)\cup(z \times y) \supset (z \times x). \) (Metoda z poprzedniego punktu podziała równie dobrze.)

Ćwiczenie 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 \)

Rozwiązanie

Nie. Na przykład, gdy \( \displaystyle A=\emptyset \), to dla dowolnych zbiorów \( \displaystyle B,C \) mamy

\( \displaystyle \emptyset \times B =\emptyset = \emptyset \times C. \)

Biorąc różne zbiory \( \displaystyle B,C \), otrzymamy kontrprzykład dla badanej implikacji.