Декартов производ

У математици, Декартов (Картезијански) производ је директни производ скупова. Име је добио по француском математичару Декарту,^[1] захваљујући чијем заснивању аналитичке геометрије је постављен темељ за овај концепт.

Декартов производ скупова и

Посебно, Декартов производ два скупа (нпр. скуп тачака на -оси) и (нпр. скуп тачака на -оси), у ознаци , је скуп свих могућих уређених парова код којих је прва компонента елемент скупа а друга компонента елемент скупа (у примеру би то била цела раван ):

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

Декартов производ два коначна скупа може се представити табелом, тако да су елементи једног скупа распоређени у редове, а другог у колоне. Тада се уређени парови могу схватити као ћелије у табели, где је свака одређена својим редом и колоном.

Примери

Производ непразних скупова

Нека су дати скупови ${\displaystyle A=\{1,2,3\}}$ и ${\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)\}}$

У питању су различити скупови, тј. ${\displaystyle A\times B\neq B\times A}$.

Шпил карата

Шпил од 52 карте

На шпилу од 52 карте се може илустровати Декартов производ. Шпил има 13 врста карата {} и свака врста се појављује у четири боје {♠, ♥, ♦, ♣}. Декартов производ ових скупова се састоји од 52 уређена пара свих могућих карата.

Врста × боја даје следећи скуп {}.

Боја × врста даје следећи скуп {}.

У питању су различити дисјунктни скупови.

Дводимензионални координатни систем

Картезијанске координате тачака

Главни историјски пример је картезијанскa раван у аналитичкој геометрији. У циљу представљања геометријских облика на нумерички начин и добијања нумеричких информација од оваквих репрезентација облика, Рене Декарт је свакој тачки у равни доделио пар реалних бројева, названих координатама. Обично се такав пар првих и других компонената назива и координата. Скуп свих таквих парова, односно картезијански производ ℝ × ℝ где су ℝ реални бројеви, представља скуп свих тачака у равни.

Имплементација у теорији скупова

Формална дефиниција Декартовог производа са аспекта теорије скупова следи из дефиниције уређеног пара. Најчешћа дефиниција уређеног пара је ${\displaystyle (x,y)=\{\{x\},\{x,y\}\}}$, коју је дао Куратовски. Из дефиниције следи да је ${\displaystyle X\times Y\subseteq {\mathcal {P}}({\mathcal {P}}(X\cup Y))}$, где је ${\displaystyle {\mathcal {P}}}$ партитивни скуп. Дакле, постојање Декартовог производа било која два скупа у Цермело-Френкел теорији скупова је последица аксиоме пара, аксиоме уније, аксиоме партитивног скупа, и схеме сепарације. Пошто се функције најчешће дефинишу као специјалан случај релација, а релације се дефинишу као подскуп Декартовог производа, следи да је Декартов производ суштински неопходан за већину других дефиниција.

Некомутативност и неасоцијативност

Нека су , , и скупови.

Декартов производ није комутативан,

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

јер су координате уређених парова пермутоване, осим ако је испуњен један од следећих услова^[3]:

• је једнако ,
• бар један од скупова и је празан.

Примери:

• Скупови и су различити. На пример:

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

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

• Скупови и су једнаки. На пример: = {1,2}

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

• Један од скупова или је празан. На пример:

= {1,2} × ∅ = ∅

= ∅ × {1,2} = ∅

У општем случају, Декартов производ није асоцијативан (осим ако је један од скупова празан).

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

На пример, ако је = {1}, онда је .

Декартов производ у односу на пресек, унију, подскуп

Скуповна једнакост илустрована на примеру скупова , и .

графички приказ

Скуповне једнакости и илустроване скуповима и .

Декартов производ се лепо понаша у односу на пресек скупова.

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

Међутим, скуповна једнакост не важи уколико пресек заменимо са унијом.

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

У ствари, важи следећа једнакост: ${\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]}$

За разлику скупова важи идентитет:

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

Следеће скуповне једнакости илуструју дистрибутивност Декартовог производа и скуповних операција^[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].

За подскупове важи следеће:

Ако је ${\displaystyle A\subseteq B}$ онда је ${\displaystyle A\times C\subseteq B\times C}$,

Ако су A,B ${\displaystyle \neq \emptyset }$ онда је ${\displaystyle A\times B\subseteq C\times D\iff A\subseteq C\land B\subseteq D}$^[5].

Кардиналност

Кардиналност (кардинал или кардинални број) је број елемената скупа. На пример, нека су дата два скупа: и. Скупови и имају по два елемента. Њихов Декартов производ, у ознаци , даје нови скуп који се састоји од следећих елемената:

.

Сваки елемент скупа се упарује са сваким елементом скупа . Сваки уређени пар је елемент у резултујућем скупу . Број различитих елемената у Декартовом производу скупова једнак је производу броја елемената скупова чији се Декартов производ рачуна; у овом случају је 2·2=4. Кардинални број добијеног скупа, једнак је производу кардиналних бројева скупова чији се Декартов производ рачуна. Дакле,

.

Слично,

и тако даље.

Скуп је бесконачан ако је бар један од скупова или бесконачан а други скуп је непразан.^[6]

n {\displaystyle n} -арни производ

Декартово степеновање

Декартов квадрат (или бинарни Декартов производ) скупа је Декартов производ . Пример овог производа је дводимензионална раван R² = R × R где је скуп реалних бројева: ² је скуп свих тачака где су и реални бројеви (види Декартов координатни систем).

Декартов степен скупа може се дефинисати као:

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

Одговарајући пример је R³ = R × R × R, где је R скуп реалних бројева. Општији пример је Rⁿ.

-арни Декартов степен скупа је изоморфан простору функција које пресликавају скуп од елемената у скуп . Као специјалан случај, 0-арни Декартов степен од може се узети једноелементни скуп и одговарајуће празно пресликавање са кодоменом X.

Коначни n-арни производ

Декартов производ може се уопштити на -арни Декартов производ са скупова ₁, ..., :

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

Овако дефинисан производ је скуп -торки. Ако се -торке дефинишу као угњеждени уређени парови, онда се скуп -торки може поистоветити са (₁ × ... × ₋₁) × .

Бесконачни производи

Могуће је дефинисати Декартов производ за произвољну (бесконачну) индексирану фамилију скупова. Ако је произвољан скуп индекса, и ${\displaystyle \{X_{i}\}_{i\in I}}$ фамилија скупова индексираних са , тада се Декартов производ скупова у дефинише као

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

што представља скуп свих функција дефинисаних на скупу индекса тако да вредност функције за одређени индекс буде елемент скупа . Чак и када је сваки од непразан, Декартов производ може бити празан ако не претпоставимо да важи аксиома избора (која је еквивалентна тврђењу да је сваки такав производ непразан).

За свако из , функција

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

дефинисана са ${\displaystyle \pi _{j}(f)=f(j)}$ назива се -та пројекција.

Важан случај је када је скуп индекса скуп природних бројева ${\displaystyle \mathbb {N} }$: овај Декартов производ је скуп свих бесконачних секвенци где је -та координата из одговарајућег скупа . На пример, сваки елемент производа

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

може се представити као вектор са пребројиво много реалних координата. Овај скуп се најчешће означава са ${\displaystyle \mathbb {R} ^{\omega }}$, или ${\displaystyle \mathbb {R} ^{\mathbb {N} }}$.