Iloczyn kartezjański

Iloczyn kartezjański, produkt zbiorów^[1], produkt kartezjański^[2] – działanie na dowolnej liczbie dowolnych zbiorów, definiowane na różne sposoby. W najprostszym przypadku iloczyn kartezjański to działanie dwuargumentowe opisujące zbiór odpowiednich par uporządkowanych – tych utworzonych z elementów wyjściowych dwóch zbiorów. Symbolicznie – jeśli ${\displaystyle A}$ i ${\displaystyle B}$ są dowolnymi zbiorami, to^[3][4]:

${\displaystyle A\times B:=\{(a,b):a\in A\wedge b\in B\},}$

Każde pole szachownicy jest oznaczone uporządkowaną parą litery i cyfry. Dlatego mówi się, że zbiór oznaczeń pól ${\displaystyle \{a1,...,h8\}}$ to iloczyn kartezjański (${\displaystyle \times }$) dwóch zbiorów – zbioru odpowiednich liter ${\displaystyle \{a,...,h\}}$ i zbioru odpowiednich cyfr ${\displaystyle \{1,...,8\}}$

×

gdzie ${\displaystyle \wedge }$ oznacza spójnik „i” (koniunkcję).

Nazwa kartezjański odnosi się do Kartezjusza^[5] – matematyka, którego upamiętnia też nazwa kartezjańskiego układu współrzędnych. Taki układ to opis każdego punktu płaszczyzny uporządkowaną parą liczb rzeczywistych, nazywanych współrzędnymi. Przez to płaszczyznę można utożsamić z iloczynem kartezjańskim ${\displaystyle \mathbb {R} \times \mathbb {R} ,}$ gdzie ${\displaystyle \mathbb {R} }$ to zbiór wszystkich liczb rzeczywistych^[2].

Definicje i przykłady

Z trójelementowych zbiorów A i B można utworzyć ich iloczyn kartezjański A×B, który ma dziewięć (9) elementów

Wypełniony walec (kołowy prosty) można definiować jako iloczyn kartezjański koła i odcinka^[1]. Tutaj przedstawiono powierzchnię boczną takiego walca w kartezjańskim układzie współrzędnych

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=\{(x,1),(y,1),(x,2),(y,2),(x,3),(y,3)\}.}$

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

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

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}}({\mathcal {P}}(X\cup Y)).}$

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

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^[7][8], 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 (a,(b,c))}$^[9].

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^[10][11]; 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 \{a,\{b,\{c,d\}\}\},}$ wówczas iloczyn ${\displaystyle A\times B\times C\times D}$ określa się jako ${\displaystyle A\times (B\times (C\times D)).}$

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^[12]

${\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}.}$

Własności

Algebraiczne

Przykład rozdzielności iloczynu kartezjańskiego (${\displaystyle \times }$) względem sumy zbiorów (${\displaystyle \cup }$)

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

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

Iloczyn kartezjański nie jest też łączny – w ogólności:

${\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^[14].

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

${\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 }$)^[15]:

${\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\backslash C)&=(A\times B)\backslash (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}$^[2].

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\}=\\&=\{(a,b)\mid (a\in \{a_{1},\dots ,a_{n}\}\lor a\in \{a_{n+1}\})\land b\in B\}=\\&=\{(a,b)\mid (a\in \{a_{1},\dots ,a_{n}\}\land b\in B)\lor (a\in \{a_{n+1}\}\land b\in B)\}=\\&=\{(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\}=\\&=\left(\{a_{1},\dots ,a_{n}\}\times B\right)\cup \left(\{a_{n+1}\}\times B\right).\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.

Zobacz też

• m-produkt
• produkt (teoria kategorii)
• suma prosta
• topologia produktowa
• zbiór potęgowy