Definition:Cartesian Product

From ProofWiki
(Redirected from Definition:Direct Product)
Jump to navigation Jump to search

This page is about Cartesian Cross Product in the context of Set Theory. For other uses, see Cross Product.

Definition

Let $S$ and $T$ be sets.


The cartesian product $S \times T$ of $S$ and $T$ is the set 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$.


Class Theory

Let $A$ and $B$ be classes.


The cartesian product $A \times B$ of $A$ and $B$ is the class of ordered pairs $\tuple {x, y}$ with $x \in A$ and $y \in B$:

$A \times B = \set {\tuple {x, y}: x \in A \land y \in B}$


Diagram

The following diagram illustrates the cartesian product of the line segment $S$ with the line segment $T$

CartesianProduct.png

The ordered pair $\tuple {s, t}$ formed from the element $s$ of $S$ and the element $t$ of $T$ is seen to be an element of $S \times T$.


Finite Cartesian Product

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

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

$\ds \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 $\sequence {S_n}_{n \mathop \in \N}$ be an infinite sequence of sets.

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

$\ds \prod_{k \mathop = 1}^\infty S_k = \set {\tuple {x_1, x_2, \ldots, x_n, \ldots}: \forall k \in \N: x_k \in S_k}$


It defines the concept:

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

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


Family of Sets

Let $I$ be an indexing set.

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

The cartesian product of $\family {S_i}_{i \mathop \in I}$ is the set of all families $\family {s_i}_{i \mathop \in I}$ with $s_i \in S_i$ for each $i \in I$.


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


Cartesian Space

Let $S$ be a set.

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

$\ds 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}_{\text{$n$ 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 $\tuple {x_1, x_2, \ldots, x_n}$ of a cartesian space $S^n$ is known as a basis element of $S^n$.


Factors

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$.


Coordinate

Let $\ds \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 \ds \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.


Also known as

The cartesian product of two sets has a number of different names in the literature:

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


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$.


Examples

Product of Arbitrary Sets: 1

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

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

Then:

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


Product of Arbitrary Sets: 2

Let $V = \set {v_1, v_2}$.

Let $W = \set {w_1, w_2, w_3}$.

Then:

\(\ds V \times W\) \(=\) \(\ds \set {\tuple {v_1, w_1}, \tuple {v_1, w_2}, \tuple {v_1, w_3}, \tuple {v_2, w_1}, \tuple {v_2, w_2}, \tuple {v_2, w_3} }\)
\(\ds V \times V\) \(=\) \(\ds \set {\tuple {v_1, v_1}, \tuple {v_1, v_2}, \tuple {v_2, v_1}, \tuple {v_2, v_2} }\)


Also see

  • Results about cartesian products can be found here.


Source of Name

This entry was named for René Descartes.


Historical Note

René Descartes is (rightly or wrongly) credited with inventing what is usually referred to as the Cartesian coordinate system of analytic geometry, in which points on (for example) the plane are identified with ordered pairs of real numbers.

Thus the plane is seen to be the Cartesian product of the set of real numbers $\R$ with itself.

Hence the reason for the name of the Cartesian product when used for general set or classes.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Cartesian_Product&oldid=730313"