Descartes-szorzat

A matematikában, közelebbről a halmazelméletben az A és B halmaz Descartes-szorzatán [ejtsd: dékárt-szorzat] (vagy direkt szorzatán) azt a halmazt értjük, melynek azon rendezett párok az elemei, amiknek első eleme A-beli, második eleme pedig B-beli és a szorzat minden lehetséges párt tartalmaz. A szorzatot az A×B szimbólum jelöli, melyet "A kereszt B"-nek olvasunk, és nem "A-szor B"-nek.

A Descartes-szorzat általánosítható oly módon, hogy nem csak két halmaz Descartes-szorzatát lehessen képezni, hanem akárhány n pozitív egész számú, sőt akár tetszőleges (végtelen) sok halmaz szorzatát is.

Két halmaz Descartes-szorzata és néhány tulajdonsága

Az A halmaz és a B halmaz, ilyen sorrendben vett Descartes-szorzata, melyet

$A\times B$

jelöl, nem más, mint az

$\{(a,b)\mid a\in A\;\wedge \;b\in B\}$

halmaz.

A szorzás × jele alkalmazásának az a magyarázata, hogy ha A és B véges halmaz, elemszámuk rendre n és k, akkor az A × B halmaz elemeinek száma $n\cdot k$.

Ha A, B és C halmazok, akkor teljesülnek a következő disztributivitási formulák:

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

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

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

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

Általában (azaz különböző, nemüres tényezőkre) nem teljesül a kommutativitás és az asszociativitás:

$A\times B\neq B\times A$

$(A\times B)\times C\neq A\times (B\times C)$

Megjegyzés. Ellenben (ugyan nem feltétlenül természetes módon, de) létrehozhatók az A × B ≅ B × A és (A × B) × C ≅ A × (B × C) azonosítások. Például a következő bijekciók ilyenek:

$A\times B\rightarrow B\times A;\;(a,b)\mapsto (b,a)$

$(A\times B)\times C\rightarrow A\times (B\times C);((a,b),c)\mapsto (a,(b,c))$

Az ily módon fennálló asszociativitást célszerűségi okokból általában érvényesnek tekintik és az azonosítás két oldalán lévő hármas szorzatot egységesen A × B × C-vel jelölik. A kommutativitást viszont csak a legritkább esetben tekintik érvényesnek. Például egy 1 × m-es vektort (mátrixot) és transzponáltját, azaz egy m × 1-es mátrixot adott esetben érdemes azonosnak tekintenünk. Ugyanez a helyzet a tenzorszorzattal is: lehetséges, de nem szokás a tenzorszorzást kommutatívnak tekinteni. Ezek a mátrixalgebrai példák azon múlnak, hogy egy vektorteret és duálisát (V^*-ot) véges dimenziós esetben azonosíthatunk egymással, de nem feltétlenül „természetes” módon.

Halmazelméleti részletek

A Descartes-szorzat elemei rendezett párok, melyek a szokásos gyakorlat szerint {{a},{a,b}} alakú halmazok (ez az (a,b) rendezett pár). A pontos definíció szerint

$A\times B:=\{z\mid (\exists x)(\exists y)(z=(x,y)\;\wedge \;x\in A\wedge \;y\in B)\}$

Kérdéses lehet, hogy A × B valóban halmaz-e? Az A × B osztály egy (x,y) eleme olyan, hogy x ∈ A, tehát {x} ∈ ℘(A) (azaz, az {x} az A hatványhalmazában van) és {x,y} ∈ ℘(A ∪ B), tehát (x,y) = {{x},{x,y}} ∈ ℘(℘(A ∪ B)). Tehát a részhalmaz axióma miatt A × B szintén halmaz, de ehhez fel kellett használni a pár-, a hatványhalmaz és az unióaxiómát.

Halmazrendszer Descartes-szorzata

Legyen I tetszőleges halmaz, (A_i)_i∈I indexezett halmazrendszer. Ekkor azon függvények halmazát, melyek az I halmazon értelmezettek és minden i ∈ I elemhez A_i-beli elemet rendelnek, tehát az

$\{f:I\to \bigcup _{i\in I}A_{i}\ |\ (\forall i)(f(i)\in A_{i})\}$

halmazt az (A_i)_i∈I halmazrendszer Descartes-szorzatának nevezzük és a

$\prod _{i\in I}A_{i}$,

$\prod (A_{i})_{i\in I}$ vagy $\times (A_{i})_{i\in I}$

szimbólummal jelöljük.

A Descartes-szorzat egy elemét az (A_i)_i∈I halmazrendszer egy kiválasztófüggvényének mondjuk. Világos, hogy egy kiválasztófüggvény által felvett érték a halmazrendszer egy elemének eleme, így összességében a kiválasztófüggvények a halmazrendszer elemeinek uniójába képeznek (ezt jelöltük U_i∈I A_i-vel). Egy halmazrendszer Descartes-szorzata természetesen üres halmaz, amennyiben akár az indexhalmaza, akár valamelyik eleme üres. Nem nyilvánvaló azonban, hogy ha egy halmazrendszernek sem az indexhalmaza, sem tetszőleges eleme nem üres, akkor a Descartes-szorzat sem üres. Ezt speciális esetekben (véges indexhalmazra, vagy egyelemű tagokat tartalmazó halmazrendszerre) igazolni lehet, ám általános esetben axiómában kell megkövetelni: ez a kiválasztási axióma, mely szerint:

Nemüres halmazok nemüres rendszerének Descartes-szorzata nem üres.

Az sem nyilvánvaló, hogy az előbbi módon definiált szorzat kételemű halmaz esetén egybeesik a szócikk elején lévő módon definiált Descartes-szorzattal. Ha I = { α, β } kételemű indexhalmaz és A_α továbbá A_β két halmaz, akkor a

$b:\prod _{i=\alpha ,\beta }A_{i}\rightarrow A_{\alpha }\times A_{\beta },f\mapsto (f(\alpha ),f(\beta ))$

halmaz bijekció, mely által azonosítható a két Descartes-szorzat. Tény azonban, hogy a Π_i=α,β A_i halmaz ugyanígy az A_β × A_α halmazzal is azonosítható, tekintve, hogy I = { α, β } rendezetlen. Ez azért van, mert a Descartes-szorzat nem abból a szempontból nem kommutatív, mint a rendezett pár (vagyis A_α × A_β ≠ A_β × A_α) hanem, hogy az α jelű elemeket a kiválasztó függvények mindig az α jelű halmazba, a β jelű elemeket mindig a β jelű halmazba képezik. Sőt, a Descartes-szorzat általános definíciója kommutatív is a következő értelemben. Az I indexhalmaz minden σ: I $\rightarrow$ I permutációja (bijekciója) esetén fennáll:

$\prod (A_{i})_{i\in I}\cong \prod (A_{\sigma (i)})_{i\in I}$

alapulvéve az

$f\mapsto f\circ \sigma$

bijekciót.

Kanonikus projekciók

A kanonikus projekciók az A × B Descartes-szorzat elemeihez hozzárendelik az első, illetve második tagjukat. Eszerint

$pr_{1}:A\times B\rightarrow A;(a,b)\mapsto a$, illetve

$pr_{2}:A\times B\rightarrow B;(a,b)\mapsto b$

Hasonlóképpen a Π_i∈IA_i szorzat esetén is léteznek a projekciók. Minden k ∈ I-re a

$pr_{k}:\prod _{i\in I}A_{i}\rightarrow A_{k};f\mapsto f(k)$

k ∈ I elemmel történő kiértékelés a szorzat k-adik kanonikus projekciója.

A kanonikus projekciók szürjektív függvények (azaz pr_i ráképez A_i-re). Ez majdnem nyilvánvaló, hiszen a szorzat elemeit az összes lehetséges módon képeztük, tehát a szorzat tagjai összes elemének szerepelnie kell a kiválasztófüggvények értékeiben.

Kategóriaelméleti definíció

Halmazrendszer Descartes-szorzatát a kategóriaelmélet fogalmaival is lehet definiálni, éspedig a szorzat univerzális tulajdonsága segítségével. Eszerint, ha A=( A_i )_i∈I indexezett halmazrendszer, akkor ennek Descartes-szorzata olyan P halmaz a p=( p_i )_i∈I) függvényrendszerrel együtt, melyre teljesül, hogy egyetlen olyan h:Q $\rightarrow$ P függvény van, amire az alábbi diagram kommutatív:

azaz minden i ∈ I-re

$q_{i}=p_{i}\circ h$ .

Itt Set a halmazok kategóriája, ^ISet az I indexhalmazú halmazrendszerek kategóriája, ahol egy f morfizmus nem más mint olyan ( f_i )_i∈I függvényrendszerek, melyek elemei halmazelméleti függvények, köztük a művelet: ( f_i )_i∈Io( g_i )_i∈I = ( f_iog_i )_i∈I, Δ a diagonalizáló funktor, mely egy H halmazhoz hozzárendeli azt az I-vel indexelt rendszert, melynek minden eleme H, egy f függvényhez pedig hozzárendeli azt az I-vel indexelt függvényrendszert, melynek minden eleme f. A megfogalmazás úgy rövidíthető, hogy a (P,p) pár a (Δ↓A) vegyespár kategória terminális objektuma.

Természetesen, mint minden univerzális tulajdonságon keresztül történő definíciónál a szorzat nem lesz egyértelmű, ellenben az alkalmas objektumok kitüntetett módon izomorfak lesznek egymással. Ha (P,p) és (P',p') az A halmazrendszer két Descartes-szorzata, akkor egyetlen olyan h:P $\rightarrow$ P' bijekció van, amivel p=p'oh teljesül.

Szintén hasonló módon az összes univerzális tulajdonságon keresztül történő definícióhoz az alkalmas objektum létezését igazolni kell. A Set kategóriában az előző bekezdésben definiált ΠA halmaz megfelel Descartes-szorzatnak, a kanonikus projekciókkal ellátva. Megjegyezzük, hogy nem csak Set-ben, hanem minden kategóriában definiálható a Descartes-szorzat fogalma, csak nem mindenhol igazolható a megfelelő objektum létezése. Ha az adott kategóriában léteznek a Descartes-szorzatok, akkor azt Descartes-módon zárt kategóriának nevezzük (Set tehát ilyen).

A Descartes-szorzat kategóriaelméleti értelemben duális párja a direkt összegnek vagy koszorzatnak.