ads Cartesian Products and Power Sets

Section 1.3 Cartesian Products and Power Sets

Subsection 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 \times B,

is defined as follows:

A \times B = {(a, b) ∣ a \in A and b \in B},

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 .

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

\times

is used for Cartesian products.

Let $A = {1, 2, 3}$ and $B = {4, 5} .$ Then $A \times B = {(1, 4), (1, 5), (2, 4), (2, 5), (3, 4), (3, 5)} .$ Note that $| A \times B | = 6 = | A | \times | B | .$
$A \times A = {(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)} .$ Note that $| A \times A | = 9 = {| A |}^{2} .$

🔗

These two examples illustrate the general rule that if

A

and

B

are finite sets, then

| A \times B | = | A | \times | B | .

🔗

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

🔗

It is common to use exponents if the sets in a Cartesian product are the same:

A^{2} = A \times A

A^{3} = A \times A \times A

🔗

and in general,

A^{n} = \underset{n factors}{\underset{―}{A \times A \times \dots \times A}} .

🔗

Subsection 1.3.2 Power Sets

🔗

Definition 1.3.3. Power Set.

🔗

A

is any set, the power set of

A

is the set of all subsets of

A,

denoted

P (A) .

🔗

The two extreme cases, the empty set and all of

A,

are both included in

P (A) .

Example 1.3.4. Some Power Sets.

$P (\emptyset) = {\emptyset}$
$P ({1}) = {\emptyset, {1}}$
$P ({1, 2}) = {\emptyset, {1}, {2}, {1, 2}} .$

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.

🔗

Subsection 1.3.3 SageMath Note: Cartesian Products and Power Sets

🔗

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

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

🔗

Here is the cardinality of the cartesian product.

xxxxxxxxxx
 
P.cardinality()

🔗

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

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

🔗

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

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

🔗

Exercises 1.3.4 Exercises

🔗

1.

🔗

Let

A = {0, 2, 3},

B = {2, 3},

C = {1, 4},

and let the universal set be

U = {0, 1, 2, 3, 4} .

List the elements of

🔗

$A \times B$
$B \times A$
$A \times B \times C$
$U \times \emptyset$
$A \times A^{c}$
$B^{2}$
$B^{3}$
$B \times P (B)$

Answer.

${(0, 2), (0, 3), (2, 2), (2, 3), (3, 2), (3, 3)}$
${(2, 0), (2, 2), (2, 3), (3, 0), (3, 2), (3, 3)}$
${(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)}$
$\emptyset$
${(0, 1), (0, 4), (2, 1), (2, 4), (3, 1), (3, 4)}$
${(2, 2), (2, 3), (3, 2), (3, 3)}$
${(2, 2, 2), (2, 2, 3), (2, 3, 2), (2, 3, 3), (3, 2, 2), (3, 2, 3), (3, 3, 2), (3, 3, 3)}$
${(2, \emptyset), (2, {2}), (2, {3}), (2, {2, 3}), (3, \emptyset), (3, {2}), (3, {3}), (3, {2, 3})}$

🔗

2.

🔗

Suppose that you are about to flip a coin and then roll a die. Let

A = {H E A D S, T A I L S}

and

B = {1, 2, 3, 4, 5, 6} .

🔗

What is $| A \times B | ?$
How could you interpret the set $A \times B$ ?

🔗

3.

🔗

List all two-element sets in

P ({a, b, c, d})

Answer.

{a, b}, {a, c}, {a, d}, {b, c}, {b, d} and {c, d}

🔗

4.

🔗

List all three-element sets in

P ({a, b, c, d}) .

🔗

5.

🔗

How many singleton (one-element) sets are there in

P (A)

| A | = n

Answer.

There are

n

singleton subsets, one for each element.

🔗

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

🔗

List the elements of $A \times B$
How many elements do $A^{4}$ and $(A \times B)^{3}$ have?

Answer.

${+ 00, + 01, + 10, + 11, - 00, - 01, - 10, - 11}$
$16 and 512$

🔗

8.

🔗

Let

A = {∙, ◻, \otimes}

and

B = {◻, ⊖, ∙} .

🔗

List the elements of $A \times B$ and $B \times A .$ 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,$ 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.

They are equal when

A = B .

You have attempted 1 of 1 activities on this page.

Prev Top Next