Tutorial: Sets and set operations

Go to Part A: Basics, unions, intersections, and complements

This tutorial: Part B: Cartesian products and sets of outcomes

(This topic is also in Section 6.1 in Finite Mathematics or Section 7.1 in Finite Mathematics and Applied Calculus)

Cartesian products

Suppose you are at the dealership buying a new motorcycle, and you are down to deciding on an engine capacity and a color. The set of of capacities you are considering is

$V=\{$ 250, 350, 650, 750 $\}$ (in cc). and the set of colors available is

$C = \{$ red, white, green $\}$. How can you represent the set of all motorcycle alternatives that result?

Here, choosing a motorcycle means choosing two elements: a capacity from the set $V$ and and a color fromthe set $C$. For instance, if you choose 250 from $V$ and green from $C$, you end up with a green 250 cc motorcycle. We can represent this particular choice mathematically as an ordered pair "(250, green)". The first element of the pair represents the first choice made (a capacity) and the second element represents the second choice made (a color).

If we go through all the possible alternatives, we get the following set of all the possible outcomes:

We displayed the elements in four rows for convenience.

We call this set the Cartesian product of the sets $V$ and $C$, and write it as $V \times C$. Thus,

$\displaystyle V \times C = \begin{Bmatrix}(250, \text{red}), & (250, \text{white}), & (250, \text{green),} \\ (350, \text{red}), & (350, \text{white}), & (350, \text{green}), \\ (650, \text{red}), & (650, \text{white}), & (650, \text{green}), \\ (750, \text{red}), & (750, \text{white}), & (750, \text{green}) \end{Bmatrix}$

Cartesian product
The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs $(a, b)$ with $a \in A$ and $b \in B$:

$A \times B = \{ (a, b) \mid a \in A \text{ and } b \in B \}$.

Examples

1. \t !2! %%Let $A = \{a,b\}$ %%and $B = \{1,2,3\}$, Then \\ \t !2!

$A \times B = \{(a,1),(a,2),(a,3),(b,1),(b,2),(b,3)\}$. \\ \\ \t #[Visualizing the cartesian product][Visualizando el producto cartesiano]#:
\t The elements of the cartesian product remind us of the way we represent points in the cartesian plane with two coordinates. Here, the "$x$-coordinate" is an element of $A$, and the "$y$-coordinate" is an element of $B$. So, we place the elements of $A$ along the $x$-axis and the elements of $B$ along the $y$-axis, and then look at the resulting coordinate grid, where each intersection point has coordinates that represent an element of $A \times B$. \\ \\ 2. \t %%If \\ \t \gap[40] $S = \{$%%H, %%T$\} \qquad$ \\ \t then \\ \t !2! \gap[40] $S \times S = \{$(%%H, %%H), (%%H, %%T), (%%T, %%H), (%%T, %%T)$\} \qquad$ \\ \\ 3. \t !3! Take R to be the set of all real numbers. Then \\ \\ \t !2! \gap[40] R × R $ = \{ (x, y) \mid x \text{ and } y $ real numbers $\}$, \\ \\ \t !3! which we recognize as a representation of the cartesian plane

Some for you

Sets of outcomes

We are often interested in the outcome of some kind of activity or "experiment". For instance:

Toss a coin and observe which side faces up: There are two possible outcomes: %%heads (%%H) or %%tails (%%T), so the set of possible outcomes can be written as $S = \{\text{H},\text{T}\}$.
Cast a die and observe the number facing up. We can represent the set of the six oucomes as $S = \{1, 2, 3, 4, 5, 6\}$.

Suppose, for instance, that our experiment consists of a sequence of two steps, such as tossing a coin or rolling a dice twice in succession. In such cases, the outcomes will be pairs of outcomes of the individual steps. For instance, if we toss a coin twice in succession, we might get %%heads followed by %%tails, which we can represent as (H, T), or two heads in a row, presented by (%%H, %%H). Notice that these outcomes are just elements of the cartesian product $\{$%%H, %%T$\} \times \{$%%H, %%T$\}$.

Cartesian products and multi-step experiments
If an experiment consists of two steps with individual sets of outcomes $A$ for the first step and $B$ for the second, then the set of outcomes for the two-step experiment is $A \times B$.

Similarly, if an experiment consists of three steps with individual sets of outcomes $A, B$ and $C$ respectively for the individual steps, then the set of outcomes for the three-step experiment is $A \times B \times C$, the set of triples $(a,b,c)$ with $a \in A, b \in B$, and $c \in C$:

$A \times B \times C = \{(a,b,c) \mid a \in A, b \in B, c \in C \}$. We can generalize this observation to any number of steps, as you will see in the #[decisions algorithms tutorial][tutorial sobre algoritmos de decisión]#.

Examples

\\ 1. \t %%If \\ \t \gap[40] $S = \{$%%H, %%T$\} \qquad$ \\ \t !r! #[The set of outcomes of tossing a coin once][El conjunto de resultados al lanzar una moneda una vez]# \\ \t then \\ \t !2! \gap[40] $S \times S = \{$(%%H, %%H), (%%H, %%T), (%%T, %%H), (%%T, %%T)$\} \qquad$ \\ \t !r! #[The set of outcomes of tossing a coin twice][El conjunto de resultados al lanzar una moneda dos veces]# \\ \\ 2. \t %%If \\ \t \gap[40] $S = \{1, 2, 3, 4, 5, 6\} \qquad$ \\ \t !r! #[The set of outcomes of rolling a die once][El conjunto de resultados al tirar un dado una vez]# \\ \t then \\ \t !2! \gap[40] \t \\ \t !r! The set of outcomes of rolling a die twice \\ \t !3! Thus, for example, the outcome $(2, 3)$ represents a 2 followed by a 3 when you cast a die twice. \\ \\ 3. \t Look again at the example of buying a motorcycle at the beginning of this tutorial. \\ \t The decision as to which motorcycle to choose can be thought of as a two-step experiment:

Choose a capacity from the set $V=\{$ 250, 350, 650, 750 $\}$.
Choose a color from the set $C = \{$ red, white, green $\}$.

The set of outcomes is therefore

which is exactly the set we arrived at in the discussion above. S

Some for you

Distinguishable and indistinguishable dice

We saw above that the set of outcomes when we throw a dice twice can be represented by a cartesian product

$\displaystyle \{1, 2, 3, 4, 5, 6\} \times \{1, 2, 3, 4, 5, 6\} = \begin{Bmatrix} (1,1), & (1,2), & (1,3), & (1,4), & (1,5), & (1,6), \\ (2,1), & (2,2), & (2,3), & (2,4), & (2,5), & (2,6), \\ (3,1), & (3,2), & (3,3), & (3,4), & (3,5), & (3,6), \\ (4,1), & (4,2), & (4,3), & (4,4), & (4,5), & (4,6), \\ (5,1), & (5,2), & (5,3), & (5,4), & (5,5), & (5,6), \\ (6,1), & (6,2), & (6,3), & (6,4), & (6,5), & (6,6) \end{Bmatrix}$. We get the same set of outcomes if we throw the two dice simultaneously but distinguish them in some way; for instance if one is red and the other is green, then we can think of the first coordinate as the result of the red die and the second as the result of the green die. So, for instance, the outcome $(3, 2)$ would indicate that the red die shows a 3 and the green die shows a 2 while $(2, 3)$ would indicate the red die showing a 2 and the green die showing a 3.

However, what if the two dice were identical and we placed them in a closed box and then shook the box. When we look inside afterward, there is no way to tell which die is which. (If we make a small marking on one of the dice or somehow keep track of it as it bounces around, we are distinguishing the dice.) We regard two dice as indistinguishable if we make no attempt to distinguish them. Thus, for example, the two different outcomes $(2,3)$ and $(3,2)$ would represent the same outcome (one die shows a 2 and the other a 3). Because the set of outcomes should contain each outcome only once, we can remove $(3,2)$. Following this approach gives the following smaller set of outcomes:

Set of outcomes for a pair of indistinguishable dice $\displaystyle = \begin{Bmatrix} (1,1), & (1,2), & (1,3), & (1,4), & (1,5), & (1,6), \\ \ & (2,2), & (2,3), & (2,4), & (2,5), & (2,6), \\ \ & \ & (3,3), & (3,4), & (3,5), & (3,6), \\ \ & \ & \ & (4,4), & (4,5), & (4,6), \\ \ & \ & \ & \ & (5,5), & (5,6), \\ \ & \ & \ & \ & \ & (6,6) \end{Bmatrix}$. Similarly, the set of outcomes for a pair of indistinguishable coins would be

#[We eliminated (%%T, %%H), as it is the same as (%%H, %%T).][Eliminaos (%%T, %%H), ya que es lo mismo que (%%H, %%T).]#

Now try the exercises in Section 6.1 in Finite Mathematics or Section 7.1 in Finite Mathematics and Applied Calculus.