A table can be created by taking the Cartesian product of a set of rows and a set of columns. If the Cartesian productrows ×columns is taken, the cells of the table contain ordered pairs of the form(row value, column value).[4]
One can similarly define the Cartesian product ofn sets, also known as ann-fold Cartesian product, which can be represented by ann-dimensional array, where each element is ann-tuple. An ordered pair is a2-tuple or couple. More generally still, one can define the Cartesian product of anindexed family of sets.
A rigorous definition of the Cartesian product requires a domain to be specified in theset-builder notation. In this case the domain would have to contain the Cartesian product itself. For defining the Cartesian product of the sets and, with the typicalKuratowski's definition of a pair as, an appropriate domain is the set where denotes thepower set. Then the Cartesian product of the sets and would be defined as[6]
An illustrative example is thestandard 52-card deck. Thestandard playing card ranks {A, K, Q, J, 10, 9, 8, 7, 6, 5, 4, 3, 2} 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 52ordered pairs, which correspond to all 52 possible playing cards.
Ranks ×Suits returns a set of the form {(A, ♠), (A, ♥), (A, ♦), (A, ♣), (K, ♠), ..., (3, ♣), (2, ♠), (2, ♥), (2, ♦), (2, ♣)}.
Suits ×Ranks returns a set of the form {(♠, A), (♠, K), (♠, Q), (♠, J), (♠, 10), ..., (♣, 6), (♣, 5), (♣, 4), (♣, 3), (♣, 2)}.
These two sets are distinct, evendisjoint, but there is a naturalbijection between them, under which (3, ♣) corresponds to (♣, 3) and so on.
The main historical example is theCartesian plane inanalytic geometry. 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 ofreal numbers, called itscoordinates. Usually, such a pair's first and second components are called itsx andy 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.[7]
A formal definition of the Cartesian product fromset-theoretical principles follows from a definition ofordered 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 thepower set operator. Therefore, the existence of the Cartesian product of any two sets inZFC follows from the axioms ofpairing,union,power set, andspecification. Sincefunctions are usually defined as a special case ofrelations, 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.
Strictly speaking, the Cartesian product is notassociative (unless one of the involved sets is empty).If for exampleA = {1}, then(A ×A) ×A = {((1, 1), 1)} ≠{(1, (1, 1))} =A × (A ×A).
Thecardinality of a set is the number of elements of the set. For example, defining two sets:A = {a, b} andB = {5, 6}. Both setA and setB consist of two elements each. Their Cartesian product, written asA ×B, results in a new set which has the following elements:
A ×B = {(a,5), (a,6), (b,5), (b,6)}.
where each element ofA is paired with each element ofB, 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,
The Cartesian product can be generalized to then-ary Cartesian product overn setsX1, ...,Xn as the set
ofn-tuples. If tuples are defined asnested ordered pairs, it can be identified with(X1 × ... ×Xn−1) ×Xn. If a tuple is defined as a function on{1, 2, ...,n} that takes its value ati to be thei-th element of the tuple, then the Cartesian productX1 × ... ×Xn is the set of functions
TheCartesian square of a setX is the Cartesian productX2 =X ×X.An example is the 2-dimensionalplaneR2 =R ×R whereR is the set ofreal numbers:[1]R2 is the set of all points(x,y) wherex andy are real numbers (see theCartesian coordinate system).
TheCartesiannth power of a setX, denoted, can be defined as
An example of this isR3 =R ×R ×R, withR again the set of real numbers,[1] and more generallyRn.
The Cartesiannth power of a setX may be identified with the set of the functions mapping toX then-tuples of elements ofX. As a special case, the Cartesian 0th power ofX is thesingleton set, that has theempty function withcodomainX as its unique element.
, at the same time, if there exists at least one such that, then;[11]
, moreover, equality is possible only in the following cases:[12]
or;
for all except for one from.
The complement of a Cartesian product can be calculated,[12] if auniverse is defined. To simplify the expressions, we introduce the following notation. Let us denote the Cartesian product as a tuple bounded by square brackets; this tuple includes the sets from which the Cartesian product is formed, e.g.:
.
Inn-tuple algebra (NTA),[12] such a matrix-like representation of Cartesian products is called aC-n-tuple.
With this in mind, the union of some Cartesian products given in the same universe can be expressed as a matrix bounded by square brackets, in which the rows represent the Cartesian products involved in the union:
.
Such a structure is called aC-system in NTA.
Then the complement of the Cartesian product will look like the followingC-system expressed as a matrix of the dimension:
.
The diagonal components of this matrix are equal correspondingly to.
In NTA, a diagonalC-system, that represents the complement of aC-n-tuple, can be written concisely as a tuple of diagonal components bounded by inverted square brackets:
.
This structure is called aD-n-tuple. Then the complement of theC-system is a structure, represented by a matrix of the same dimension and bounded by inverted square brackets, in which all components are equal to the complements of the components of the initial matrix. Such a structure is called aD-system and is calculated, if necessary, as the intersection of theD-n-tuples contained in it. For instance, if the followingC-system is given:
,
then its complement will be theD-system
.
Let us consider some new relations for structures with Cartesian products obtained in the process of studying the properties of NTA.[12] The structures defined in the same universe are calledhomotypic ones.
The intersection of C-systems. Assume the homotypicC-systems are given and. Their intersection will yield aC-system containing all non-empty intersections of eachC-n-tuple from with eachC-n-tuple from.
Checking the inclusion of a C-n-tuple into a D-n-tuple. For theC-n-tuple and theD-n-tuple holds, if and only if, at least for one holds.
Checking the inclusion of a C-n-tuple into a D-system. For theC-n-tuple and theD-system is true, if and only if, for everyD-n-tuple from holds.
It is possible to define the Cartesian product of an arbitrary (possiblyinfinite)indexed family of sets. IfI is anyindex set, and is a family of sets indexed byI, then the Cartesian product of the sets in is defined to bethat is, the set of all functions defined on theindex setI such that the value of the function at a particular indexi is an element ofXi. Even if each of theXi is nonempty, the Cartesian product may be empty if theaxiom of choice, which is equivalent to the statement that every such product is nonempty, is not assumed. may also be denoted.[13]
For eachj inI, the functiondefined by is called thej-thprojection map.
Cartesian power is a Cartesian product where all the factorsXi are the same setX. In this case,is the set of all functions fromI toX, and is frequently denotedXI. This case is important in the study ofcardinal exponentiation. An important special case is when the index set is, thenatural numbers: this Cartesian product is the set of all infinite sequences with thei-th term in its corresponding setXi. For example, each element ofcan be visualized as avector with countably infinite real number components. This set is frequently denoted, or.
Iff is a function fromX toA andg is a function fromY toB, then their Cartesian productf ×g is a function fromX ×Y toA ×B with
This can be extended totuples and infinite collections of functions.This is different from the standard Cartesian product of functions considered as sets.
Let be a set and. Then thecylinder of with respect to is the Cartesian product of and.
Normally, is considered to be theuniverse of the context and is left away. For example, if is a subset of the natural numbers, then the cylinder of is.
Although the Cartesian product is traditionally applied to sets,category theory provides a more general interpretation of theproduct of mathematical structures. Product is the simplest example of categorical limit, where the indexing category is discrete. As category of sets can be identified with discrete categories and embedded this way as full subcategory of the diagrams indexing products can be reduced to indexing sets matching the set-theoretic definition.
Ingraph theory, theCartesian product of two graphsG andH is the graph denoted byG ×H, whosevertex set is the (ordinary) Cartesian productV(G) ×V(H) and such that two vertices(u,v) and(u′,v′) are adjacent inG ×H, if and only ifu =u′ andv is adjacent withv′ inH,orv =v′ andu is adjacent withu′ inG. The Cartesian product of graphs is not aproduct in the sense of category theory. Instead, the categorical product is known as thetensor product of graphs.
^F. R. Drake,Set Theory: An Introduction to Large Cardinals, p. 24. Studies in Logic and the Foundations of Mathematics, vol. 76 (1978). ISBN 0-7204-2200-0.
^Osborne, M., and Rubinstein, A., 1994.A Course in Game Theory. MIT Press.
