Kartezijanski umnožak

U matematici, **Dekartov (Kartezijanski) umnožak** je direktni umnožak skupova. Ime je dobio po francuskom matematičaru Dekartu, 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):

:A\times B = \{(x,y) | x\in A\;\wedge\;y\in B\}.

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.

## Primeri
### Umnožak nepraznih skupova

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

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

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

U pitanju su različiti skupovi, tj. A \times B \neq B \times A.

### Špil karata

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.

### Dvodimenzionalni koordinatni sistem

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.

## Implementacija u teoriji skupova
Formalna definicija Dekartovog umnoška sa aspekta teorije skupova sledi iz definicije uređenog para. Najčešća definicija uređenog para je (x, y) = \{\{x\},\{x, y\}\}, koju je dao Kuratovski. Iz definicije sledi da je X\times Y \subseteq \mathcal{P}(\mathcal{P}(X \cup Y)), gde je \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.

### Nekomutativnost i neasocijativnost
Neka su A, B, C i D skupovi.

Dekartov umnožak **nije** komutativan,

A \times B \ne B \times A,

jer su koordinate uređenih parova permutovane, osim ako je ispunjen jedan od sledećih uslova:
* 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).

(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 u odnosu na presek, uniju, podskup

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

(A \cap B) \times (C \cap D) = (A \times C) \cap (B \times D)

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

(A \cup B) \times (C \cup D) \neq (A \times C) \cup (B \times D)

U stvari, važi sledeća jednakost:
(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:

(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

A \times (B \cap C) = (A \times B) \cap (A \times C),

A \times (B \cup C) = (A \times B) \cup (A \times C),

A \times (B \setminus C) = (A \times B) \setminus (A \times C),

(A \times B)^c = (A^c \times B^c) \cup (A^c \times B) \cup (A \times B^c).

Za podskupove važi sledeće:

Ako je  A \subseteq B onda je A \times C \subseteq B \times C,

Ako su A,B  \neq \emptyset onda je A \times B \subseteq C \times D \iff A \subseteq C \land B \subseteq D.

### Kardinalnost

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.

## <math>n</math>-arni umnožak
### Dekartovo stepenovanje
**Dekartov kvadrat** (ili binarni Dekartov umnožak) skupa X je Dekartov umnožak X2 = X × X. Primer ovog umnoška je dvodimenzionalna ravan  gde je **R** skup realnih brojeva: **R**2 je skup svih tačaka  gde su *x* i *y* realni brojevi (vidi Dekartov koordinatni sistem).

**Dekartov stepen** skupa *X* može se definisati kao:

:  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 , gde je **R** skup realnih brojeva. Opštiji primer je **R***n*.

*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*.

### Konačni <var>n</var>-arni umnožak
Dekartov umnožak može se uopštiti na ***n''-arni Dekartov umnožak''' sa ''n'' skupova ''X''<sub>1</sub>, ..., ''X<sub>n</sub>'':

: <math>X_1\times\cdots\times X_n = \{(x_1, \ldots, x_n) : x_i \in X_i \}.</math>

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 .

=== Beskonačni umnošci ===

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

: <math>\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\},</math>

što predstavlja skup svih funkcija definisanih na skupu indeksa tako da vrednost funkcije za određeni indeks ''i'' bude elemenet skupa ''X<sub>i</sub>''. Čak i kada je svaki od ''X<sub>i</sub>'' 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
: <math>  \pi_{j} : \prod_{i \in I} X_i \to X_{j},</math>
definisana sa <math>\pi_{j}(f) = f(j)</math> naziva se ***j*-ta projekcija*'.

Važan slučaj je kada je skup indeksa skup prirodnih brojeva \mathbb{N}: ovaj Dekartov umnožak je skup svih beskonačnih sekvenci gde je *i*-ta koordinata iz odgovarajućeg skupa *X<sub>i</sub>*. Na primer, svaki element umnoška
: \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 \mathbb{R}^\omega, ili \mathbb{R}^{\mathbb{N}}.

## Reference

## Vanjske veze
* Članak o Dekartovom umnošku