Cartesian product

From Wikipedia, the free encyclopedia

Categories: Basic concepts in set theory | Binary operations

In mathematics, the Cartesian product is a direct product of sets. The Cartesian product is named after René Descartes, 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):

Failed to parse (Missing texvc executable; please see math/README to configure.): X\times Y = \{(x,y) | x\in X\;\mathrm{and}\;y\in Y\}.

For example, the Cartesian product of the thirteen-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 playing cards {(Ace, ♠), (King, ♠), ..., (2, ♠), (Ace, ♥), ..., (3, ♣), (2, ♣)}. The Cartesian product has 52 elements because that is the product of 13 times 4.

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.

1 n-ary product
2 Cartesian square and Cartesian power
3 Infinite products
4 Abbreviated form
5 Cartesian product of functions
6 Category theory
7 See also
8 External links
9 References

n-ary product

The Cartesian product can be generalized to the n-ary Cartesian product over n sets X₁, ..., X_n:

Failed to parse (Missing texvc executable; please see math/README to configure.): X_1\times\cdots\times X_n = \{(x_1, \ldots, x_n) \mid x_1\in X_1\;\mathrm{and}\;\cdots\;\mathrm{and}\;x_n\in X_n\}.

Indeed, it can be identified to (X₁ × ... × X_n-1) × X_n. It is a set of n-tuples.

Cartesian square and Cartesian power

The Cartesian square (or binary Cartesian product) of a set X is the Cartesian product X² = X × X. An example is the 2-dimensional plane R² = R × R where R is the set of real numbers - all points (x,y) where x and y are real numbers (see the Cartesian coordinate system).

The cartesian power of a set X can be defined as:

Failed to parse (Missing texvc executable; please see math/README to configure.): X^n = X \times X \times X \ldots = \left\{ (x_1, x_2, \ldots, x_n) \ | \ x_1 \in X \land x_2 \in X \land \ldots x_n \in X \right\}.

An example of this is R³ = R × R × R, with R again the set of real numbers, and more generally Rⁿ.

Infinite products

The above definition is usually all that's needed for the most common mathematical applications. However, it is possible to define the Cartesian product over an arbitrary (possibly infinite) collection of sets. If I is any index set, and

Failed to parse (Missing texvc executable; please see math/README to configure.): \{X_i\ | i \in I\}

is a collection of sets indexed by I, then we define

Failed to parse (Missing texvc executable; please see math/README to configure.): \prod_{i \in I} X_i = \{ f : I \to \bigcup_{i \in I} X_i\ |\ (\forall i)(f(i) \in X_i)\},

that is, the set of all functions defined on the index set such that the value of the function at a particular index i is an element of X_i .

For each j in I, the function

Failed to parse (Missing texvc executable; please see math/README to configure.): \pi_{j} : \prod_{i \in I} X_i \to X_{j},

defined by

Failed to parse (Missing texvc executable; please see math/README to configure.): \pi_{j}(f) = f(j),\,

is called the j ^th projection map.

An n-tuple can be viewed as a function on {1, 2, ..., n} that takes its value at i to be the i ^th element of the tuple. Hence, when I is {1, 2, ..., n} this definition coincides with the definition for the finite case. In the infinite case this is a family.

One particular and familiar infinite case is when the index set is Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb N,

the natural numbers: this is just the set of all infinite sequences with the i ^th term in its corresponding set X_i. Once again, Failed to parse (Missing texvc executable; please see math/README to configure.): \mathbb R
provides an example of this:

Failed to parse (Missing texvc executable; please see math/README to configure.): \prod_{n = 1}^\infty \mathbb R =\mathbb{R}^\omega= \mathbb R \times \mathbb R \times \cdots

is the collection of infinite sequences of real numbers, and it is easily visualized as a vector or tuple with an infinite number of components. Another special case (the above example also satisfies this) is when all the factors X_i involved in the product are the same, being like "Cartesian exponentiation." Then the big union in the definition is just the set itself, and the other condition is trivially satisfied, so this is just the set of all functions from I to X.

Otherwise, the infinite cartesian product is less intuitive; though valuable in its applications to higher mathematics.

The assertion that the Cartesian product of an arbitrary collection of non-empty sets is non-empty is equivalent to the axiom of choice.

Abbreviated form

If several sets are being multiplied together, e.g. Failed to parse (Missing texvc executable; please see math/README to configure.): X_1, X_2, X_3, ... , then some authors ^[1] choose to abbreviate the Cartesian product as simply Failed to parse (Missing texvc executable; please see math/README to configure.): \times X_i .

Cartesian product of functions

If f is a function from A to B and g is a function from X to Y, their cartesian product f×g is a function from A×X to B×Y with

Failed to parse (Missing texvc executable; please see math/README to configure.): (f\times g)(a, x) = (f(a), g(x))

As above this can be extended to tuples and infinite collections of functions.

Category theory

Although the Cartesian product is traditionally applied to sets, category theory provides a more general interpretation of the product of mathematical structures.