Cartesian Product · aiwiki.page

The Cartesian product is a construction in set theory that combines sets by forming all ordered selections of their elements. For two sets $A$ and $B$ , it is written $A\times B$ and consists of every ordered pair $(a,b)$ with $a\in A$ and $b\in B$ . The construction extends to finite lists and arbitrary indexed families of sets. Unlike numerical multiplication, its result is a set whose elements retain their coordinate positions. (homepages.ucl.ac.uk)

Definition and examples

Formally,

A\times B=\{(a,b)\mid a\in A,\ b\in B\}.

The defining property of ordered pairs is

(a,b)=(c,d)\quad\Longleftrightarrow\quad a=c\text{ and }b=d.

Thus order matters within each pair, although the order in which the pairs are listed does not matter. Coordinates may be numbers, symbols, sets, or other mathematical objects. (homepages.ucl.ac.uk)

For example, if $A=\{1,2\}$ and $B=\{x,y,z\}$ , then

A\times B= \{(1,x),(1,y),(1,z),(2,x),(2,y),(2,z)\}.

Each element of $A$ is paired with every element of $B$ , so the product has six elements. The factors need not be disjoint, and repeated coordinates are permitted: $(1,1)$ belongs to $\{1,2\}\times\{1,2\}$ . (math.libretexts.org)

In geometry, the product of the real numbers with themselves,

\mathbb R^2=\mathbb R\times\mathbb R,

provides the coordinate representation of the plane. More generally, $\mathbb R^n$ , equipped with its usual geometric structure, represents $n$ -dimensional Euclidean space. (math.libretexts.org)

Basic properties

If either factor is the empty set, the product is empty:

A\times\varnothing=\varnothing\times A=\varnothing.

Conversely, two nonempty factors have a nonempty product, since choosing one element from each produces an ordered pair. (math.unm.edu)

Cartesian products are not generally commutative as literal sets: $A\times B$ need not equal $B\times A$ . Nevertheless, coordinate reversal,

(a,b)\longmapsto(b,a),

is a bijection between them. Similarly, $(A\times B)\times C$ and $A\times(B\times C)$ contain differently nested pairs, but the reassociation map

((a,b),c)\longmapsto(a,(b,c))

is a natural bijection. Mathematical notation often suppresses these distinctions by identifying both with ordered triples. (math.cmu.edu)

Products distribute over union and intersection in either coordinate. For example,

A\times(B\cup C)=(A\times B)\cup(A\times C),

A\times(B\cap C)=(A\times B)\cap(A\times C).

These identities follow by checking coordinate membership. (math.libretexts.org)

For finite sets, the cardinality satisfies

|A\times B|=|A|\,|B|.

There are $|B|$ possible second coordinates for each of the $|A|$ first coordinates. This is an instance of the multiplication principle in combinatorics. (homepages.ucl.ac.uk)

Finite and indexed products

For sets $A_1,\ldots,A_n$ , the finite product is

\prod_{i=1}^{n}A_i =\{(a_1,\ldots,a_n)\mid a_i\in A_i\text{ for every }i\}.

Its elements are ordered tuples. When all factors are the same set $A$ , the notation $A^n$ is customary. If the factors are finite, their cardinalities multiply. (math.unm.edu)

For an arbitrary index set $I$ , a product element is described as a function selecting one coordinate from each factor:

\prod_{i\in I}A_i = \left\{ f:I\to\bigcup_{i\in I}A_i \ \middle|\ f(i)\in A_i\text{ for every }i \right\}.

This definition accommodates infinite families without requiring a finite tuple notation. When $I$ is empty, there is exactly one such function—the empty function—so the empty product is a singleton. (public.csusm.edu)

A finite product of nonempty sets is nonempty without any additional choice principle. For arbitrary families, the assertion that every product of nonempty sets is nonempty is equivalent, in Zermelo–Fraenkel set theory, to the axiom of choice. (math.uwaterloo.ca)

Relations, functions, and projections

A binary relation from $A$ to $B$ is a subset of $A\times B$ : it specifies which pairs satisfy a particular condition. A function $f:A\to B$ has a graph

\{(a,f(a))\mid a\in A\}\subseteq A\times B,

with exactly one output paired with each input. Cartesian products therefore supply the ambient sets used to describe relations and function graphs. (math.cmu.edu)

The coordinate projections are

\pi_A(a,b)=a,\qquad \pi_B(a,b)=b.

They express a universal property: given functions $f:X\to A$ and $g:X\to B$ , there is a unique function

h:X\to A\times B,\qquad h(x)=(f(x),g(x)),

such that $\pi_A\circ h=f$ and $\pi_B\circ h=g$ , where $\circ$ denotes function composition. This characterizes the product through its relationship with maps into the factors. (public.csusm.edu)

Additional structures and computing

For topological spaces, the Cartesian product of the underlying sets carries the product topology. In a finite product, products of open sets form a basis. For an infinite product, basic open sets restrict only finitely many coordinates, leaving every other coordinate unrestricted. The underlying set construction and the topology placed on it are distinct ingredients. (public.csusm.edu)

In a relational database, a cross join implements a Cartesian product of rows. An SQL expression such as T1 CROSS JOIN T2 combines every row of the first table with every row of the second, retaining the columns from both. If the tables contain $m$ and $n$ rows, the result contains $mn$ rows before filtering. SQL tables may retain duplicate rows, so this operation follows SQL’s row semantics rather than necessarily behaving as a duplicate-free mathematical set. (postgresql.org)