## 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 *∈* **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}*B*= {4, 5}. Then*A**×**B**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*|*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:

##### 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 . The two extreme cases, the empty set and all of *A*, are both included in .

**Example
1.3.4: Some
Power Sets.**

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.

Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.