CS202: Discrete Structures

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} 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|².

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: 

A² = A × A

A³ = A × A × A

and in general,

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