Definition:Cartesian Product

From ProofWiki
Jump to: navigation, search

This page is about (cartesian) cross product. For other uses, see Definition:Cross Product.


Let $S$ and $T$ be sets or classes.

The cartesian product $S \times T$ of $S$ and $T$ is the set (or class) of ordered pairs $\tuple {x, y}$ with $x \in S$ and $y \in T$:

$S \times T = \set {\tuple {x, y}: x \in S \land y \in T}$

Another way of defining it is by:

$\tuple {x, y} \in S \times T \iff x \in S, y \in T$

More specifically:

$\forall p: \paren {p \in S \times T \iff \exists x: \exists y: x \in S \land y \in T \land p = \tuple {x, y} }$

$S \times T$ can be voiced $S$ cross $T$.

Finite Cartesian Product

Let $\sequence {S_n}$ be a sequence of sets.

The cartesian product of $\sequence {S_n}$ is defined as:

$\displaystyle \prod_{k \mathop = 1}^n S_k = \set {\tuple {x_1, x_2, \ldots, x_n}: \forall k \in \N^*_n: x_k \in S_k}$

It is also denoted $S_1 \times S_2 \times \cdots \times S_n$.

Thus $S_1 \times S_2 \times \cdots \times S_n$ is the set of all ordered $n$-tuples $\tuple {x_1, x_2, \ldots, x_n}$ with $x_k \in S_k$.

Countable Cartesian Product

The same notation can be used to define the (countable) cartesian product of an infinite sequence:

Let $\left \langle {S_n} \right \rangle_{n \mathop \in \N}$ be an infinite sequence of sets.

The cartesian product of $\left \langle {S_n} \right \rangle$ is defined as:

$\displaystyle \prod_{k \mathop = 1}^\infty S_k = \left\{{\left({x_1, x_2, \ldots, x_n, \ldots}\right): \forall k \in \N: x_k \in S_k}\right\}$

It defines the concept:

$S_1 \times S_2 \times \cdots \times S_n \times \cdots$

Thus $\displaystyle \prod_{k \mathop = 1}^\infty S_k$ is the set of all infinite sequences $\left({x_1, x_2, \ldots, x_n, \ldots}\right)$ with $x_k \in S_k$.

Uncountable Cartesian Product

Let $I$ be an indexing set with uncountable cardinality.

Let $\left\langle{\left({S_\alpha}\right)}\right \rangle_{\alpha \mathop \in I}$ be a family of sets indexed by $I$.

The cartesian product of $\left \langle {S_\alpha} \right \rangle$ is denoted:

$\displaystyle \prod_{\alpha \mathop \in I} S_\alpha$

Family of Sets

Definition 1

Let $I$ be an indexing set.

Let $\left\langle{S_i}\right\rangle_{i \mathop \in I}$ be an family of sets indexed by $I$.

The Cartesian product of $\left\langle{S_i}\right\rangle_{i \mathop \in I}$ is the set of all families $\left\langle{s_i}\right\rangle_{i \mathop \in I}$ with $s_i \in S_i$ for each $i \in I$.

This can be denoted $\displaystyle \prod_{i \mathop \in I} S_i$ or, if $I$ is understood, $\displaystyle \prod_i S_i$.

Definition 2

Let $\family {S_i}_{i \mathop \in I}$ be an indexed family of sets.

The Cartesian product of $\family{S_i}_{i \mathop \in I}$ is the set:

$\displaystyle \prod_{i \mathop \in I} S_i := \set {f: \paren {f: I \to \bigcup_{i \mathop \in I} S_i} \land \paren {\forall i \in I: \paren {f \paren i \in S_i} } }$

where $f$ denotes a mapping.

When $S_i = S$ for all $i \in I$, the expression is written:

$\displaystyle S^I := \set {f: \paren {f: I \to S} \land \paren {\forall i \in I: \paren {f \paren i \in S} } }$

which follows from Union is Idempotent:

$\displaystyle \bigcup_{i \mathop \in I} S = S$

Cartesian Space

Let $S$ be a set.

The cartesian $n$th power of $S$, or $S$ to the power of $n$, is defined as:

$\displaystyle S^n = \prod_{k \mathop = 1}^n S = \set {\tuple {x_1, x_2, \ldots, x_n}: \forall k \in \N^*_n: x_k \in S}$

Thus $S^n = \underbrace{S \times S \times \cdots \times S}_{n \text{ times} }$

Alternatively it can be defined recursively:

$S^n = \begin{cases} S: & n = 1 \\ S \times S^{n-1} & n > 1 \end{cases}$

The set $S^n$ called a cartesian space.

An element $x_j$ of an ordered tuple $\left({x_1, x_2, \ldots, x_n}\right)$ of a cartesian space $S^n$ is known as a basis element of $S^n$.


Let $S \times T$ be the cartesian product of $S$ and $T$.

Then the sets $S$ and $T$ are called the factors of $S \times T$.


Let $\displaystyle \prod_{i \mathop \in I} S_i$ be a cartesian product.

Let $j \in I$, and let $s = \sequence {s_i}_{i \mathop \in I} \in \displaystyle \prod_{i \mathop \in I} S_i$.

Then $s_j$ is called the $j$th coordinate of $s$.

If the indexing set $I$ consists of ordinary numbers $1, 2, \ldots, n$, one speaks about, for example, the first, second, or $n$th coordinate.

For an element $\tuple {s, t} \in S \times T$ of a binary cartesian product, $s$ is the first coordinate, and $t$ is the second coordinate.

Axiomatic Set Theory

The concept of the cartesian product is shown in Kuratowski Formalization of Ordered Pair to be constructible from the Zermelo-Fraenkel axioms.

Also known as

Some authors call this the direct product of $S$ and $T$.

Some call it the cartesian product set, others just the product set.

Some authors use uppercase for the initial, that is: Cartesian product.

It is also known as the cross product of two sets, but this can be confused with other usages of this term.

The notation for the cartesian power of a set $S^n$ should not be confused with the notation used for the conjugate of a set.

Also beware not to confuse the name of the concept itself with that of the power set $\powerset S$ of $S$.


Product of Arbitrary Sets

Let $S = \set {1, 2, 3}$.

Let $T = \set {a, b}$.


\(\displaystyle S \times T\) \(=\) \(\displaystyle \set {\tuple {1, a}, \tuple {1, b}, \tuple {2, a}, \tuple {2, b}, \tuple {3, a}, \tuple {3, b} }\) $\quad$ $\quad$
\(\displaystyle T \times S\) \(=\) \(\displaystyle \set {\tuple {a, 1}, \tuple {a, 2}, \tuple {a, 3}, \tuple {b, 1}, \tuple {b, 2}, \tuple {b, 3} }\) $\quad$ $\quad$

Also see

  • Results about Cartesian products can be found here.

Source of Name

This entry was named for René Descartes.