Kartezijanski umnožak

U matematici, Dekartov (Kartezijanski) umnožak je direktni umnožak skupova. Ime je dobio po francuskom matematičaru Dekartu,^[1] zahvaljujući čijem zasnivanju analitičke geometrije je postavljen temelj za ovaj koncept.

Posebno, Dekartov umnožak dva skupa X (npr. skup tačaka na x-osi) i Y (npr. skup tačaka na y-osi), u oznaci X × Y, je skup svih mogućih uređenih parova kod kojih je prva komponenta element skupa X a druga komponenta element skupa Y (u primeru bi to bila cela ravan x0y):

${\displaystyle A\times B=\{(x,y)|x\in A\;\wedge \;y\in B\}.}$^[2]

Dekartov umnožak dva konačna skupa može se predstaviti tabelom, tako da su elementi jednog skupa raspoređeni u redove, a drugog u kolone. Tada se uređeni parovi mogu shvatiti kao ćelije u tabeli, gde je svaka određena svojim redom i kolonom.

Neka su dati skupovi ${\displaystyle A=\{1,2,3\}}$ i ${\displaystyle B=\{1,2\}}$.

${\displaystyle A\times B=\{(1,1),(1,2),(2,1),(2,2),(3,1),(3,2)\}}$

${\displaystyle B\times A=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)\}}$

U pitanju su različiti skupovi, tj. ${\displaystyle A\times B\neq B\times A}$.

Na špilu od 52 karte se može ilustrovati dekartov umnožak. Špil ima 13 vrsta karata {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} i svaka vrsta se pojavljuje u četiri boje {♠, ♥, ♦, ♣}. Dekartov umnožak ovih skupova se sastoji od 52 uređena para svih mogućih karata.

Vrsta × boja daje sledeći skup {(A, ♠), (A, ♥), (A, ♦,), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}.

Boja × vrsta daje sledeći skup {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.

U pitanju su različiti disjunktni skupovi.

Glavni istorijski primer je kartezijanska ravan u analitičkoj geometriji. U cilju predstavljanja geometrijskih oblika na numerički način i dobijanja numeričkih informacija od ovakvih reprezentacija oblika, Rene Dekart je svakoj tački u ravni dodelio par realnih brojeva, nazvanih koordinatama. Obično se takav par prvih i drugih komponenata naziva x i y koordinata, respektivno. Skup svih takvih parova, odnosno kartezijanski umnožak ℝ × ℝ gde su ℝ realni brojevi, predstavlja skup svih tačaka u ravni.

Formalna definicija Dekartovog umnoška sa aspekta teorije skupova sledi iz definicije uređenog para. Najčešća definicija uređenog para je ${\displaystyle (x,y)=\{\{x\},\{x,y\}\}}$, koju je dao Kuratovski. Iz definicije sledi da je ${\displaystyle X\times Y\subseteq {\mathcal {P}}({\mathcal {P}}(X\cup Y))}$, gde je ${\displaystyle {\mathcal {P}}}$ partitivni skup. Dakle, postojanje Dekartovog umnoška bilo koja dva skupa u Cermelo-Frenkel teoriji skupova je posledica aksiome para, aksiome unije, aksiome partitivnog skupa, i sheme separacije. Pošto se funkcije najčešće definišu kao specijalan slučaj relacija, a relacije se definišu kao podskup Dekartovog umnoška, sledi da je Dekartov umnožak suštinski neophodan za većinu drugih definicija.

Neka su A, B, C i D skupovi.

Dekartov umnožak nije komutativan,

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

jer su koordinate uređenih parova permutovane, osim ako je ispunjen jedan od sledećih uslova^[3]:

• A je jednako B,
• bar jedan od skupova A i B je prazan.

Primeri:

• Skupovi A i B su različiti. Na primer: A = {1,2}; B = {3,4}

A × B = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}

B × A = {3,4} × {1,2} = {(3,1), (3,2), (4,1), (4,2)}

• Skupovi A i B su jednaki. Na primer: A = B = {1,2}

A × B = B × A = {1,2} × {1,2} = {(1,1), (1,2), (2,1), (2,2)}

• Jedan od skupova A ili B je prazan. Na primer: A = {1,2}; B = ∅

A × B = {1,2} × ∅ = ∅

B × A = ∅ × {1,2} = ∅

U opštem slučaju, Dekartov umnožak nije asocijativan (osim ako je jedan od skupova prazan).

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

Na primer, ako je A = {1}, onda je (A × A) × A = {((1,1),1)} ≠ { (1,(1,1)) } = A × (A × A).

Dekartov umnožak se lepo ponaša u odnosu na presek skupova.

${\displaystyle (A\cap B)\times (C\cap D)=(A\times C)\cap (B\times D)}$^[4]

Međutim, skupovna jednakost ne važi ukoliko presek zamenimo sa unijom.

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

U stvari, važi sledeća jednakost: ${\displaystyle (A\times C)\cup (B\times D)=[(A\setminus B)\times C]\cup [(A\cap B)\times (C\cup D)]\cup [(B\setminus A)\times D]}$

Za razliku skupova važi identitet:

${\displaystyle (A\times C)\setminus (B\times D)=[A\times (C\setminus D)]\cup [(A\setminus B)\times C]}$

Sledeće skupovne jednakosti ilustruju distributivnost Dekartovog umnoška i skupovnih operacija^[3]

${\displaystyle A\times (B\cap C)=(A\times B)\cap (A\times C)}$,

${\displaystyle A\times (B\cup C)=(A\times B)\cup (A\times C)}$,

${\displaystyle A\times (B\setminus C)=(A\times B)\setminus (A\times C)}$,

${\displaystyle (A\times B)^{c}=(A^{c}\times B^{c})\cup (A^{c}\times B)\cup (A\times B^{c})}$^[4].

Za podskupove važi sledeće:

Ako je ${\displaystyle A\subseteq B}$ onda je ${\displaystyle A\times C\subseteq B\times C}$,

Ako su A,B ${\displaystyle \neq \emptyset }$ onda je ${\displaystyle A\times B\subseteq C\times D\iff A\subseteq C\land B\subseteq D}$^[5].

Kardinalnost (kardinal ili kardinalni broj) je broj elemenata skupa. Na primer, neka su data dva skupa: A = {a, b} i B = {5, 6}. Skupovi A i B imaju po dva elementa. Njihov Dekartov umnožak, u oznaci A × B, daje novi skup koji se sastoji od sledećih elemenata:

A × B = {(a,5), (a,6), (b,5), (b,6)}.

Svaki element skupa A se uparuje sa svakim elementom skupa B. Svaki uređeni par je element u rezultujućem skupu A × B. Broj različitih elemenata u Dekartovom umnošku skupova jednak je umnošku broja elemenata skupova čiji se Dekartov umnožak računa; u ovom slučaju je 2·2=4. Kardinalni broj dobijenog skupa, jednak je omnošku kardinalnih brojeva skupova čiji se Dekartov umnožak računa. Dakle,

||A × B| = |A| · |B|.

Slično,

||A × B × C| = |A| · |B| · |C|

i tako dalje.

Skup A × B je beskonačan ako je bar jedan od skupova A ili B beskonačan a drugi skup je neprazan.^[6]

Dekartov kvadrat (ili binarni Dekartov umnožak) skupa X je Dekartov umnožak X² = X × X. Primer ovog umnoška je dvodimenzionalna ravan R² = R × R gde je R skup realnih brojeva: R² je skup svih tačaka (x,y) gde su x i y realni brojevi (vidi Dekartov koordinatni sistem).

Dekartov stepen skupa X može se definisati kao:

${\displaystyle X^{n}=\underbrace {X\times X\times \cdots \times X} _{n}=\{(x_{1},\ldots ,x_{n})\ |\ x_{i}\in X{\text{ za sve }}i=1,\ldots ,n\}.}$

Odgovarajući primer je R³ = R × R × R, gde je R skup realnih brojeva. Opštiji primer je Rⁿ.

n-arni Dekartov stepen skupa X je izomorfan prostoru funkcija koje preslikavaju skup od n elemenata u skup X. Kao specijalan slučaj, 0-arni Dekartov stepen od X može se uzeti jednoelementni skup i odgovarajuće prazno preslikavanje sa kodomenom X.

Dekartov umnožak može se uopštiti na n-arni Dekartov umnožak sa n skupova X₁, ..., X_n:

${\displaystyle X_{1}\times \cdots \times X_{n}=\{(x_{1},\ldots ,x_{n}):x_{i}\in X_{i}\}.}$

Ovako definisan umnožak je skup n-torki. Ako se n-torke definišu kao ugnježdeni uređeni parovi, onda se skup n-torki može poistovetiti sa (X₁ × ... × X_n−1) × X_n.

Moguće je definisati Dekartov umnožak za proizvoljnu (beskonačnu) indeksiranu familiju skupova. Ako je I proizvoljan skup indeksa, i ${\displaystyle \{X_{i}\}_{i\in I}}$ familija skupova indeksiranih sa I, tada se Dekartov umnožak skupova u X definiše kao

${\displaystyle \prod _{i\in I}X_{i}=\left\{\left.f:I\to \bigcup _{i\in I}X_{i}\ \right|\ (\forall i)(f(i)\in X_{i})\right\},}$

što predstavlja skup svih funkcija definisanih na skupu indeksa tako da vrednost funkcije za određeni indeks i bude elemenet skupa X_i. Čak i kada je svaki od X_i neprazan, Dekartov umnožak može biti prazan ako ne pretpostavimo da važi aksioma izbora (koja je ekvivalentna tvrđenju da je svaki takav umnožak neprazan).

Za svako j iz I, funkcija

${\displaystyle \pi _{j}:\prod _{i\in I}X_{i}\to X_{j},}$

definisana sa ${\displaystyle \pi _{j}(f)=f(j)}$ naziva se j-ta projekcija.

Važan slučaj je kada je skup indeksa skup prirodnih brojeva ${\displaystyle \mathbb {N} }$: ovaj Dekartov umnožak je skup svih beskonačnih sekvenci gde je i-ta koordinata iz odgovarajućeg skupa X_i. Na primer, svaki element umnoška

${\displaystyle \prod _{n=1}^{\infty }\mathbb {R} =\mathbb {R} \times \mathbb {R} \times \cdots }$

može se predstaviti kao vektor sa prebrojivo mnogo realnih koordinata. Ovaj skup se najčešće označava sa ${\displaystyle \mathbb {R} ^{\omega }}$, ili ${\displaystyle \mathbb {R} ^{\mathbb {N} }}$.

• Članak o Dekartovom umnošku (en)