Iloczyn kartezjański

Działanie dla pary zbiorów

Iloczyn kartezjański zbiorów ${\displaystyle A}$ i ${\displaystyle B}$ to zbiór:

${\displaystyle A\times B:=\left\{(a,b)\mid a\in A\land b\in B\right\}.}$

Przykład: niech dane będą zbiory ${\displaystyle A=\{x,y\}}$ oraz ${\displaystyle B=\{1,2,3\}.}$ Ich iloczyn kartezjański to:

${\displaystyle A\times B={\big \{}(x,1),(y,1),(x,2),(y,2),(x,3),(y,3){\big \}}}$ .

Uwaga: istnieje kilka nierównoważnych definicji par uporządkowanych. Najczęściej przyjmowana jest definicja Kuratowskiego:

${\displaystyle (x,y):={\big \{}\{x\},\{x,y\}{\big \}}}$ .

Jeśli ${\displaystyle x\in X}$ i ${\displaystyle y\in Y,}$ to zbiory ${\displaystyle \{x\}}$ i ${\displaystyle \{x,y\}}$ są podzbiorami odpowiedniej sumy zbiorów: ${\displaystyle \{x\},\{x,y\}\subseteq X\cup Y.}$ Można to też opisać przez zbiór potęgowy: ${\displaystyle \{x\},\{x,y\}\in {\mathcal {P}}(X\cup Y).}$ Stąd wynika, że ${\displaystyle (x,y)\in {\mathcal {P}}{\big (}{\mathcal {P}}(X\cup Y){\big )}}$.

Istnienie takiego zbioru wynika z aksjomatu podzbiorów, inaczej aksjomatu wyróżniania – jednego z założeń teorii mnogości ZF.

Uogólnienie na skończoną liczbę zbiorów

W analogiczny sposób można zdefiniować iloczyn kartezjański więcej niż dwóch zbiorów. Mianowicie ${\displaystyle A\times B\times C}$ to zbiór wszystkich trójek uporządkowanych ${\displaystyle (a,b,c)}$ takich, że ${\displaystyle a\in A,}$ ${\displaystyle b\in B,}$ ${\displaystyle c\in C.}$ Definicja ta wymaga uściślenia, co się rozumie przez owe trójki. Można to zrobić na różne sposoby:

• potraktować te trójki jako ciągi trójwyrazowe, czyli funkcje na zbiorze ${\displaystyle \{1,2,3\}}$ w zbiór ${\displaystyle A\cup B\cup C;}$
• inny sposób to definiowanie ${\displaystyle A\times B\times C}$ przez ${\displaystyle A\times (B\times C),}$ a zatem trójka to para par: ${\displaystyle {\big (}a,(b,c){\big )}}$.

Formalnie zbiór trójek jako funkcji i zbiór ${\displaystyle A\times (B\times C)}$ nie są równe, ale w praktyce to rozróżnienie nie ma znaczenia; opisuje to bliżej jedna z dalszych sekcji.

Podobnie ${\displaystyle A\times B\times C\times D}$ można określić jako zbiór czwórek uporządkowanych ${\displaystyle (a,b,c,d)}$ takich, że ${\displaystyle a\in A,}$ ${\displaystyle b\in B,}$ ${\displaystyle c\in C,}$ ${\displaystyle d\in D.}$ Czwórki te można interpretować dwojako:

• jako funkcje z ${\displaystyle \{1,2,3,4\}}$ w zbiór ${\displaystyle A\cup B\cup C\cup D,}$
• jako pary par ${\displaystyle {\Big \{}a,{\big \{}b,\{c,d\}{\big \}}{\Big \}}}$, wówczas iloczyn ${\displaystyle A\times B\times C\times D}$ określa się jako ${\displaystyle A\times {\big (}B\times (C\times D){\big )}}$.

Iloczyny kartezjańskie większej liczby zbiorów definiuje się analogicznie. Przykład: zbiór ${\displaystyle \mathbb {R} ^{n}=\mathbb {R} \times \mathbb {R} \times \ldots \times \mathbb {R} }$ służy do konstruowania n-wymiarowej przestrzeni euklidesowej.

Uogólnienie na nieskończoną liczbę zbiorów

Dla rodziny zbiorów ${\displaystyle \{A_{i}\,\,\colon \,\,i\in I\}}$ można wprowadzić pojęcie uogólnionego iloczynu kartezjańskiego (często nazywanego produktem kartezjańskim (rodziny) zbiorów). Dokładniej, zbiór złożony ze wszystkich tych funkcji

${\displaystyle f\colon I\to \bigcup _{i\in I}A_{i},}$

takich że ${\displaystyle f(i)\in A_{i}}$ dla każdego ${\displaystyle i\in I}$ nazywa się produktem kartezjańskim rodziny zbiorów ${\displaystyle \{A_{i}\,\,\colon \,\,i\in I\}}$ i oznacza takimi symbolami jak

${\displaystyle \prod _{i\in I}A_{i},}$ ${\displaystyle {\underset {i\in I}{\times }}A_{i}}$ lub ${\displaystyle {\underset {i\in I}{\operatorname {P} }}\;A_{i}.}$

Algebraiczne

Iloczyn kartezjański nie jest przemienny – w ogólności kolejność argumentów ma znaczenie:

${\displaystyle A\times B\neq B\times A.}$

Iloczyn kartezjański w ogólności nie jest też łączny — co zapisujemy jako:

${\displaystyle A\times (B\times C)\neq (A\times B)\times C.}$

Mimo to, jak wspomniano wyżej, ta niełączność nie jest istotna. Między tymi zbiorami istnieją odpowiednie bijekcje, które mają szczególny status z punktu widzenia teorii kategorii. Samuel Eilenberg i Saunders Mac Lane pokazali, że te bijekcje są transformacjami naturalnymi odpowiednich funktorów.

Iloczyn kartezjański ma element absorbujący – jest nim zbiór pusty ${\displaystyle (\emptyset )}$:

${\displaystyle A\times \emptyset =\emptyset \times A=\emptyset .}$

Iloczyn kartezjański jest rozdzielny względem sumy zbiorów ${\displaystyle (\cup )}$, ich przekroju ${\displaystyle (\cap )}$ i ich różnicy ${\displaystyle (\backslash )}$:

${\displaystyle {\begin{aligned}A\times (B\cup C)&=(A\times B)\cup (A\times C),\\A\times (B\cap C)&=(A\times B)\cap (A\times C),\\A\times (B\setminus C)&=(A\times B)\setminus (A\times C).\end{aligned}}}$

Kombinatoryczne

Niech ${\displaystyle A}$ i ${\displaystyle B}$ będą skończonymi zbiorami. Jeśli ${\displaystyle \vert A\vert =n}$ oraz ${\displaystyle \vert B\vert =m,}$ to ${\displaystyle \vert A\times B\vert =nm}$.

Dowód tego faktu można przeprowadzić indukcyjnie ze względu na ${\displaystyle n.}$ Jeżeli ${\displaystyle n=1,}$ to ${\displaystyle A=\{a\},}$ przy czym ${\displaystyle a}$ jest jedynym elementem zbioru ${\displaystyle A.}$ Wówczas wprost z definicji ${\displaystyle A\times B=\{(a,b)\mid b\in B\}.}$ Zbiór ten jest równoliczny z ${\displaystyle B,}$ ponieważ przekształcenie ${\displaystyle b\mapsto (a,b)}$ jest bijekcją między tymi zbiorami. Zatem w tym przypadku ${\displaystyle \vert A\times B\vert =m=1\cdot m.}$

Ponadto, jeżeli pewna liczba ${\displaystyle n\geqslant 1}$ ma tę własność, że ${\displaystyle \vert A\times B\vert =nm}$ dla każdego ${\displaystyle A}$ takiego, że ${\displaystyle \vert A\vert =n}$ oraz dla każdego ${\displaystyle \vert B\vert =m,}$ to tę własność ma także liczba ${\displaystyle n+1.}$ Istotnie, można przedstawić ${\displaystyle (n+1)}$-elementowy zbiór ${\displaystyle A}$ w postaci sumy rozłącznych zbiorów ${\displaystyle A=\{a_{1},a_{2},\dots ,a_{n}\}\cup \{a_{n+1}\}.}$ Wtedy z definicji sumy zbiorów zachodzą równości

${\displaystyle {\begin{aligned}A\times B&=\{(a,b)\mid a\in A\land b\in B\}=\\&={\big \{}(a,b)\mid (a\in \{a_{1},\dots ,a_{n}\}\lor a\in \{a_{n+1}\})\land b\in B{\big \}}=\\&={\big \{}(a,b)\mid (a\in \{a_{1},\dots ,a_{n}\}\land b\in B)\lor (a\in \{a_{n+1}\}\land b\in B){\big \}}=\\&={\big \{}(a,b)\mid a\in \{a_{1},\dots ,a_{n}\}\land b\in B\}\cup \{(a,b)\mid a\in \{a_{n+1}\}\land b\in B{\big \}}=\\&={\big (}\{a_{1},\dots ,a_{n}\}\times B{\big )}\cup {\big (}\{a_{n+1}\}\times B{\big )}.\end{aligned}}}$

Pierwszy z tych zbiorów ma z założenia indukcyjnego ${\displaystyle nm}$ elementów. Z kolei drugi ze zbiorów ma (na mocy rozumowania przeprowadzonego dla ${\displaystyle n=1}$) ${\displaystyle m}$ elementów. Ponieważ wobec rozłączności ${\displaystyle \{a_{1},a_{2},\dots ,a_{n}\}}$ oraz ${\displaystyle \{a_{n+1}\}}$ zbiory te są rozłączne i sumują się do ${\displaystyle A\times B,}$ zachodzi równość ${\displaystyle \vert A\times B\vert =nm+m=(n+1)m.}$ To kończy dowód indukcyjny.

Literatura dodatkowa

• Kazimierz Kuratowski: Wstęp do teorii mnogości i topologii. Wyd. 7. Warszawa: Państwowe Wydawnictwo Naukowe, 1977.
• Matematyka. Włodzimierz Waliszewski (red.). Warszawa: Wydawnictwa Szkolne i Pedagogiczne, 1988, s. 298, seria: Encyklopedia szkolna. ISBN 83-02-02551-8.