HOME

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 concern ...
, 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. Defining ...
, 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 de ...
. 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. Mathem ...
, 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, 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 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 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. Mathem ...
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. Every ...
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 (x, y) = \. Under this definition, (x, y) is an element of \mathcal(\mathcal(X \cup Y)), 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 pos ...
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 pos ...
, 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 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 othe ...
. 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). : (A\times B)\times C \neq A \times (B \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 \cap B) \times (C \cap D) = (A \times C) \cap (B \times D) 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: (A \times C) \cup (B \times D) = A \setminus B) \times C\cup A \cap B) \times (C \cup D)\cup B \setminus A) \times D/math> For the set difference, we also have the following identity: (A \times C) \setminus (B \times D) = \times (C \setminus D)\cup A \setminus B) \times C/math> Here are some rules demonstrating distributivity with other operators (see leftmost picture):Singh, S. (August 27, 2009). ''Cartesian product''. Retrieved from the Connexions Web site: http://cnx.org/content/m15207/1.5/ \begin A \times (B \cap C) &= (A \times B) \cap (A \times C), \\ A \times (B \cup C) &= (A \times B) \cup (A \times C), \\ A \times (B \setminus C) &= (A \times B) \setminus (A \times C), \end :(A \times B)^\complement = \left(A^\complement \times B^\complement\right) \cup \left(A^\complement \times B\right) \cup \left(A \times B^\complement\right)\!, where A^\complement denotes the absolute complement 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 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. Every ...
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 in ...
). 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 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 th ...
''X''.


Infinite Cartesian products

It is possible to define the Cartesian product of an arbitrary (possibly infinite)
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. 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 consist ...
, 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 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 consist ...
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 o ...
, 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 projec ...
. 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. 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 ''Xi''. For example, each element of : \prod_^\infty \mathbb R = \mathbb R \times \mathbb R \times \cdots can be visualized as a vector 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 : (f\times g)(x, y) = (f(x), g(y)). 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 de ...
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. Acc ...
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, cate ...
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 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 r ...
is the right adjoint of the Cartesian product; thus any category with a Cartesian product (and a final object) is a Cartesian closed category.


Graph theory

In
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 conne ...
, 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 positio ...
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.


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 in ...
* 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 copro ...
* Cross product *
Direct product of groups In mathematics, specifically in group theory, the direct product is an operation that takes two groups and and constructs a new group, usually denoted . This operation is the group-theoretic analogue of the Cartesian product of sets and is on ...
* Empty product *
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 * 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-seemin ...
* Product type *
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 fact ...


References


External links


Cartesian Product at ProvenMath
*

{{Mathematical logic Axiom of choice Operations on sets