Skip to main content
\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Mathematics LibreTexts

1.3: Cartesian Products and Power Sets

  • Page ID
    80497
  • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)

     Cartesian Products

    Definition \(\PageIndex{1}\): Cartesian 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{.}\)

    Example \(\PageIndex{1}\): Cartesian Product

    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*}

    Power Sets

    Definition \(\PageIndex{2}\): Power 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{.}\)

    Example \(\PageIndex{2}\): Some Power Sets

    • \(\displaystyle \mathcal{P}(\emptyset )=\{\emptyset \}\)
    • \(\displaystyle \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.

    SageMath Note: Cartesian Products and Power Sets

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

    A=Set([0,1,2])
    B=Set(['a','b'])
    P=cartesian_product([A,B]);P
    

    Here is the cardinality of the cartesian product.

    P.cardinality()
    

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

    U=Set([0,1,2,3])
    subsets(U)
    

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

    for a in subsets(U):
        print(str(a)+ " has " +str(len(a))+" elements.")
    

    Exercises

    Exercise \(\PageIndex{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. \(\displaystyle A \times B\)
    2. \(\displaystyle B \times A\)
    3. \(\displaystyle A \times B\times C\)
    4. \(\displaystyle U \times \emptyset\)
    5. \(\displaystyle A \times A^c\)
    6. \(\displaystyle B^2\)
    7. \(\displaystyle B^3\)
    8. \(\displaystyle B\times \mathcal{P}(B)\)
    Answer
    1. \(\displaystyle \{(0, 2), (0, 3), (2, 2), (2, 3), (3, 2), (3, 3)\}\)
    2. \(\displaystyle \{(2, 0), (2, 2), (2, 3), (3, 0), (3, 2), (3, 3)\}\)
    3. \(\displaystyle \{(0, 2, 1), (0, 2, 4), (0, 3, 1), (0, 3, 4), (2, 2, 1), (2, 2, 4),\\ (2, 3, 1), (2, 3, 4), (3, 2, 1), (3, 2, 4), (3, 3, 1), (3, 3, 4)\}\)
    4. \(\displaystyle \emptyset\)
    5. \(\displaystyle \{(0, 1), (0, 4), (2, 1), (2, 4), (3, 1), (3, 4)\}\)
    6. \(\displaystyle \{(2, 2), (2, 3), (3, 2), (3, 3)\}\)
    7. \(\displaystyle \{(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)\}\)
    8. \(\displaystyle \{(2, \emptyset ), (2, \{2\}), (2, \{3\}), (2, \{2, 3\}), (3, \emptyset ), (3, \{2\}), (3, \{3\}), (3, \{2, 3\})\}\)

    Exercise \(\PageIndex{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{.}\)

    1. What is \(|A \times B|\text{?}\)
    2. How could you interpret the set \(A \times B\) ?

    Exercise \(\PageIndex{3}\)

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

    Answer

    \(\{a, b\}, \{a, c\}, \{a, d\}, \{b, c\}, \{b, d\} \textrm{ and } \{c, d\}\)

    Exercise \(\PageIndex{4}\)

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

    Exercise \(\PageIndex{5}\)

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

    Answer

    There are \(n\) singleton subsets, one for each element.

    Exercise \(\PageIndex{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?

    Exercise \(\PageIndex{7}\)

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

    1. List the elements of \(A \times B\)
    2. How many elements do \(A ^4\) and \((A \times B)^3\) have?
    Answer
    1. \(\displaystyle \{+00, +01, +10, +11, -00, -01, -10, -11\}\)
    2. \(\displaystyle 16 \textrm{ and } 512\)

    Exercise \(\PageIndex{8}\)

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

    1. 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.
    2. 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.

    Exercise \(\PageIndex{9}\)

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

    Answer

    They are equal when \(A=B\).


    1.3: Cartesian Products and Power Sets is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Al Doerr & Ken Levasseur.

    • Was this article helpful?