Definition:Cartesian Product/Family of Sets

From ProofWiki
Jump to: navigation, search

Definition

Definition 1

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 $\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 {\map f 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 {\map f i \in S} } }$

which follows from Union is Idempotent:

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


Uncountable Cartesian Product

Using this notation, it is then possible to define the Cartesian product of an uncountable family:


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

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


The cartesian product of $\family {S_\alpha}$ is denoted:

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


Axiom of Choice

It is of the utmost importance that one be aware that for many $I$, establishing non-emptiness of $\displaystyle \prod_{i \mathop \in I} S_i$ requires a suitable version of the Axiom of Choice.

Details on this correspondence can be found on Equivalence of Versions of Axiom of Choice.


Also denoted as

Some sources use $\def \bigtimes {\mathop {\vcenter {\huge \times} } } \bigtimes_{i \mathop \in I} S_i$ for $\displaystyle \prod_{i \mathop \in I} S_i$.


Examples

Household Pets

Informally it is like this. We have a set of sets which are indexed by the indexing set can be anything, as long as it is ordered. We think of it as numbers, but it could be anything. The indexing set indentifies both sets, and elements in the tuple.

Let $I$ be the set of household pets:

$I := \set {\text {Bruiser}, \text {Claude} }$

Let $T$ be the set of toys they play with:

$T:= \set {\text {rubber bone}, \text {chewed tennis ball}, \text {missing slipper}, \text {jingly roller}, \text {fluffy mouse on a string}, \text {table tennis ball} }$

The set of toys played with by $\text {Bruiser}$ consist of:

$\set {\text {rubber bone}, \text {chewed tennis ball}, \text {missing slipper} }$

The set of toys played with by $\text {Claude}$ consist of:

$\set {\text {table tennis ball}, \text {jingly roller}, \text {fluffy mouse on a string} }$


Thus we have a tuple of sets:

$\tuple {\set {\text {rubber bone}, \text {chewed tennis ball}, \text {missing slipper} }, \set {\text {table tennis ball}, \text {jingly roller}, \text {fluffy mouse on a string} } }$


Let $I = \set {\text {Bruiser}, \text {Claude} }$ be considered as an indexing set.

The tuple indexed by $\text {Bruiser}$ is:

$\set {\text {rubber bone}, \text {chewed tennis ball}, \text {missing slipper} }$

The tuple indexed by $\text {Claude}$ is:

$\set {\text {table tennis ball}, \text {jingly roller}, \text {fluffy mouse on a string} }$

The Cartesian product of the toys of $\text {Bruiser}$ and $\text {Claude}$ is:

$\left \{ {\tuple {\text {rubber bone}, \text {jingly roller} }, \tuple {\text {chewed tennis ball}, \text {jingly roller} }, \tuple {\text {missing slipper}, \text {jingly roller} }, }\right.$
$\left. {\tuple {\text {rubber bone}, \text {table tennis ball} }, \tuple {\text {chewed tennis ball}, \text {table tennis ball} }, \tuple {\text {missing slipper}, \text {table tennis ball} }, }\right.$
$\left. {\tuple {\text {rubber bone}, \text {fluffy mouse on a string} }, \tuple {\text {chewed tennis ball}, \text {fluffy mouse on a string} }, \tuple {\text {missing slipper}, \text {fluffy mouse on a string} } }\right\}$


Each of these tuples is indexed by $\set {\text {Bruiser}, \text {Claude} }$.

So $\tuple {\text {chewed tennis ball}, \text {fluffy mouse on a string} }$ indexed by $\text {Bruiser}$ is $\text {chewed tennis ball}$.

$\tuple {\text {chewed tennis ball}, \text {fluffy mouse on a string} }$ indexed by $\text {Claude}$ is $\text {fluffy mouse on a string}$.


Also see

  • Results about Cartesian products can be found here.


Source of Name

This entry was named for René Descartes.