1.4 Set Theory

Overview¶

This section develops the formal mathematical model for events, namely, the theory of sets. Several important concepts are introduced, namely, element, subset, empty set, intersection, union, complement, and disjoint sets.

1.4.1 The Sample Space¶

The sample space of an experiment can be thought of as a set, or collection, of different possible outcomes; and each outcome can be thought of as a point, or an element, in the sample space. Similarly, events can be thought of as subsets of the sample space.

Because we can interpret outcomes as elements of a set and events as subsets of a set, the language and concepts of set theory provide a natural context for the development of probability theory. The basic ideas and notation of set theory will now be reviewed.

1.4.2 Relations of Set Theory¶

Let $S$ denote the sample space of some experiment. Then each possible outcome $s$ of the experiment is said to be a member of the space $S$, or to belong to the space $S$. The statement that s is a member of $S$ is denoted symbolically by the relation $s \in S$.

When an experiment has been performed and we say that some event $E$ has occurred, we mean two equivalent things. One is that the outcome of the experiment satisfied the conditions that specified that event $E$. The other is that the outcome, considered as a point in the sample space, is an element of $E$.

To be precise, we should say which sets of outcomes correspond to events as defined above. In many applications, such as Example 1.4.1, it will be clear which sets of outcomes should correspond to events. In other applications (such as Example 1.4.5 coming up later), there are too many sets available to have them all be events. Ideally, we would like to have the largest possible collection of sets called events so that we have the broadest possible applicability of our probability calculations. However, when the sample space is too large (as in Example 1.4.5) the theory of probability simply will not extend to the collection of all subsets of the sample space.We would prefer not to dwell on this point for two reasons. First, a careful handling requires mathematical details that interfere with an initial understanding of the important concepts, and second, the practical implications for the results in this text are minimal.

In order to be mathematically correct without imposing an undue burden on the reader, we note the following. In order to be able to do all of the probability calculations that we might find interesting, there are three simple conditions that must be met by the collection of sets that we call events. In every problem that we see in this text, there exists a collection of sets that includes all the sets that we will need to discuss and that satisfies the three conditions, and the reader should assume that such a collection has been chosen as the events. For a sample space $S$ with only finitely many outcomes, the collection of all subsets of S satisfies the conditions, as the reader can show in Div in this section.

The first of the three conditions can be stated immediately.

That is, we must include the sample space $S$ in our collection of events. The other two conditions will appear later in this section because they require additional definitions.

For events, to say that $A \subset B$ means that if $A$ occurs then so does $B$.

The proof of the following result is straightforward and is omitted.

The Empty Set: Some events are impossible. For example, when a die is rolled, it is impossible to obtain a negative number. Hence, the event that a negative number will be obtained is defined by the subset of $S$ that contains no outcomes.

In terms of events, the empty set is any event that cannot occur.

Finite and Infinite Sets: Some sets contain only finitely many elements, while others have infinitely many elements. There are two sizes of infinite sets that we need to distinguish.

Examples of countably infinite sets include the integers, the even integers, the odd integers, the prime numbers, and any infinite sequence. Each of these can be put in one-to-one correspondence with the natural numbers. For example, the following function $f$ puts the integers in one-to-one correspondence with the natural numbers:

Every infinite sequence of distinct items is a countable set, as its indexing puts it in one-to-one correspondence with the natural numbers. Examples of uncountable sets include the real numbers, the positive reals, the numbers in the interval $[0, 1]$, and the set of all ordered pairs of real numbers. An argument to show that the real numbers are uncountable appears at the end of this section. Every subset of the integers has at most countably many elements.

1.4.3 Operations of Set Theory¶

In terms of events, the event $A^c$ is the event that $A$ does not occur.

We can now state the second condition that we require of the collection of events.

That is, for each set $A$ of outcomes that we call an event, we must also call its complement $A^c$ an event.

A generic version of the relationship between $A$ and $A^c$ is sketched in Figure 1.1.

A sketch of this type is called a Venn diagram.

Some properties of the complement are stated without proof in the next result.

The set $A \cup B$ is sketched in Figure 1.2. In terms of events, $A \cup B$ is the event that either $A$ or $B$ or both occur.

The union has the following properties whose proofs are left to the reader.

The concept of union extends to more than two sets.

Similarly, the union of an infinite sequence of sets $A_1, A_2, \ldots$ is the set that contains all outcomes that belong to at least one of the events in the sequence. The infinite union is denoted by $\bigcup_{i=1}^{\infty}A_i$.

In terms of events, the union of a collection of events is the event that at least one of the events in the collection occurs.

We can now state the final condition that we require for the collection of sets that we call events.

In other words, if we choose to call each set of outcomes in some countable collection an event, we are required to call their union an event also. We do not require that the union of an arbitrary collection of events be an event. To be clear, let $I$ be an arbitrary set that we use to index a general collection of events $\{A_i : i \in I \}$. The union of the events in this collection is the set of outcomes that are in at least one of the events in the collection. The notation for this union is $\bigcup_{i \in I}A_i$. We do not require that $\bigcup_{i \in I}A_i$ be an event unless $I$ is countable.

Condition 3 refers to a countable collection of events. We can prove that the condition also applies to every finite collection of events.

The union of three events $A$, $B$, and $C$ can be constructed either directly from the definition of $A \cup B \cup C$ or by first evaluating the union of any two of the events and then forming the union of this combination of events and the third event. In other words, the following result is true.

The set $A \cap B$ is sketched in a Venn diagram in Figure 1.3. In terms of events, $A \cap B$ is the event that both $A$ and $B$ occur.

The proof of the first part of the next result follows from Example 1 in this section. The rest of the proof is straightforward.

The concept of intersection extends to more than two sets.

In terms of events, the intersection of a collection of events is the event that every event in the collection occurs.

The following result concerning the intersection of three events is straightforward to prove.

::: {.callout-tip}
::: {#def-1-4-10}

## Definition 1.4.10: Disjoint/Mutually Exclusive

It is said that two sets A and B are disjoint, or mutually
exclusive, if A and B have no outcomes in common, that is, if A ∩ B = ∅. The sets
A1, . . . , An or the sets A1, A2, . . . are disjoint if for every i  = j , we have that Ai and
Aj are disjoint, that is, Ai
∩ Aj
=∅ for all i  = j . The events in an arbitrary collection
are disjoint if no two events in the collection have any outcomes in common.

In terms of events, $A$ and $B$ are disjoint if they cannot both occur.

As an illustration of these concepts, a Venn diagram for three events $A_1$, $A_2$, and $A_3$ is presented in @fig-1-4. This diagram indicates that the various intersections of $A_1$, $A_2$, and $A_3$ and their complements will partition the sample space $S$ into eight disjoint subsets.

```{figure} images/fig-1-4.svg
:label: fig-1-4
:enumerator: 1.4
:align: center
:width: 50%

Partition of $S$ determined by three events $A_1$, $A_2$, $A_3$
```

:::: {prf:example} Tossing a Coin
:label: exm-1-4-4
:enumerator: 1.4.4

Suppose that a coin is tossed three times. Then the sample space $S$ contains the following eight possible outcomes $s_1, \ldots, s_8$:

s1: HHH,
s2: THH,
s3: HTH,
s4: HHT,
s5: HTT,
s6: THT,
s7: TTH,
s8: TTT.
In this notation, H indicates a head and T indicates a tail. The outcome s3, for
example, is the outcome in which a head is obtained on the first toss, a tail is obtained
on the second toss, and a head is obtained on the third toss.
To apply the concepts introduced in this section, we shall define four events as
follows: Let A be the event that at least one head is obtained in the three tosses; let
B be the event that a head is obtained on the second toss; let C be the event that a
tail is obtained on the third toss; and let D be the event that no heads are obtained.
Accordingly,
A = {s1, s2, s3, s4, s5, s6, s7},
B = {s1, s2, s4, s6},
C = {s4, s5, s6, s8},
D = {s8}.
Various relations among these events can be derived. Some of these relations
are B ⊂ A, Ac = D, B ∩ D = ∅, A ∪ C = S, B ∩ C = {s4, s6}, (B ∪ C)c = {s3, s7}, and
A ∩ (B ∪ C) = {s1, s2, s4, s5, s6}.  

{#fig-1-6 width=“50%”}

Additional Properties of Sets¶

The proof of the following useful result is left to Div in this section.

The generalization of Theorem 1.4.9 is the subject of Div in this section.

The proofs of the following distributive properties are left to Div in this section. These properties also extend in natural ways to larger collections of events.

The following result is useful for computing probabilities of events that can be partitioned into smaller pieces. Its proof is left to Div in this section, and is illuminated by fig-1-6.

## Proof That the Real Numbers Are Uncountable

We shall show that the real numbers in the interval $[0, 1)$ are uncountable. Every larger set is a fortiori uncountable. For each number $x \in [0, 1)$, define the sequence $\{a_n(x)\}_{n=1}^{\infty}$ as follows. First, $a_1(x) = \lfloor{}10x \rfloor$, where $\lfloor y \rfloor$ stands for the greatest integer less than or equal to $y$ (round non-integers down to the closest integer below). Then set $b_1(x) = 10x − a_1(x)$, which will again be in $[0, 1)$. For $n > 1$, $a_n(x) = \lfloor{}10b_{n−1}(x)\rfloor{}$ and $b_n(x) = 10b_{n−1}(x) − a_n(x)$. It is easy to see that the sequence $\{a_n(x)\}_{n=1}^{\infty}$ gives a
decimal expansion for $x$ in the form

$$
x = \sum_{n=1}^{\infty}a_n(x)10^{-n}.
$$ {#eq-1-4-1}

By construction, each number of the form $x = k/10^m$ for some nonnegative integers $k$ and $m$ will have $a_n(x) = 0$ for $n > m$. The numbers of the form $k/10^m$ are the only ones that have an alternate decimal expansion $x = \sum_{n=1}^{\infty}c_n(x)10^{-n}$. When $k$ is not a multiple of 10, this alternate expansion satisfies $c_n(x) = a_n(x)$ for $n = 1, \ldots, m-1$, $c_m(x) = a_m(x) − 1$, and $c_n(x) = 9$ for $n > m$. Let $C = \{0, 1, \ldots, 9\}^{\infty}$ stand for the set of all infinite sequences of digits. Let $B$ denote the subset of $C$ consisting of those sequences that don’t end in repeating 9's. Then we have just constructed a function a from the interval $[0, 1)$ onto $B$ that is one-to-one and whose inverse is given in @eq-1-4-1. We now show that the set $B$ is uncountable, hence $[0, 1)$ is uncountable. Take any countable subset of $B$ and arrange the sequences into a rectangular array with the $k$th sequence running across the $k$th row of the array for $k = 1, 2, \ldots$. @fig-1-7 gives an example of part of such an array.

In @fig-1-7, we have underlined the $k$th digit in the $k$th sequence for each $k$. This portion of the array is called the **diagonal** of the array. We now show that there must exist a sequence in $B$ that is not part of this array. This will prove that the whole set $B$ cannot be put into such an array, and hence cannot be countable. Construct the sequence $\{d_n\}_{n=1}^{\infty}$ as follows. For each $n$, let $d_n = 2$ if the $n$th digit in the $n$th sequence is 1, and $d_n = 1$ otherwise. This sequence does not end in repeating 9's; hence, it is in $B$. We conclude the proof by showing that $\{d_n\}_{n=1}^{\infty}$ does not appear anywhere in the array. If the sequence did appear in the array, say, in the $k$th row, then its $k$th element would be the $k$th diagonal element of the array. But we constructed the sequence so that for every $n$ (including $n = k$), its $n$th element never matched the $n$th diagonal element. Hence, the sequence can't be in the $k$th row, no matter what $k$ is. The argument given here is essentially that of the nineteenth-century German
mathematician Georg Cantor.

::: {#fig-1-7}

$$
\begin{matrix}
\underline{0} & 2 & 3 & 0 & 7 & 1 & 3 & \cdots \\
1 & \underline{9} & 9 & 2 & 1 & 0 & 0 & \cdots \\
2 & 7 & \underline{3} & 6 & 0 & 1 & 1 & \cdots \\
8 & 0 & 2 & \underline{1} & 2 & 7 & 9 & \cdots \\ 
7 & 0 & 1 & 6 & \underline{0} & 1 & 3 & \cdots \\
1 & 5 & 1 & 5 & 1 & \underline{5} & 1 & \cdots \\
2 & 3 & 4 & 5 & 6 & 7 & \underline{8} & \cdots \\
% 0 & 1 & 7 & 3 & 2 & 9 & 8 & \cdots \\
\vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \vdots & \ddots \\
\end{matrix}
$$

An array of a countable collection of sequences of digits with the diagonal underlined.

1.4.4 Summary¶

We will use set theory for the mathematical model of events. Outcomes of an experiment are elements of some sample space $S$, and each event is a subset of $S$. Two events both occur if the outcome is in the intersection of the two sets. At least one of a collection of events occurs if the outcome is in the union of the sets. Two events cannot both occur if the sets are disjoint. An event fails to occur if the outcome is in the complement of the set. The empty set stands for every event that cannot possibly occur. The collection of events is assumed to contain the sample space, the complement of each event, and the union of each countable collection of events.

1.4.5 Exercises¶