In 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 co ...

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, whe ...

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

, whose formulation of analytic geometry gave rise to the concept, which is further generalized in terms of

direct product In mathematics, one can often define a direct product of objects already known, giving a new one. This generalizes the Cartesian product of the underlying sets, together with a suitably defined structure on the product set. More abstractly, one t ...

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

, 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 Disjoint may refer to: *Disjoint sets, sets with no common elements *Mutual exclusivity, the impossibility of a pair of propositions both being true See also *Disjoint union *Disjoint-set data structure {{disambig

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) Infinite ( ko, 인피니트; stylized as INFINITE) is a South Ko ...

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''₁, ..., ''X_n'' 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''₁×⋯×''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 Plane(s) most often refers to: * Aero- or airplane, a powered, fixed-wing aircraft * Plane (geometry), a flat, 2-dimensional surface Plane or planes may also refer to: Biology * Plane (tree) or ''Platanus'', wetland native plant * ''Planes'' ...

where R is the set of

real number In mathematics, a real number is a number that can be used to measurement, measure a ''continuous'' one-dimensional quantity such as a distance, time, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small var ...

s: R² 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 ...

). 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 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, t ...

, corresponding to the

empty function In mathematics, a function from a set to a set assigns to each element of exactly one element of .; the words map, mapping, transformation, correspondence, and operator are often used synonymously. The set is called the domain of the func ...

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

''X''.

Infinite Cartesian products

It is possible to define the Cartesian product of an arbitrary (possibly

)

of sets. If ''I'' is any

index set In mathematics, an index set is a set whose members label (or index) members of another set. For instance, if the elements of a set may be ''indexed'' or ''labeled'' by means of the elements of a set , then is an index set. The indexing consis ...

, 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

such that the value of the function at a particular index ''i'' is an element of ''X_i''. Even if each of the ''X_i'' 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_(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 ''X_i'' 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 ''X^I''. 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 Set (mathematics), sets. The cardinality of a finite set is a natural number: the number of elemen ...

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

: this Cartesian product is the set of all infinite sequences with the ''i''th term in its corresponding set ''X_i''. 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''₁, ''X''₂, ''X''₃, …), 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 :

(f\times g)(x, y) = (f(x), g(y)).

This can be extended to

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

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

B \times \mathbb

Definitions outside set theory

Category theory

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

product Product may refer to: Business * Product (business), an item that serves as a solution to a specific consumer problem. * Product (project management), a deliverable or set of deliverables that contribute to a business solution Mathematics * Prod ...

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

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

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

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

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 (mathematics), category is an object in such that for every object in , there exists precisely one morphism . The dual (category theory), dual notion is that of a t ...

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

Graph theory

graph theory In mathematics, graph theory is the study of '' graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, 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

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

References

External links

Cartesian Product at ProvenMath
*

{{Mathematical logic Axiom of choice Operations on sets