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.

Dekartov umnožak A×B skupova A={x,y,z} i B={1,2,3}

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

Špil od 52 karte

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

Kartezijanske koordinate tačaka

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\neq 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

Skupovna jednakost (A∩B)×(C∩D)=(A×C)∩(B×D) ilustrovana na primeru skupova A={x∈ℝ:2≤x≤5}, B={x∈ℝ:3≤x≤7}, C={y∈ℝ:1≤y≤3}, i D={y∈ℝ:2≤y≤4}.

(A∪B)×(C∪D)≠(A×C)∪(B×D) grafički prikaz

Skupovne jednakosti A×(B∩C)=(A×B)∩(A×C), A×(B∪C)=(A×B)∪(A×C) i A×(B\C)=(A×B)\(A×C) ilustrovane skupovima A={y∈ℝ:1≤y≤4}, B={x∈ℝ:2≤x≤5} i C={x∈ℝ:4≤x≤7}.

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.

$n$-arni umnožak

Dekartovo stepenovanje

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:

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

Konačni n-arni umnožak

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

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

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 $\{X_{i}\}_{i\in I}$ familija skupova indeksiranih sa I, tada se Dekartov umnožak skupova u X definiše kao

$\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

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

definisana sa $\pi _{j}(f)=f(j)$ 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_i. 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} }$.

Spoljašnje veze

• Članak o Dekartovom umnošku (en)