5. Produkty kartezjańskie

Czytelnik zna już zapewne pojęcie kartezjańskiego układu współrzędnych na płaszczyźnie czy w przestrzeni. Po ustaleniu osi współrzędnych każdemu punktowi płaszczyzny przypisane są dwie współrzędne: odcięta i rzędna. Ta para liczb rzeczywistych jednoznacznie określa położenie punktu w układzie współrzędnych. W parze takiej istotne jest zaznaczenie, która liczba jest pierwszą, a która drugą współrzędną (mogą one też być sobie równe). W ten sposób wprowadza się pojęcie uporządkowanej pary liczb.

Analogicznie wprowadzamy pojęcie uporządkowanej pary dowolnych przedmiotów $a$ i $b$: jest to obiekt zapisywany w postaci $\langle a,b\rangle$, w którym $a$ nazywa się pierwszą współrzędną, zaś $b$ drugą współrzędną^5.1.

W przypadku zbiorów przyjęliśmy, że dwa zbiory są równe wtedy i tylko wtedy, gdy mają te same elementy. Tutaj przyjmujemy, że dwie pary uporządkowane są równe, gdy ich odpowiednie współrzędne są równe. Innymi słowy mamy:

$$(*) \langle a,b\rangle=\langle c,d\rangle\Leftrightarrow a=c\land b=d.$$

W rozdziale trzecim wspomnieliśmy, że wszystkie pojęcia matematyki można zdefiniować używając pojęcia zbioru. W przypadku pary uporządkowanej w teorii mnogości przyjmuje się definicję $\langle a,b\rangle=\{\{a\},\{a,b\}\}$. Nietrudno udowodnić, że tak określone pojęcie pary uporządkowanej spełnia $(*)$.

Definiujemy również trójki $\langle a,b,c\rangle$, czwórki $\langle a,b,c,d\rangle$ i ogólniej $n$-ki uporządkowane jako obiekty, które ``pamiętają'' swoje kolejne współrzędne (tzn. spełniają warunki analogiczne do $(*)$). Można również zdefiniować te pojęcia używając par uporządkowanych. Mianowicie, można przyjąć:

$$\langle a,b,c\rangle=\langle \langle a,b\rangle,c\rangle,$$

$$\langle a,b,c,d\rangle=\langle\langle\langle a,b\rangle,c\rangle,d\rangle,$$

$$\langle a_1,\dots,a_n\rangle=\langle\cdots\langle\langle a_1,a_2\rangle,a_3\rangle,\dots,a_n\rangle,$$

i udowodnić, że tak określone obiekty spełniają nasze wymagania.

Produktem kartezjańskim zbiorów $A$ i $B$ nazywamy zbiór

$$A\times B=\{\langle a,b\rangle: a\in A\land b\in B\}$$

złożony z par uporządkowanych o pierwszej współrzędnej ze zbioru $A$, a drugiej współrzędnej ze zbioru $B$.

Ogólniej, produktem kartezjańskim zbiorów $A_1,\dots,A_n$ nazywamy zbiór

$$A_1\times\dots\times A_n=\{\langle a_1,\dots,a_n\rangle:a_1\in A_1\land\dots\land a_n\in A_n\}$$

złożony z uporządkowanych $n$-ek o pierwszej współrzędnej z $A_1$, drugiej współrzędnej z $A_2$,$\dots$, $n$-tej współrzędnej z $A_n$.

Zbiór $A^2=A\times A$ nazywamy kwadratem kartezjańskim zbioru $A$. Zbiór $A^n=\underbrace{A\times\dots\times A}_n$ nazywamy $n$-tą potęgą kartezjańską zbioru $A$ ($n\geq 1$). Przyjmujemy, że $A^1=A$.

Przykłady. Zbiór ${\mathbb{R}}^2={\mathbb{R}}\times{\mathbb{R}}$ jest zbiorem par współrzędnych punktów na płaszczyźnie z układem współrzędnych. Podobnie zbiór ${\mathbb{R}}^3={\mathbb{R}}\times{\mathbb{R}}\times{\mathbb{R}}$ jest zbiorem trójek współrzędnych punktów przestrzeni z układem współrzędnych. Dlatego pary i trójki liczb rzeczywistych często graficznie przedstawiamy jako odpowiadające im punkty na płaszczyźnie lub w przestrzeni.

Stąd bierze się też geometryczne wyobrażenie produktów $A\times B$ czy $A\times B\times C$.

W pewnym sensie produkt kartezjański związany jest z mnożeniem liczb.

Uwaga 5.1   Jeśli zbiór $A$ ma $n$ elementów, zaś zbiór $B$ $m$ elementów, to zbiór $A\times B$ ma $n\times m$ elementów.

Dowód. Załóżmy, że $A=\{a_1,\dots,a_n\},\ B=\{b_1,\dots,b_m\}$. Wówczas elementy zbioru $A\times B$ (czyli pary uporządkowane) możemy ułożyć w formie prostokątnej tablicy o $n$ rzędach i $m$ kolumnach (macierzy). Dla $1\leq i\leq n$ $i$-ty rząd składa się kolejno z par

$$\langle a_i,b_1\rangle, \langle a_i,b_2\rangle,\dots,\langle a_i, b_m\rangle,$$

(więc ma $m$ elementów). Jest $n$ takich rzędów, więc razem jest $n\times m$ takich par. $\Box$

Podamy teraz własności operacji produktu kartezjańskiego.

1. $A\times (B\cup C)=(A\times B)\cup (A\times C); (B\cup C)\times A=(B\times A)\cup (C\times A).$
2. $A\times (B\cap C)=(A\times B)\cap (A\times C); (B\cap C)\times A=(B\times A)\cap (C\times A).$
3. $A\times (B\setminus C)=(A\times B)\setminus (A\times C); (B\setminus C)\times A=(B\times A)\setminus (C\times A).$
4. $(A\times B)\cap (C\times D)=(A\cap C)\times (B\cap D)$.

Dowód. Dla przykładu udowodnimy, że zbiory $A\times (B\cap C)$ i $(A\times B)\cap (A\times C)$ są równe. W tym celu wystarczy pokazać, że mają one te same elementy. Elementy obu tych zbiorów są parami uporządkowanymi, są więc postaci $\langle x,y\rangle$ dla pewnych $x,y$. Wystarczy więc pokazać, że dla dowolnych $x,y$ mamy

$$(*) \langle x,y\rangle\in A\times(B\cap C)\Leftrightarrow\langle x,y\rangle\in (A\times B)\cap (A\times C).$$

Rozważmy więc dowolne $x,y$. Używając definicji $\times$ i $\cap$ oraz tautologii rachunku zdań dostajemy ciąg zdań równoważnych:

$$\langle x,y\rangle\in A\times(B\cap C)$$

$$\Updownarrow$$

$$x\in A\land y\in B\cap C$$

$$\Updownarrow$$

$$x\in A\land y\in B\land y\in C$$

$$\Updownarrow$$

$$(x\in A\land y\in B)\land(x\in A\land y\in C)$$

$$\Updownarrow$$

$$\langle x,y\rangle\in A\times B\land \langle x,y\rangle\in A\times C$$

$$\Updownarrow$$

$$\langle x,y\rangle\in (A\times B)\cap (A\times C),$$

który świadczy o $(*)$.

Dowody pozostałych punktów pozostawiamy jako ćwiczenie. $\Box$

W przypadku, gdy zbiory $A,B,C,D$ są podzbiorami przestrzeni $X$, warto przedstawić zbiory z punktów 1-4 na diagramie.

Rozważmy teraz zbiór $A\subseteq X\times Y$. Rzutem zbioru $A$ na pierwszą oś nazywamy zbiór pierwszych współrzędnych par $\langle x,y\rangle$ należących do zbioru $A$. Oznaczamy go przez $\pi_X[A]$. Podobnie definiujemy zbiór $\pi_Y[A]$, rzut zbioru $A$ na drugą oś. Mamy więc dla wszystkich $x\in X$ i $y\in Y$:

$$x\in \pi_X[A]\Leftrightarrow\mbox{ istnieje }y\in Y\mbox{ takie, że }\langle x,y\rangle\in A,$$

$$y\in \pi_Y[A]\Leftrightarrow\mbox{ istnieje }x\in X\mbox{ takie, że }\langle x,y\rangle\in A.$$

Dla $a\in X$ i $b\in Y$ zbiory

$$A_a=\{y\in Y:\langle a,y\rangle\in A\}\mbox{ i }A^b=\{x\in X:\langle x,b\rangle\in A\}$$

nazywamy odpowiednio cięciem pionowym zbioru $A$ na współrzędnej $a$ i cięciem poziomym zbioru $A$ na współrzędnej $b$.

Wykres funkcji zdaniowej. Załóżmy, że $\varphi(x),x\in X$ jest funkcją zdaniową. Wykres funkcji zdaniowej $\varphi(x)$ definiujemy jako zbiór

$$\{x\in X:\varphi(x)\},$$

czyli zbiór tych elementów $a\in X$, dla których zdanie $\varphi(a)$ jest prawdziwe. Gdy $\psi(x,y),x\in X,y\in Y$ jest funkcją zdaniową dwóch zmiennych, jej wykres definiujemy jako zbiór

$$\{\langle x,y\rangle\in X\times Y: \psi(x,y)\},$$

czyli zbiór tych par $\langle a,b\rangle\in X\times Y$, dla których zdanie $\psi(a,b)$ jest prawdziwe.

Na przykład wykresem funkcji zdaniowej $x^2>y,x,y\in{\mathbb{R}}$ jest zbiór

$$\{\langle x,y\rangle\in{\mathbb{R}^2}: x^2>y\}.$$

Podobnie definiujemy wykres funkcji zdaniowej większej liczby zmiennych.