Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section1.3Cartesian Products and Power Sets

Subsection1.3.1Cartesian Products

Definition1.3.1Cartesian Product

Let \(A\) and \(B\) be sets. The Cartesian product of \(A\) and \(B\text{,}\) denoted by \(A\times B\text{,}\) is defined as follows: \(A\times B = \{(a, b) \mid a \in A \quad\textrm{ and }\quad b \in B\}\text{,}\) that is, \(A\times B\) is the set of all possible ordered pairs whose first component comes from \(A\) and whose second component comes from \(B\text{.}\)

Example1.3.2Some Cartesian Products

Notation in mathematics is often developed for good reason. In this case, a few examples will make clear why the symbol $\times $ is used for Cartesian products.

  • Let \(A = \{1, 2, 3\}\) and \(B = \{4, 5\}\text{.}\) Then \(A \times B = \{(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)\}\text{.}\) Note that \(|A \times B| = 6 = \lvert A \rvert \times \lvert B \rvert \text{.}\)

  • \(A \times A = \{(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)\}\text{.}\) Note that \(|A \times A| = 9 = {\lvert A \rvert}^2\text{.}\)

These two examples illustrate the general rule that if \(A\) and \(B\) are finite sets, then \(\lvert A \times B \rvert = \lvert A \rvert \times \lvert B \rvert \text{.}\)

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

It is common to use exponents if the sets in a Cartesian product are the same: \begin{equation*} A^2= A \times A \end{equation*} \begin{equation*} A^3=A \times A \times A \end{equation*} and in general, \begin{equation*} A^n = \underset{n \textrm{ factors}}{\underline{A \times A \times \ldots \times A}}\text{.} \end{equation*}

Subsection1.3.2Power Sets

Definition1.3.3Power Set

If \(A\) is any set, the power set of \(A\) is the set of all subsets of \(A\text{,}\) denoted \(\mathcal{P}(A)\text{.}\)

The two extreme cases, the empty set and all of \(A\text{,}\) are both included in \(\mathcal{P}(A)\text{.}\)

Example1.3.4Some Power Sets

  • \(\mathcal{P}(\emptyset )=\{\emptyset \}\)

  • \(\mathcal{P}(\{1\}) = \{\emptyset , \{1\}\}\)

  • \(\mathcal{P}(\{1,2\}) = \{\emptyset , \{1\}, \{2\}, \{1, 2\}\}\text{.}\)

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. In Chapter 2, we will discuss counting rules that will help us derive this formula.

Subsection1.3.3Sage Note: Cartesian Products and Power Sets

Here is a simple example of a cartesian product of two sets:

Here is the cardinality of the cartesian product.

The power set of a set is an iterable, as you can see from the output of this next cell

You can iterate over a powerset. Here is a trivial example.

Subsection1.3.4EXERCISES FOR SECTION 1.3

1

Let \(A = \{0, 2, 3\}\text{,}\) \(B = \{2, 3\}\text{,}\) \(C = \{1, 4\}\text{,}\) and let the universal set be \(U = \{0, 1, 2, 3, 4\}\text{.}\) List the elements of

  1. \(A \times B\)

  2. \(B \times A\)

  3. \(A \times B\times C\)

  4. \(U \times \emptyset\)

  5. \(A \times A^c\)

  6. \(B^2\)

  7. \(B^3\)

  8. \(B\times \mathcal{P}(B)\)

Answer
2

Suppose that you are about to flip a coin and then roll a die. Let \(A = \{HEADS, TAILS\}\) and \(B = \{1, 2, 3, 4, 5, 6\}\text{.}\)

  • What is \(|A \times B|\text{?}\)

  • How could you interpret the set \(A \times B\) ?

3

List all two-element sets in \(\mathcal{P}(\{a,b,c,d\})\)

Answer
4

List all three-element sets in \(\mathcal{P}(\{a, b, c,d\})\text{.}\)

5

How many singleton (one-element) sets are there in \(\mathcal{P}(A)\) if \(\lvert A \rvert =n\) ?

Answer
6

A person has four coins in his pocket: a penny, a nickel, a dime, and a quarter. How many different sums of money can he take out if he removes 3 coins at a time?

7

Let \(A = \{+,-\}\) and \(B = \{00, 01, 10, 11\}\text{.}\)

  • List the elements of \(A \times B\)

  • How many elements do \(A ^4\) and \((A \times B)^3\) have?

Answer
8

Let \(A = \{\bullet,\square ,\otimes \}\) and \(B = \{\square ,\ominus ,\bullet\}\text{.}\)

  • List the elements of \(A \times B\) and \(B \times A\text{.}\) The parentheses and comma in an ordered pair are not necessary in cases such as this where the elements of each set are individual symbols.

  • Identify the intersection of \(A \times B\) and \(B \times A\) for the case above, and then guess at a general rule for the intersection of \(A \times B\) and \(B \times A\text{,}\) where \(A\) and \(B\) are any two sets.

9

Let \(A\) and \(B\) be nonempty sets. When are \(A \times B\) and \(B \times A\) equal?

Answer