next up previous contents
Next: Binary relations Up: Sets Previous: Symmetric difference   Contents

The cartesian product of sets

Definition 3.3.1   Let $ A$ and $ B$ be two sets. The cartesian product of $ A$ and $ B$, denoted $ A \times B$, is the set of all ordered pairs $ (a,b)$ such that $ a \in A$ and $ b \in B$.

$\displaystyle A \times B = \{ (a,b) \; \vert \; a \in A, \; b \in B \}.$    

For example, if $ A=\{ a,b,c \}$ and $ B= \{ 1,2 \}$, then

$\displaystyle A \times B = \{ (a,1), (a,2), (b,1), (b,2), (c,1), (c,2) \}.$    

Graphic presentations can always help to understand; we represent the elements of $ A$ as points on an horizontal axis and the elements of $ B$ on a vertical axis, as in figure 18. The elements of the cartesian products are then represented by the crossing points of the lattice of parallels to the axes through the points defined above. In Figure [*], we display a graphical representation for the above example.

Figure 18: The cartesian product of two sets.
\begin{figure}
\centering\mbox{\epsfig{file=CartesianProduct.eps,height=4cm}}
\end{figure}

Remark 3.3.2   In general, $ A \times B \neq B \times A$.

For example, if $ A$ and $ B$ are as above, we have:

$\displaystyle B \times A = \{ (1,a), (2,a), (1,b), (2,b), (1,c), (2,c) \}.$    

Notation 1   For any set $ A$, we denote $ A^2=A \times A$.

The set $ \mathbb{R}^2$ studied extensively in Linear Algebra is the cartesian product of $ \mathbb{R}$ with itself. In this case the coordinate axes in the plane show the plane as a graphic presentation of $ \mathbb{R}^2$. The notion of the cartesian product of two sets can be generalized to three (or more) sets. First note that for three sets $ A$, $ B$ and $ C$, we have $ A \times ( B \times C) \neq (A \times B) \times C$: the elements of $ A \times ( B \times C)$ are ordered pairs whose first component is an element of $ A$ and whose second element is an ordered pair belonging to $ B \times C$; the elements of $ (A \times B) \times
C$ are ordered pairs whose first component is an ordered pair belonging to $ A \times B$ and whose second element belongs to $ C$. Now we denote by $ A \times B \times C$ the set of ordered triples $ (a,b,c)$ where $ a \in A$, $ b \in B$ and $ c \in C$.

$\displaystyle A \times B \times C = \{ (a,b,c) \; \vert \; a \in A, b \in B, c \in C \}.$    

We generalize this definition to the product of $ n$ sets $ A_1$, $ \dots$, $ A_n$:

$\displaystyle A_1 \times \dots \times A_n= \{ (a_1, \dots , a_n ) \; \vert \; \forall
 i=1,\dots , n, \; a_i \in A_i \}.$    

For a set $ A$, the cartesian power $ A^n$ is defined in the obvious way.

Proposition 3.3.3   If $ A$, $ B$ and $ C$ are three sets, then

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

Proof. The pair $ (x,y)$ is an element of $ A \times (B \cap C)$ if, and only if, $ x \in A$ and $ y \in B \cap C$, i.e. $ y \in B$ and $ y \in C$; therefore $ (x,y) \in A \times B$ and $ (x,y) \in A \times C$, i.e. $ (x,y) \in (A \times B) \cap (A \times C)$. Conversely, take $ (x,y) \in (A \times B) \cap (A \times C)$, i.e. $ (x,y) \in (A \times B)$ and $ (x,y) \in (A \times C)$; it follows that $ y \in B$ and $ y \in C$, thus $ y \in B \cap C$ and $ (x,y) \in A
\times (B \cap C)$. $ \qedsymbol$


next up previous contents
Next: Binary relations Up: Sets Previous: Symmetric difference   Contents
root 2002-06-10