Cartesian product

related topics
{math, number, function}
{game, team, player}

In mathematics, a Cartesian product (or product set) is the direct product of two sets. The Cartesian product is named after René Descartes,[1] whose formulation of analytic geometry gave rise to this concept.

Specifically, the Cartesian product of two sets X (for example the points on an x-axis) and Y (for example the points on a y-axis), denoted X × Y, is the set of all possible ordered pairs whose first component is a member of X and whose second component is a member of Y (e.g., the whole of the x–y plane):

For example, the Cartesian product of the 13-element set of standard playing card ranks {Ace, King, Queen, Jack, 10, 9, 8, 7, 6, 5, 4, 3, 2} and the four-element set of card suits {♠, ♥, ♦, ♣} is the 52-element set of all possible playing cards: ranks × suits = {(Ace, ♠), (King, ♠), ..., (2, ♠), (Ace, ♥), ..., (3, ♣), (2, ♣)}. The corresponding Cartesian product has 52 = 13 × 4 elements. The Cartesian product of the suits × ranks would still be the 52 pairings, but in the opposite order {(♠, Ace), (♠, King), ...}. Ordered pairs (a kind of tuple) have order, but sets are unordered. The order in which the elements of a set are listed is irrelevant; you can shuffle the deck and it's still the same set of cards.

A Cartesian product of two finite sets can be represented by a table, with one set as the rows and the other as the columns, and forming the ordered pairs, the cells of the table, by choosing the element of the set from the row and the column.


Basic properties

Let A,B,C, and D be sets.

In cases where the two input sets are not the same, the Cartesian product is not commutative because the ordered pairs are reversed.

Although the elements of each of the ordered pairs in the sets will be the same, the pairing will differ.

For example:

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

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

One exception is with the empty set, which acts as a "zero", and for equal sets.

and, supposing G,T are sets and G=T:

Strictly speaking, the Cartesian Product is not associative.

The Cartesian Product acts nicely with respect to intersections.

Notice that in most cases the above statement is not true if we replace intersection with union.

Full article ▸

related documents
Kolmogorov space
Laurent series
Axiom of regularity
Conjunctive normal form
Diophantine set
Goodstein's theorem
Generalized Riemann hypothesis
Carmichael number
Monotonic function
Lebesgue measure
Group representation
Algebraic topology
Local ring
Isomorphism theorem
Tree (data structure)
Convex set
Differential topology
Knight's tour
Euler's totient function
Kruskal's algorithm
Mean value theorem
Symmetric group
Spectrum of a ring
Product topology
Mersenne twister
Theory of computation