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.[1]
Például Descartes-szorzattal képezhetők két elemű személynevek:
- {Kovács, Szabó, Horváth} × {János, Anna} = {Kovács János, Kovács Anna, Szabó János, Szabó Anna, Horváth János, Horváth Anna}.
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
szerkesztésAz A halmaz és a B halmaz, ilyen sorrendben vett Descartes-szorzata, melyet
jelöl, nem más, mint az
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 .
Ha A, B és C halmazok, akkor teljesülnek a következő disztributivitási formulák:
Általában (azaz különböző, nemüres tényezőkre) nem teljesül a kommutativitás és az asszociativitás:
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:
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
szerkesztésA 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
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
szerkesztésLegyen I tetszőleges halmaz, (Ai)i∈I indexezett halmazrendszer. Ekkor azon függvények halmazát, melyek az I halmazon értelmezettek és minden i ∈ I elemhez Ai-beli elemet rendelnek, tehát az
halmazt az (Ai)i∈I halmazrendszer Descartes-szorzatának nevezzük és a
- ,
- vagy
szimbólummal jelöljük.
A Descartes-szorzat egy elemét az (Ai)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 Ui∈I Ai-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
halmaz bijekció, mely által azonosítható a két Descartes-szorzat. Tény azonban, hogy a Πi=α,β Ai 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 I permutációja (bijekciója) esetén fennáll:
alapulvéve az
bijekciót.
Kanonikus projekciók
szerkesztésA kanonikus projekciók az A × B Descartes-szorzat elemeihez hozzárendelik az első, illetve második tagjukat. Eszerint
- , illetve
Hasonlóképpen a Πi∈IAi szorzat esetén is léteznek a projekciók. Minden k ∈ I-re a
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 pri ráképez Ai-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ó
szerkesztésHalmazrendszer 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=( Ai )i∈I indexezett halmazrendszer, akkor ennek Descartes-szorzata olyan P halmaz a p=( pi )i∈I) függvényrendszerrel együtt, melyre teljesül, hogy egyetlen olyan h:Q P függvény van, amire az alábbi diagram kommutatív:
azaz minden i ∈ I-re
- .
Itt Set a halmazok kategóriája, ISet az I indexhalmazú halmazrendszerek kategóriája, ahol egy f morfizmus nem más mint olyan ( fi )i∈I függvényrendszerek, melyek elemei halmazelméleti függvények, köztük a művelet: ( fi )i∈Io( gi )i∈I = ( fiogi )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 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.
Források
szerkesztés- ↑ Dancs István–Magyarkúti Gyula–Medvegyev Péter–Puskás Csaba–Tallos Péter. Bevezetés a matematikai analízisbe (1996)