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 = {</span>(</span><i>a,</i><i> </i><i>b</i>)<span> <span style="">| </span></span><i style="font-size: 0.9375rem;">a </i><span style="font-size: 0.9375rem;">∈</span><i style="font-size: 0.9375rem;"> </i><i style="font-size: 0.9375rem;">A </i><span style="font-size: 0.9375rem;">and </span><i style="font-size: 0.9375rem;">b </i><span style="font-size: 0.9375rem;">∈</span><i style="font-size: 0.9375rem;"> </i><i style="font-size: 0.9375rem;">B</i><span style="font-size: 0.9375rem;">} , 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 = {</span>1, 2, 3} and B = {</span>4, 5}. Then A×B = {</span>(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)}. Note that | A × B| = 6 = |A| × |B|.
  • A × A = {</span>(1<span style="">,</span><span style=""> </span>1)<span style="">, </span>(1<span style="">, </span>2)<span style="">, </span>(1<span style="">, </span>3)<span style="">, </span>(2<span style="">, </span>1) <span style="">, </span>(2<span style="">, </span>2)<span style="">, </span>(2<span style="">, </span>3)<span style="">, </span>(3<span style="">, </span>1)<span style="">, </span>(3<span style="">, </span>2)<span style="">, </span>(3 <span style="">, </span>3) <span style="">}. 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 × A

A3 = A × A × 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.


Source: Al Doerr and Ken Levasseur, http://faculty.uml.edu/klevasseur/ads-latex/ads.pdf
Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 3.0 License.
Last modified: Monday, 10 August 2020, 2:32 PM