Section Cartesian Products of Sets
The final operation on sets that we discuss is the Cartesian product (or cross product). This is an operation that we have seen before. When we draw the graph of a line \(y = mx+b\) in the plane, we plot the points \((x,mx+b)\text{.}\) These points are ordered pairs of real numbers. We can extend this idea to any sets.
Definition 1.5.
Let \(A\) and \(B\) are sets. The Cartesian product of \(A\) and \(B\) is the set
\begin{equation*}
A \times B = \{(a,b) \mid a \in A \text{ and } b \in B\}\text{.}
\end{equation*}
In other words, the Cartesian product of \(A\) and \(B\) is the set of ordered pairs \((a,b)\) with \(a\) coming from \(A\) and \(b\) coming from \(B\text{.}\) Note that the order is important.
Activity 1.7.
(a)
List all of the elements in \(\{\text{ red } , \text{ blue } \} \times \{\text{ car } , \text{ truck } , \text{ van } \}\text{.}\)
(b)
If \(A\) has \(m\) elements and \(B\) has \(n\) elements, how many elements does the set \(A \times B\) have? Explain.
There is no reason to restrict ourselves to a Cartesian product of just two sets. This is an idea that we have encountered before. The Cartesian product \(\R \times \R\) is the standard real plane that we denote as \(\R^2\) and the Cartesian product \(\R \times \R \times \R\) is the three-dimensional real space denoted as \(\R^3\text{.}\) If we have an indexed collection \(\{X_{i}\}\) of sets, with \(i\) running through the set of positive integers, then we can define the Cartesian product of the sets \(X_{i}\) as the set of infinite sequences \((x_1, x_2, \ldots,
x_n, \ldots)\text{,}\) where \(x_i \in X_i\) for each \(i \in \Z^+\text{.}\) We denote this cartesian product as
\begin{equation*}
\Pi_{i \in \Z^+} X_i = \Pi_{i=1}^{\infty} X_i\text{.}
\end{equation*}
The capital pi (\(\Pi\)) is used to represent a product an an analog of the capital sigma (\(\Sigma\)) that is used to represent a sum. We will study sequences in more detail later.
To conclude this section we summarize some properties of sets. Many of these properties can be extended to arbitrary collections of sets. Most of the proofs are straightforward. The associative and distributive laws are left for
Exercise 3.
Theorem 1.6.
Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of a universal set \(U\text{.}\)
- Properties of the Empty Set
\(\displaystyle A \cap \emptyset = \emptyset\)
\(\displaystyle A \cup \emptyset = A\)
\(\displaystyle A-\emptyset = A\)
\(\displaystyle \emptyset^c = U\)
- Properties of the Universal Set
\(\displaystyle A \cap U = A\)
\(\displaystyle A \cup U = U\)
\(\displaystyle A-U = \emptyset\)
\(\displaystyle U^c = \emptyset\)
- Idempotent Laws
\(\displaystyle A \cap A = A\)
\(\displaystyle A \cup A = A\)
- Commutative Laws
\(\displaystyle A \cap B = B \cap A\)
\(\displaystyle A \cup B = B \cup A\)
- Associative Laws
\(\displaystyle (A \cap B) \cap C = A \cap (B \cap C)\)
\(\displaystyle (A \cup B) \cup C = A \cup (B \cup C)\)
- Distributive Laws
\(\displaystyle A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)
\(\displaystyle A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\)
- Basic Properties
\(\displaystyle \left(A^c\right)^c = A\)
\(\displaystyle A - B = A \cap B^c\)
- Subsets and Complements
\(\displaystyle A \subseteq B \text{ if and only if } B^c \subseteq A^c\)