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 pairs where ''a'' is in ''A'' and ''b'' is in ''B''.
In terms of
set-builder notation, that is
:
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. An ordered pair is a
2-tuple or couple. More generally still, one can define the Cartesian product of an
indexed family of sets.
The Cartesian product is named after
René Descartes, 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 engineer ...
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 used ...
. 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, 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 ...
between them, under which (3, ♣) corresponds to (♣, 3) and so on.
A two-dimensional coordinate system
The main historical example is the
Cartesian plane
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 in ...
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 engineer ...
. In order to represent geometrical shapes in a numerical way, and extract numerical information from shapes' numerical representations,
René Descartes assigned to each point in the plane a pair of
real numbers, called its
coordinates
In geometry, a coordinate system is a system that uses one or more numbers, or coordinates, to uniquely determine the position of the points or other geometric elements on a manifold such as Euclidean space. The order of the coordinates is sign ...
. 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. The most common definition of ordered pairs,
Kuratowski's definition, is
. Under this definition,
is an element of
, and
is a subset of that set, where
represents the
power set operator. Therefore, the existence of the Cartesian product of any two sets in
ZFC follows from the axioms of
pairing
In mathematics, a pairing is an ''R''-bilinear map from the Cartesian product of two ''R''- modules, where the underlying ring ''R'' is commutative.
Definition
Let ''R'' be a commutative ring with unit, and let ''M'', ''N'' and ''L'' be ''R''-mo ...
,
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''U ...
,
power set, and
specification. 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,
:
because the
ordered pairs 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
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
.
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 replacement ...
(unless one of the involved sets is empty).
:
If for example ''A'' = , then .
Intersections, unions, and subsets
The Cartesian product satisfies the following property with respect to
intersections
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, their ...
(see middle picture).
:
In most cases, the above statement is not true if we replace intersection with
union
Union commonly refers to:
* Trade union, an organization of workers
* Union (set theory), in mathematics, a fundamental operation on sets
Union may also refer to:
Arts and entertainment
Music
* Union (band), an American rock group
** ''U ...
(see rightmost picture).
In fact, we have that: