Cartesisch product

In de verzamelingenleer is het cartesische product of de productverzameling van twee verzamelingen de verzameling van alle koppels of ook geordende paren waarvan het eerste element uit de eerste verzameling en het tweede uit de tweede verzameling komt.

Definitie

Het cartesische product van de twee verzamelingen $A$ en $B$ wordt genoteerd als $A\times B$ en is gedefinieerd als een verzameling koppels, als volgt:

A\times B=\{(a,b)\mid a\in A,b\in B\}

Het cartesische product is genoemd naar de Franse filosoof en wiskundige René Descartes. Hij ontdekte dat een punt in een vlak kon worden gezien als een getallenpaar. In moderne notatie maakte hij het vlak equivalent met $\mathbb {R} \times \mathbb {R}$ .

Voorbeeld

Voor $A=\{a_{1},a_{2}\}$ en $B=\{b_{1},b_{2},b_{3}\}$ , is:

A\times B=\{(a_{1},b_{1}),(a_{1},b_{2}),(a_{1},b_{3}),(a_{2},b_{1}),(a_{2},b_{2}),(a_{2},b_{3})\}

Herhaald cartesisch product

Het product $A\times B$ is weer een verzameling, en daarmee kan dus het product met een derde verzameling $C$ worden gevormd:

(A\times B)\times C=\{((a,b),c)\mid (a,b)\in A\times B,c\in C\}

Anderzijds bestaat ook het product van $A$ met de productverzameling $B\times C$ :

A\times (B\times C)=\{(a,(b,c))\mid a\in A,(b,c)\in B\times C\}

Deze twee verzamelingen zijn volgens de definitie verschillend, maar er is wel een bijectie tussen de twee:

f:(A\times B)\times C\to A\times (B\times C):((a,b),c)\mapsto (a,(b,c))

Het verschil tussen deze twee is in de meeste wiskundige theorieën waarin met het cartesische product van verzamelingen wordt gerekend van weinig belang. Men laat dan een stel haakjes vallen en noteert

A\times B\times C=\{(a,b,c)\mid a\in A,b\in B,c\in C\}

De elementen van $A\times B\times C$ heten geordende drietallen. Zo ontstaan de tupels. Een tupel met $n$ elementen heet een $n$ -tupel. Door inductie bestaat het cartesische product van $n$ verzamelingen uit alle geordende $n$ -tupels waarvan de $i$ -de component tot de $i$ -de verzameling behoort:

\prod _{i=1}^{n}A_{i}=A_{1}\times \ldots \times A_{n}=\{(a_{1},\ldots ,a_{n})\mid a_{1}\in A_{1},\ldots ,a_{n}\in A_{n}\}

Het cartesische product van één verzameling is bij afspraak die verzameling zelf, dus een 1-tupel wordt geïdentificeerd met de enige component waaruit het bestaat. Het cartesische product van nul verzamelingen is het singleton met alleen het 0-tupel $()$ als element. Dit product is dus niet de lege verzameling.

Is een cartesisch product gevormd met steeds dezelfde verzameling, dan wordt het geschreven met een exponentiële notatie:

A\times A\times A=A^{3},\mathbb {R} \times \mathbb {R} =\mathbb {R} ^{2}

enzovoort

Product van willekeurig veel verzamelingen

Een $n$ -tupel kan worden opgevat als een afbeelding van de getallenverzameling $\{1,2,\ldots ,n\}$ naar de vereniging van de betrokken verzamelingen:

f:\{1,2,\ldots ,n\}\to \bigcup _{i=1}^{n}A_{i}

,

met als eigenschap dat:

f(i)\in A_{i}

De functie $f$ wordt dan geïdentificeerd met het $n$ -tupel

(f(1),f(2),\ldots ,f(n))

Het herhaalde cartesische product van de $n$ verzamelingen $A_{1},\ldots ,A_{n}$ is dan de verzameling van die functies.

Zij $(A_{i})$ een familie verzamelingen geïndexeerd door een verzameling $I$ , die niet noodzakelijk een getallenverzameling hoeft te zijn. Ze kan leeg zijn, of eindig en niet leeg, of oneindig en zelfs overaftelbaar.

Het cartesische product van deze familie is de verzameling van alle afbeeldingen van de indexverzameling naar de vereniging van de familie die elke index binnen het overeenkomstige element van de familie afbeelden:

\prod _{i\in I}A_{i}=\{f:I\to \bigcup _{i\in I}A_{i}\mid \forall i\in I,f(i)\in A_{i}\}

Een bijzonder geval krijgt men, als $A_{i}=A$ voor alle $i\in I$ . Dan is de productverzameling de verzameling van alle afbeeldingen van $I$ naar $A$ . Deze krijgt de intuïtief duidelijke notatie $A^{I}$ .

Projectie

Met het cartesische product $A\times B$ van twee verzamelingen associëren we twee projecties

\pi _{A}:A\times B\to A:(a,b)\mapsto a

\pi _{B}:A\times B\to B:(a,b)\mapsto b

Met een algemeen herhaald of oneindig cartesisch product wordt een stel afbeeldingen geassocieerd die elk tupel op een vaste component van dat tupel afbeelden. De $i$ -de projectie is

\pi _{i}:(\prod _{j\in I}A_{j})\to A_{i}:f\mapsto f(i)

In de cartesiaanse meetkunde op $\mathbb {R} ^{2}$ komen deze projecties overeen met de twee meetkundige projecties $\pi _{X}^{Y}$ en $\pi _{Y}^{X}$ evenwijdig met de coördinaat-assen.

Eigenschappen

Het cartesische product van een willekeurige verzameling met de lege verzameling is de lege verzameling
Als $A$ en $B$ eindige verzamelingen zijn, is het aantal elementen van $A\times B$ gelijk aan het product van het aantal elementen van $A$ en het aantal elementen van $B$ : $|A\times B|=|A|\cdot |B|$ .
Als $A$ of $B$ oneindig is, en de andere verzameling is niet leeg, dan is $A\times B$ oneindig.
Er geldt in het algemeen niet dat $A\times B=B\times A$ . Dat is alleen het geval wanneer $A=B$ . Tussen beide producten bestaat wel een bijectie, namelijk de omkering van elk paar.

Voorbeelden

Bij relationele databases wordt met het commando JOIN van twee tabellen het cartesische product gemaakt.
RGB-kleursysteem