Dekartov proizvod

U matematici, Dekartov (Kartezijanski) proizvod je direktni proizvod 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 proizvod 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\}.

^[2]

Dekartov proizvod 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

Proizvod 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 proizvod. Š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 proizvod 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. Skup svih takvih parova, odnosno kartezijanski proizvod ℝ × ℝ gde su ℝ realni brojevi, predstavlja skup svih tačaka u ravni.

Implementacija u teoriji skupova

Formalna definicija Dekartovog proizvoda 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 proizvoda 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 proizvoda, sledi da je Dekartov proizvod suštinski neophodan za većinu drugih definicija.

Nekomutativnost i neasocijativnost

Neka su A, B, C i D skupovi.

Dekartov proizvod 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^[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 proizvod 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 proizvod u odnosu na presek, uniju, podskup

Dekartov proizvod se lepo ponaša u odnosu na presek skupova.

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

$(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 proizvoda i skupovnih operacija^[3]

$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})$ ^[4].

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$ ^[5].

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 proizvod, 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 proizvodu skupova jednak je proizvodu broja elemenata skupova čiji se Dekartov proizvod računa; u ovom slučaju je 2·2=4. Kardinalni broj dobijenog skupa, jednak je proizvodu kardinalnih brojeva skupova čiji se Dekartov proizvod 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]

$n$ -arni proizvod

Dekartovo stepenovanje

Dekartov kvadrat (ili binarni Dekartov proizvod) skupa X je Dekartov proizvod X² = X × X. Primer ovog proizvoda 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{ за све }}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 proizvod

Dekartov proizvod može se uopštiti na n-arni Dekartov proizvod 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 proizvod 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 proizvodi

Moguće je definisati Dekartov proizvod 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 proizvod 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 proizvod može biti prazan ako ne pretpostavimo da važi aksioma izbora (koja je ekvivalentna tvrđenju da je svaki takav proizvod 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 proizvod je skup svih beskonačnih sekvenci gde je i-ta koordinata iz odgovarajućeg skupa X_i. Na primer, svaki element proizvoda

\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

^ Merriam-Webster Online Dictionary Pristupljeno 23.11.2015.
^ Warner, S: Modern Algebra, page 6. Dover Press, 1990.
^ ^a ^b Singh, S. Cartesian product. Pristupljeno 24. 11. 2015.
^ ^a ^b Dekartov proizvod na PlanetMath.org.
^ Dekartov proizvod podskupova na https://proofwiki.org/ Pristupljeno 29.11.2015.
^ Peter S. (1998). A Crash Course in the Mathematics Of Infinite Sets. St. John's Review, 44(2), 35–59. Retrieved August 1, 2011, from http://www.mathpath.org/concepts/infinity.htm

Spoljašnje veze

Članak o Dekartovom proizvodu (jezik: engleski)

[1] Merriam-Webster Online Dictionary Pristupljeno 23.11.2015.

[2] Warner, S: Modern Algebra, page 6. Dover Press, 1990.

[Singh-3] Singh, S. Cartesian product. Pristupljeno 24. 11. 2015.

[planetmath-4] Dekartov proizvod na PlanetMath.org.

[5] Dekartov proizvod podskupova na https://proofwiki.org/ Pristupljeno 29.11.2015.

[6] Peter S. (1998). A Crash Course in the Mathematics Of Infinite Sets. St. John's Review, 44(2), 35–59. Retrieved August 1, 2011, from http://www.mathpath.org/concepts/infinity.htm

[1]

[2]

[3]

[4]

[5]

[6]