TheInfoList

OR: In
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\times 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 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 the
standard 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 in
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 ...
. 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 of
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 ...
. The most common definition of ordered pairs, Kuratowski's definition, is $\left(x, y\right) = \$. Under this definition, $\left(x, y\right)$ is an element of $\mathcal\left(\mathcal\left(X \cup Y\right)\right)$, and $X\times Y$ is a subset of that set, where $\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 not
commutative 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 \times B \neq B \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). : $\left(A\times B\right)\times C \neq A \times \left(B \times C\right)$ If for example ''A'' = , then .

## Intersections, unions, and subsets

The Cartesian product satisfies the following property with respect to intersections (see middle picture). :$\left(A \cap B\right) \times \left(C \cap D\right) = \left(A \times C\right) \cap \left(B \times D\right)$ In most cases, the above statement is not true if we replace intersection with union (see rightmost picture). $(A \cup B) \times (C \cup D) \neq (A \times C) \cup (B \times D)$ In fact, we have that:
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: $\text A \subseteq B \text A \times C \subseteq B \times C;$ :$\text A,B \neq \emptyset \text A \times B \subseteq C \times D \!\iff\! A \subseteq C \text B \subseteq D.$

## Cardinality

The
cardinality 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''1, ..., ''Xn'' as the set : $X_1\times\cdots\times X_n = \$ 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 : $\.$

## ''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 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: R2 is the set of all points where ''x'' and ''y'' are real numbers (see the
Cartesian 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 = \underbrace_= \.$ An example of this is , with R again the set of real numbers, and more generally R''n''. The ''n''-ary Cartesian power of a set ''X'' is
isomorphic 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 (possibly
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 ...
)
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 $\_$ is a family of sets indexed by ''I'', then the Cartesian product of the sets in $\_$ is defined to be : $\prod_ X_i = \left\,$ 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''. Even if each of the ''Xi'' is nonempty, the Cartesian product may be empty if the
axiom 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 : $\pi_: \prod_ X_i \to X_,$ defined by $\pi_\left(f\right) = f\left(j\right)$ 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 ''Xi'' are the same set ''X''. In this case, : $\prod_ X_i = \prod_ X$ is the set of all functions from ''I'' to ''X'', and is frequently denoted ''XI''. This case is important in the study of
cardinal 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 $\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 ''Xi''. For example, each element of : $\prod_^\infty \mathbb R = \mathbb R \times \mathbb R \times \cdots$ can be visualized as a
vector 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 $\mathbb^\omega$, or $\mathbb^$.

# Other forms

## Abbreviated form

If several sets are being multiplied together (e.g., ''X''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 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 : $\left(f\times g\right)\left(x, y\right) = \left(f\left(x\right), g\left(y\right)\right).$ This can be extended to
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 ...
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 \subseteq A$. Then the ''cylinder'' of $B$ with respect to $A$ is the Cartesian product $B \times A$ of $B$ and $A$. Normally, $A$ is considered to be the
universe 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 $\mathbb$, then the cylinder of $B$ is $B \times \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 , whose
vertex 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 ...
.

*
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 ...