## Cartesian Products and Power Sets

While the last section discussed combining sets of individual members to create another set of individual members, here we discuss creating sets of non-repeating tuples (pairs, triplets, and higher groupings). Later in the course, we will see how to calculate the number of tuples that would be created under various circumstances.

#### 1.3 Cartesian Products and Power Sets

##### 1.3.1 Cartesian Products

Definition 1.3.1: Cartesian Product. Let A and B be sets. The Cartesian product of A and B, denoted by A × B, is defined as follows: A × B = {(a, b) a  and b  B} , that is, A × B is the set of all possible ordered pairs whose first component comes from A and whose second component comes from B

Example 1.3.2: Some Cartesian Products. Notation in mathematics is often developed for good reason. In this case, a few examples will make clear why the symbol × is used for Cartesian products.

• Let A = {1, 2, 3} and B = {4, 5}. Then A×B = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}. Note that | A × B= 6 = |A| × |B|.
• A × A = {(1, 1), (1, 2), (1, 3), (2, 1) , (2, 2), (2, 3), (3, 1), (3, 2), (3 , 3) }. Note that |A × A| = 9 = |A|2.

These two examples illustrate the general rule that if A and B are finite sets, then |A × B| = |A| × |B|.

We can define the Cartesian product of three (or more) sets similarly. For example, A × B × C = {(a, b, c) : a ∈ A, b ∈ B, c ∈ C }.

It is common to use exponents if the sets in a Cartesian product are the same:

A2× A

A3× × A

and in general,

$A^n = \frac{A \times A \times ... \times A}{n \; \mathrm{factors}}$

##### 1.3.2 Power Sets

Definition 1.3.3: Power Set. If A is any set, the power set of A is the set of all subsets of A, denoted $\wp (A)$The two extreme cases, the empty set and all of A, are both included in $\wp (A)$.

Example 1.3.4: Some Power Sets.

• $\wp (\emptyset) = \left \{ \emptyset \right \}$
• $\wp (\left \{ 1 \right \}) = \left \{ \emptyset, \left \{ 1 \right \} \right \}$
• $\wp (\left \{ 1,2 \right \}) = \left \{ \emptyset, \left \{ 1 \right \}, \left \{2 \right \}, \left \{1,2 \right \} \right \}$

We will leave it to you to guess at a general formula for the number of elements in the power set of a finite set.