Cartesian product

From Wikipedia, the free encyclopedia

(Redirected from Cartesian square)
Jump to: navigation, search

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):

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.

Contents

The Cartesian product can be generalized to the n-ary Cartesian product over n sets X1, ..., Xn:

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 (X1 × ... × Xn-1) × Xn. It is a set of n-tuples.

The Cartesian square (or binary Cartesian product) of a set X is the Cartesian product X2 = X × X. An example is the 2-dimensional plane R2 = 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:

Xn = X × X × .. × X = \{(x_1, \ldots, x_n)| x_1\in X\;\mathrm{and}\;\ldots\;\mathrm{and}\;x_n\in X\}.

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

See also:

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

\{X_i\ | i \in I\}

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

\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 Xi .

For each j in I, the function

\pi_{j} : \prod_{i \in I} X_i \to X_{j},

defined by

\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 \mathbb N, the natural numbers: this is just the set of all infinite sequences with the i th term in its corresponding set Xi . Once again, \mathbb R provides an example of this:

\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 Xi 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.

If several sets are being multiplied together, e.g. X1,X2,X3,..., then some authors [1] choose to abbreviate the Cartesian product as simply \times X_i.

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

(f\times g)(a, x) = (f(a), g(x))

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

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

  1. ^ M. Osborne and A. Rubinstein, A Course in Game Theory, MIT Press 1994.
Retrieved from "http://en.wikipedia.org/wiki/Cartesian_product"
Advanced Search
Included Web Search Engines


Safe Search

close

Top Matching Results

Occasionally Search.com will highlight specialized results that are based on the context of your query. Examples of specialized results include specific links to news, images, or video.

Top Matching Results may highlight information from other Search.com pages, content from the CNET Network of sites, or third party content. The listings are based purely on relevance. Search.com does not receive payment for listings in this section but our partners that provide this data may get paid for listing these products.

Sponsored Links

This section contains paid listings which have been purchased by companies that want to have their sites appear for specific search terms and related content. These listings are administered, sorted and maintained by a third party and are not endorsed by Search.com.

Search Results

Search.com sends your search query to several search engines at one time and integrates the results into one list which has been sorted by relevance using Search.com's proprietary algorithm. You can customize the list of search engines included in your metasearch from the preferences.

The search engines that are used in your metasearch may allow companies to pay to have their Web sites included within the results. To view the Paid Inclusion policy for a specific search engine, please visit their Web site. Search.com does not accept payment or share revenue with any search engine partner for listings in this section.