Cartesian product

In mathematics, specifically set theory, the Cartesian product of two sets A and B, denoted A × B, is the set of all ordered pairs (a, b) where a is an element of A and b is an element of B. In terms of set-builder notation, that is $${\displaystyle A\times B=\{(a,b)\mid a\in A\ {\mbox{ and }}\ b\in B\}.}$$

A table can be created by taking the Cartesian product of a set of rows and a set of columns. If the Cartesian product rows × columns is taken, the cells of the table contain ordered pairs of the form (row value, column value).

One can similarly define the Cartesian product of n sets, also known as an n-fold Cartesian product, which can be represented by an n-dimensional array, where each element is an n-tuple. An ordered pair is a 2-tuple or couple. More generally still, one can define the Cartesian product of an indexed family of sets.

The Cartesian product is named after René Descartes, whose formulation of analytic geometry gave rise to the concept, which is further generalized in terms of direct product.

A rigorous definition of the Cartesian product requires a domain to be specified in the set-builder notation. In this case the domain would have to contain the Cartesian product itself. For defining the Cartesian product of the sets ${\displaystyle A}$ and ${\displaystyle B}$, with the typical Kuratowski's definition of a pair ${\displaystyle (a,b)}$ as ${\displaystyle \{\{a\},\{a,b\}\}}$, an appropriate domain is the set ${\displaystyle {\mathcal {P}}({\mathcal {P}}(A\cup B))}$ where ${\displaystyle {\mathcal {P}}}$ denotes the power set. Then the Cartesian product of the sets ${\displaystyle A}$ and ${\displaystyle B}$ would be defined as $${\displaystyle A\times B=\{x\in {\mathcal {P}}({\mathcal {P}}(A\cup B))\mid \exists a\in A\ \exists b\in B:x=(a,b)\}.}$$

An illustrative example is the standard 52-card deck. The standard playing card ranks {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} form a 13-element set. The card suits {♠, ♥, ♦, ♣} form a four-element set. The Cartesian product of these sets returns a 52-element set consisting of 52 ordered pairs, which correspond to all 52 possible playing cards.

Ranks × Suits returns a set of the form {(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}.

Suits × Ranks returns a set of the form {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.