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.