In

_{1}, ..., ''X_{n}'' as the set
: $X\_1\backslash times\backslash cdots\backslash times\; X\_n\; =\; \backslash $
of ''n''-tuples. If tuples are defined as nested ordered pairs, it can be identified with . If a tuple is defined as a function on that takes its value at ''i'' to be the ''i''th element of the tuple, then the Cartesian product ''X''_{1}×⋯×''X''_{''n''} is the set of functions
: $\backslash .$

^{2} is the set of all points where ''x'' and ''y'' are real numbers (see the ^{''n''}.
The ''n''-ary Cartesian power of a set ''X'' is

_{i}''. Even if each of the ''X_{i}'' is nonempty, the Cartesian product may be empty if the _{i}'' are the same set ''X''. In this case,
: $\backslash prod\_\; X\_i\; =\; \backslash prod\_\; X$
is the set of all functions from ''I'' to ''X'', and is frequently denoted ''X^{I}''. This case is important in the study of _{i}''. For example, each element of
: $\backslash prod\_^\backslash infty\; \backslash mathbb\; R\; =\; \backslash mathbb\; R\; \backslash times\; \backslash mathbb\; R\; \backslash times\; \backslash cdots$
can be visualized as a

_{1}, ''X''_{2}, ''X''_{3}, …), then some authorsOsborne, M., and Rubinstein, A., 1994. ''A Course in Game Theory''. MIT Press. choose to abbreviate the Cartesian product as simply ×''X''_{''i''}.

Cartesian Product at ProvenMath

*

{{Mathematical logic Axiom of choice Operations on sets

mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, specifically set theory
Set theory is the branch of mathematical logic that studies sets, which can be informally described as collections of objects. Although objects of any kind can be collected into a set, set theory, as a branch of mathematics, is mostly concer ...

, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...

s where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation
In set theory and its applications to logic, mathematics, and computer science, set-builder notation is a mathematical notation for describing a set by enumerating its elements, or stating the properties that its members must satisfy.
Definin ...

, that is
: $A\backslash times\; B\; =\; \backslash .$
A table can be created by taking the Cartesian product of a set of rows and a set of columns. If the Cartesian product is taken, the cells of the table contain ordered pairs of the form .
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
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

. An ordered pair is a 2-tuple or couple. More generally still, one can define the Cartesian product of an indexed family
In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a ''family of real numbers, indexed by the set of integers'' is a collection of real numbers, wh ...

of sets.
The Cartesian product is named after René Descartes
René Descartes ( or ; ; Latinized: Renatus Cartesius; 31 March 1596 – 11 February 1650) was a French philosopher, scientist, and mathematician, widely considered a seminal figure in the emergence of modern philosophy and science. Math ...

, whose formulation of analytic geometry
In classical mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry using a coordinate system. This contrasts with synthetic geometry.
Analytic geometry is used in physics and engine ...

gave rise to the concept, which is further generalized in terms of direct product.
Examples

A deck of cards

An illustrative example is thestandard 52-card deck
The standard 52-card deck of French-suited playing cards is the most common pack of playing cards used today. In English-speaking countries it is the only traditional pack used for playing cards; in many countries of the world, however, it is use ...

. The standard playing card ranks 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
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...

, which correspond to all 52 possible playing cards.
returns a set of the form .
returns a set of the form .
These two sets are distinct, even disjoint, but there is a natural bijection
In mathematics, a bijection, also known as a bijective function, one-to-one correspondence, or invertible function, is a function between the elements of two sets, where each element of one set is paired with exactly one element of the other s ...

between them, under which (3, ♣) corresponds to (♣, 3) and so on.
A two-dimensional coordinate system

The main historical example is the Cartesian plane inanalytic geometry
In classical mathematics, analytic geometry, also known as coordinate geometry or Cartesian geometry, is the study of geometry using a coordinate system. This contrasts with synthetic geometry.
Analytic geometry is used in physics and engine ...

. In order to represent geometrical shapes in a numerical way, and extract numerical information from shapes' numerical representations, René Descartes
René Descartes ( or ; ; Latinized: Renatus Cartesius; 31 March 1596 – 11 February 1650) was a French philosopher, scientist, and mathematician, widely considered a seminal figure in the emergence of modern philosophy and science. Math ...

assigned to each point in the plane a pair of real number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one- dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Ever ...

s, called its coordinates. Usually, such a pair's first and second components are called its ''x'' and ''y'' coordinates, respectively (see picture). The set of all such pairs (i.e., the Cartesian product , with ℝ denoting the real numbers) is thus assigned to the set of all points in the plane.
Most common implementation (set theory)

A formal definition of the Cartesian product from set-theoretical principles follows from a definition ofordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...

. The most common definition of ordered pairs, Kuratowski's definition, is $(x,\; y)\; =\; \backslash $. Under this definition, $(x,\; y)$ is an element of $\backslash mathcal(\backslash mathcal(X\; \backslash cup\; Y))$, and $X\backslash times\; Y$ is a subset of that set, where $\backslash mathcal$ represents the power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

operator. Therefore, the existence of the Cartesian product of any two sets in ZFC follows from the axioms of pairing, union, power set
In mathematics, the power set (or powerset) of a set is the set of all subsets of , including the empty set and itself. In axiomatic set theory (as developed, for example, in the ZFC axioms), the existence of the power set of any set is post ...

, and specification
A specification often refers to a set of documented requirements to be satisfied by a material, design, product, or service. A specification is often a type of technical standard.
There are different types of technical or engineering specificati ...

. Since functions are usually defined as a special case of relations, and relations are usually defined as subsets of the Cartesian product, the definition of the two-set Cartesian product is necessarily prior to most other definitions.
Non-commutativity and non-associativity

Let ''A'', ''B'', ''C'', and ''D'' be sets. The Cartesian product is notcommutative
In mathematics, a binary operation is commutative if changing the order of the operands does not change the result. It is a fundamental property of many binary operations, and many mathematical proofs depend on it. Most familiar as the name of ...

,
: $A\; \backslash times\; B\; \backslash neq\; B\; \backslash times\; A,$
because the ordered pair
In mathematics, an ordered pair (''a'', ''b'') is a pair of objects. The order in which the objects appear in the pair is significant: the ordered pair (''a'', ''b'') is different from the ordered pair (''b'', ''a'') unless ''a'' = ''b''. (In con ...

s are reversed unless at least one of the following conditions is satisfied:
* ''A'' is equal to ''B'', or
* ''A'' or ''B'' is the empty set.
For example:
: ''A'' = ; ''B'' =
:: ''A'' × ''B'' = × =
:: ''B'' × ''A'' = × =
: ''A'' = ''B'' =
:: ''A'' × ''B'' = ''B'' × ''A'' = × =
: ''A'' = ; ''B'' = ∅
:: ''A'' × ''B'' = × ∅ = ∅
:: ''B'' × ''A'' = ∅ × = ∅
Strictly speaking, the Cartesian product is not associative
In mathematics, the associative property is a property of some binary operations, which means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacemen ...

(unless one of the involved sets is empty).
: $(A\backslash times\; B)\backslash times\; C\; \backslash neq\; A\; \backslash times\; (B\; \backslash times\; C)$
If for example ''A'' = , then .
Intersections, unions, and subsets

The Cartesian product satisfies the following property with respect to intersections (see middle picture). :$(A\; \backslash cap\; B)\; \backslash times\; (C\; \backslash cap\; D)\; =\; (A\; \backslash times\; C)\; \backslash cap\; (B\; \backslash times\; D)$ In most cases, the above statement is not true if we replace intersection with union (see rightmost picture). $$(A\; \backslash cup\; B)\; \backslash times\; (C\; \backslash cup\; D)\; \backslash neq\; (A\; \backslash times\; C)\; \backslash cup\; (B\; \backslash times\; D)$$ In fact, we have that: $$(A\; \backslash times\; C)\; \backslash cup\; (B\; \backslash times\; D)\; =;\; href="/html/ALL/l/A\_\backslash setminus\_B)\_\backslash times\_C.html"\; ;"title="A\; \backslash setminus\; B)\; \backslash times\; C">A\; \backslash setminus\; B)\; \backslash times\; C$$absolute complement
In set theory, the complement of a set , often denoted by (or ), is the set of elements not in .
When all sets in the universe, i.e. all sets under consideration, are considered to be members of a given set , the absolute complement of is ...

of ''A''.
Other properties related with subset
In mathematics, set ''A'' is a subset of a set ''B'' if all elements of ''A'' are also elements of ''B''; ''B'' is then a superset of ''A''. It is possible for ''A'' and ''B'' to be equal; if they are unequal, then ''A'' is a proper subset o ...

s are:
$$\backslash text\; A\; \backslash subseteq\; B\; \backslash text\; A\; \backslash times\; C\; \backslash subseteq\; B\; \backslash times\; C;$$
:$\backslash text\; A,B\; \backslash neq\; \backslash emptyset\; \backslash text\; A\; \backslash times\; B\; \backslash subseteq\; C\; \backslash times\; D\; \backslash !\backslash iff\backslash !\; A\; \backslash subseteq\; C\; \backslash text\; B\; \backslash subseteq\; D.$
Cardinality

Thecardinality
In mathematics, the cardinality of a set is a measure of the number of elements of the set. For example, the set A = \ contains 3 elements, and therefore A has a cardinality of 3. Beginning in the late 19th century, this concept was generalized ...

of a set is the number of elements of the set. For example, defining two sets: and Both set ''A'' and set ''B'' consist of two elements each. Their Cartesian product, written as , results in a new set which has the following elements:
: ''A'' × ''B'' = .
where each element of ''A'' is paired with each element of ''B'', and where each pair makes up one element of the output set.
The number of values in each element of the resulting set is equal to the number of sets whose Cartesian product is being taken; 2 in this case.
The cardinality of the output set is equal to the product of the cardinalities of all the input sets. That is,
: , ''A'' × ''B'', = , ''A'', · , ''B'', .
In this case, , ''A'' × ''B'', = 4
Similarly
: , ''A'' × ''B'' × ''C'', = , ''A'', · , ''B'', · , ''C'',
and so on.
The set is infinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
* Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...

if either ''A'' or ''B'' is infinite, and the other set is not the empty set.
Cartesian products of several sets

''n''-ary Cartesian product

The Cartesian product can be generalized to the ''n''-ary Cartesian product over ''n'' sets ''X''''n''-ary Cartesian power

The Cartesian square of a set ''X'' is the Cartesian product . An example is the 2-dimensional plane where R is the set ofreal number
In mathematics, a real number is a number that can be used to measure a ''continuous'' one- dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Ever ...

s: RCartesian coordinate system
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured i ...

).
The ''n''-ary Cartesian power of a set ''X'', denoted $X^n$, can be defined as
: $X^n\; =\; \backslash underbrace\_=\; \backslash .$
An example of this is , with R again the set of real numbers, and more generally Risomorphic
In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word i ...

to the space of functions from an ''n''-element set to ''X''. As a special case, the 0-ary Cartesian power of ''X'' may be taken to be a singleton set
In mathematics, a singleton, also known as a unit set or one-point set, is a set with exactly one element. For example, the set \ is a singleton whose single element is 0.
Properties
Within the framework of Zermelo–Fraenkel set theory, the ...

, corresponding to the empty function with codomain
In mathematics, the codomain or set of destination of a function is the set into which all of the output of the function is constrained to fall. It is the set in the notation . The term range is sometimes ambiguously used to refer to either the ...

''X''.
Infinite Cartesian products

It is possible to define the Cartesian product of an arbitrary (possiblyinfinite
Infinite may refer to:
Mathematics
*Infinite set, a set that is not a finite set
*Infinity, an abstract concept describing something without any limit
Music
* Infinite (group), a South Korean boy band
*''Infinite'' (EP), debut EP of American m ...

) indexed family
In mathematics, a family, or indexed family, is informally a collection of objects, each associated with an index from some index set. For example, a ''family of real numbers, indexed by the set of integers'' is a collection of real numbers, wh ...

of sets. If ''I'' is any index set, and $\backslash \_$ is a family of sets indexed by ''I'', then the Cartesian product of the sets in $\backslash \_$ is defined to be
: $\backslash prod\_\; X\_i\; =\; \backslash left\backslash ,$
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 ''Xaxiom of choice
In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collection ...

, which is equivalent to the statement that every such product is nonempty, is not assumed.
For each ''j'' in ''I'', the function
: $\backslash pi\_:\; \backslash prod\_\; X\_i\; \backslash to\; X\_,$
defined by $\backslash pi\_(f)\; =\; f(j)$ is called the ''j''th projection map
In mathematics, a projection is a mapping of a set (or other mathematical structure) into a subset (or sub-structure), which is equal to its square for mapping composition, i.e., which is idempotent. The restriction to a subspace of a project ...

.
Cartesian power is a Cartesian product where all the factors ''Xcardinal exponentiation
In mathematics, cardinal numbers, or cardinals for short, are a generalization of the natural numbers used to measure the cardinality (size) of sets. The cardinality of a finite set is a natural number: the number of elements in the set. The ...

. An important special case is when the index set is $\backslash mathbb$, the natural numbers
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''cardinal n ...

: this Cartesian product is the set of all infinite sequences with the ''i''th term in its corresponding set ''Xvector
Vector most often refers to:
*Euclidean vector, a quantity with a magnitude and a direction
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...

with countably infinite real number components. This set is frequently denoted $\backslash mathbb^\backslash omega$, or $\backslash mathbb^$.
Other forms

Abbreviated form

If several sets are being multiplied together (e.g., ''X''Cartesian product of functions

If ''f'' is a function from ''X'' to ''A'' and ''g'' is a function from ''Y'' to ''B'', then their Cartesian product is a function from to with : $(f\backslash times\; g)(x,\; y)\; =\; (f(x),\; g(y)).$ This can be extended totuple
In mathematics, a tuple is a finite ordered list (sequence) of elements. An -tuple is a sequence (or ordered list) of elements, where is a non-negative integer. There is only one 0-tuple, referred to as ''the empty tuple''. An -tuple is defi ...

s and infinite collections of functions.
This is different from the standard Cartesian product of functions considered as sets.
Cylinder

Let $A$ be a set and $B\; \backslash subseteq\; A$. Then the ''cylinder'' of $B$ with respect to $A$ is the Cartesian product $B\; \backslash times\; A$ of $B$ and $A$. Normally, $A$ is considered to be theuniverse
The universe is all of space and time and their contents, including planets, stars, galaxies, and all other forms of matter and energy. The Big Bang theory is the prevailing cosmological description of the development of the universe. A ...

of the context and is left away. For example, if $B$ is a subset of the natural numbers $\backslash mathbb$, then the cylinder of $B$ is $B\; \backslash times\; \backslash mathbb$.
Definitions outside set theory

Category theory

Although the Cartesian product is traditionally applied to sets,category theory
Category theory is a general theory of mathematical structures and their relations that was introduced by Samuel Eilenberg and Saunders Mac Lane in the middle of the 20th century in their foundational work on algebraic topology. Nowadays, cat ...

provides a more general interpretation of the product of mathematical structures. This is distinct from, although related to, the notion of a Cartesian square
In mathematics, specifically set theory, the Cartesian product of two sets ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\tim ...

in category theory, which is a generalization of the fiber product
In category theory, a branch of mathematics, a pullback (also called a fiber product, fibre product, fibered product or Cartesian square) is the limit of a diagram consisting of two morphisms and with a common codomain. The pullback is often ...

.
Exponentiation
Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to ...

is the right adjoint
In mathematics, specifically category theory, adjunction is a relationship that two functors may exhibit, intuitively corresponding to a weak form of equivalence between two related categories. Two functors that stand in this relationship are kno ...

of the Cartesian product; thus any category with a Cartesian product (and a final object
In category theory, a branch of mathematics, an initial object of a category is an object in such that for every object in , there exists precisely one morphism .
The dual notion is that of a terminal object (also called terminal element): ...

) is a Cartesian closed category
In category theory, a category is Cartesian closed if, roughly speaking, any morphism defined on a product of two objects can be naturally identified with a morphism defined on one of the factors. These categories are particularly important in m ...

.
Graph theory

In graph theory, the Cartesian product of two graphs ''G'' and ''H'' is the graph denoted by , whosevertex
Vertex, vertices or vertexes may refer to:
Science and technology Mathematics and computer science
*Vertex (geometry), a point where two or more curves, lines, or edges meet
*Vertex (computer graphics), a data structure that describes the position ...

set is the (ordinary) Cartesian product and such that two vertices (''u'',''v'') and (''u''′,''v''′) are adjacent in , if and only if and ''v'' is adjacent with ''v''′ in ''H'', ''or'' and ''u'' is adjacent with ''u''′ in ''G''. The Cartesian product of graphs is not a product in the sense of category theory. Instead, the categorical product is known as the tensor product of graphs
In graph theory, the tensor product of graphs and is a graph such that
* the vertex set of is the Cartesian product ; and
* vertices and are adjacent in if and only if
** is adjacent to in , and
** is adjacent to in .
The tensor pro ...

.
See also

*Binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and i ...

* Concatenation of sets of strings
* Coproduct
In category theory, the coproduct, or categorical sum, is a construction which includes as examples the disjoint union of sets and of topological spaces, the free product of groups, and the direct sum of modules and vector spaces. The coprod ...

* Cross product
* Direct product of groups
* Empty product
In mathematics, an empty product, or nullary product or vacuous product, is the result of multiplying no factors. It is by convention equal to the multiplicative identity (assuming there is an identity for the multiplication operation in question ...

* Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean ...

* Exponential object
In mathematics, specifically in category theory, an exponential object or map object is the categorical generalization of a function space in set theory. Categories with all finite products and exponential objects are called cartesian closed c ...

* Finitary relation
* Join (SQL) § Cross join
* Orders on the Cartesian product of totally ordered sets
* Axiom of power set
In mathematics, the axiom of power set is one of the Zermelo–Fraenkel axioms of axiomatic set theory.
In the formal language of the Zermelo–Fraenkel axioms, the axiom reads:
:\forall x \, \exists y \, \forall z \, \in y \iff \forall w \ ...

(to prove the existence of the Cartesian product)
* Product (category theory)
In category theory, the product of two (or more) objects in a category is a notion designed to capture the essence behind constructions in other areas of mathematics such as the Cartesian product of sets, the direct product of groups or rings ...

* Product topology
In topology and related areas of mathematics, a product space is the Cartesian product of a family of topological spaces equipped with a natural topology called the product topology. This topology differs from another, perhaps more natural-seemi ...

* Product type
In programming languages and type theory, a product of ''types'' is another, compounded, type in a structure. The "operands" of the product are types, and the structure of a product type is determined by the fixed order of the operands in the prod ...

* Ultraproduct
The ultraproduct is a mathematical construction that appears mainly in abstract algebra and mathematical logic, in particular in model theory and set theory. An ultraproduct is a quotient of the direct product of a family of structures. All factors ...

References

External links

Cartesian Product at ProvenMath

*

{{Mathematical logic Axiom of choice Operations on sets