Set theory is the foundation of probability and statistics, as it is for almost every branch of mathematics.

Sets and subsets

In this text, sets and their elements are primitive, self-evident concepts, an approach that is sometimes referred to as naive set theory.

Our next definition is the subset relation, another very basic concept.

Concepts in set theory are often illustrated with small, schematic sketches known as Venn diagrams, named for John Venn. The Venn diagram in the picture below illustrates the subset relation.

As noted earlier, membership is a primitive, undefined concept in naive set theory. However, the following construction, known as Russell's paradox, after the mathematician and philosopher Bertrand Russell, shows that we cannot be too cavalier in the construction of sets.

Usually, the sets under discussion in a particular context are all subsets of a well-defined, specified set \(S\), often called a universal set. The use of a universal set prevents the type of problem that arises in Russell's paradox. That is, if \(S\) is a given set and \(p(x)\) is a predicate on \(S\) (that is, a valid mathematical statement that is either true or false for each \(x \in S\)), then \(\{x \in S: p(x)\}\) is a valid subset of \(S\). Defining a set in this way is known as predicate form. The other basic way to define a set is simply be listing its elements; this method is known as list form.

In contrast to a universal set, the empty set, denoted \(\emptyset\), is the set with no elements.

One step up from the empty set is a set with just one element. Such a set is called a singleton set. The subset relation is a partial order on the collection of subsets of \(S\):

Here are a couple of variations on the subset relation.

The collection of all subsets of a given set frequently plays an important role, particularly when the given set is a universal set.

Special Sets

The following special sets are used throughout this text. Defining them will also give us practice using list and predicate form.

Note that \( \N_+ \subset \N \subset \Z \subset \Q \subset \A \subset \R \). We will also occasionally need the set of complex numbers \(\C = \{x + i y: x, \, y \in \R\}\) where \( i \) is the imaginary unit, defined by \(i^2 = - 1\). The following special rational numbers turn out to be useful for various constructions.

Note that \( \D_0 = \Z \) and \( \D_n \subset \D_{n+1} \) for \( n \in \N \), and of course, \( \D \subset \Q \). We use the usual notation for intervals of real numbers, but again the definitions provide practice with predicate notation.

The terms open and closed are actually concepts from topology.

You may recall that \( x \in \R \) is rational if and only if the decimal expansion of \( x \) either terminates or forms a repeating block. The binary rationals have simple binary expansions (that is, expansions in the base 2 number system).

Set Operations

We are now ready to review the basic operations of set theory. For the following definitions, suppose that \(A\) and \(B\) are subsets of a universal set, which we will denote by \(S\).

Sometimes (particularly in older works and particularly when \( A \subseteq B \)), the notation \( B - A \) is used instead of \( B \setminus A \). When \( A \subseteq B \), \( B - A \) is known as proper set difference.

Note that \(A^c\) would make no sense without the assumption of the universal set \(S\) in the background. Note also that union, intersection, and difference are binary set operations, while complement is a unary set operation.

Basic Rules

In the following theorems, \(A\), \(B\), and \(C\) are subsets of a universal set \(S\). The proofs are straightforward, and just use the definitions and basic logic. Try the proofs yourself before reading the ones in the text.

So the empty set acts as an identity relative to the union operation, and the universal set acts as an identiy relative to the intersection operation.

Thus, we can write \(A \cup B \cup C\) without ambiguity. Note that \( x \) is an element of this set if and only if \( x \) is an element of at least one of the three given sets. Similarly, we can write \(A \cap B \cap C\) without ambiguity. Note that \( x \) is an element of this set if and only if \( x \) is an element of all three of the given sets.

So intersection distributes over union, and union distributes over intersection. It's interesting to compare the distributive properties of set theory with those of the real number system. If \(x, \, y, \, z \in \R\), then \(x (y + z) = (x y) + (x z)\), so multiplication distributes over addition, but it is not true that \(x + (y z) = (x + y)(x + z)\), so addition does not distribute over multiplication. The following results are particularly important in probability theory.

The following result explores the connections between the subset relation and the set operations.

In addition to the special sets in , we also have the following:

Since \( \Q \subset \A \subset \R\) it follows that \( \R \setminus \A \subset \R \setminus \Q \), that is, every transcendental number is also irrational.

Set difference can be expressed in terms of complement and intersection. All of the other set operations (complement, union, and intersection) can be expressed in terms of difference.

So in principle, we could do all of set theory using the one operation of set difference. But as (c) and (d) suggest, the results would be hideous.

The set in is called the symmetric difference of \(A\) and \(B\), and is sometimes denoted \(A \bigtriangleup B\). The elements of this set belong to one but not both of the given sets. Thus, the symmetric difference corresponds to exclusive or in the same way that union corresponds to inclusive or. That is, \( x \in A \cup B \) if and only if \( x \in A \) or \( x \in B \) (or both); \( x \in A \bigtriangleup B \) if and only if \( x \in A \) or \( x \in B \), but not both. On the other hand, the complement of the symmetric difference consists of the elements that belong to both or neither of the given sets:

General Operations

The operations of union and intersection can easily be extended to a finite or even an infinite collection of sets.

Definitions

Suppose that \(\ms A\) is a nonempty collection of subsets of a universal set \(S\). In some cases, the subsets in \(\ms A\) may be naturally indexed by a nonempty index set \(I\), so that \(\ms A = \{A_i: i \in I\}\). (In a technical sense, any collection of subsets can be indexed.)

If \(\ms A = \{A_i: i \in I\} \), so that the collection of sets is indexed, then we use the more natural notation: \[ \bigcup_{i \in I} A_i =\{x \in S: x \in A_i \text{ for some } i \in I\} \]

If \(\ms A = \{A_i : i \in I\}\), so that the collection of sets is indexed, then we use the more natural notation: \[ \bigcap_{i \in I} A_i = \{x \in S: x \in A_i \text{ for all } i \in I\} \] Often the index set is an integer interval of \( \N \). In such cases, an even more natural notation is to use the upper and lower limits of the index set. For example, if the collection is \( \{A_i: i \in \N_+\} \) then we would write \( \bigcup_{i=1}^\infty A_i \) for the union and \( \bigcap_{i=1}^\infty A_i \) for the intersection. Similarly, if the collection is \( \{A_i: i \in \{1, 2, \ldots, n\}\} \) for some \( n \in \N_+ \), we would write \( \bigcup_{i=1}^n A_i \) for the union and \( \bigcap_{i=1}^n A_i \) for the intersection.

Partitions are intimately related to equivalence relations. As an example, for \( n \in \N \), the set \[ \ms{D}_n = \left\{\left[\frac{j}{2^n}, \frac{j + 1}{2^n}\right): j \in \Z\right\} \] is a partition of \( \R \) into intervals of equal length \(1 / 2^n\). Note that the endpoints are the dyadic rationals in of rank \( n \) or less as defined in , and that \( \ms{D}_{n+1} \) can be obtained from \( \ms{D}_n \) by dividing each interval into two equal parts. This sequence of partitions is one of the reasons that the dyadic rationals are important.

Basic Rules

In the following problems, \(\ms A = \{A_i : i \in I\}\) is a collection of subsets of a universal set \(S\), indexed by a nonempty set \(I\), and \(B\) is a subset of \(S\).

The sets in turn out to be important in the study of probability.

Product sets

Definitions

Product sets are sets of sequences. The defining property of a sequence, of course, is that order as well as membership is important. Let us start with ordered pairs. In this case, the defining property is that \((a, b) = (c, d)\) if and only if \(a = c\) and \(b = d\). Interestingly, the structure of an ordered pair can be defined just using set theory. The construction in is due to Kazimierz Kuratowski

Of course, it's important not to confuse the ordered pair \( (a, b) \) with the open interval \( (a, b) \), since the same notation is used for both. Usually it's clear form context which type of object is referred to. For ordered triples, the defining property is \( (a, b, c) = (d, e, f) \) if and only if \( a = d \), \( b = e \), and \( c = f \). Ordered triples can be defined in terms of ordered pairs, which via , uses only set theory.

All of this is just to show how complicated structures can be built from simpler ones, and ultimately from set theory. But enough of that! More generally, two ordered sequences of the same size (finite or infinite) are the same if and only if their corresponding coordinates agree. Thus for \( n \in \N_+ \), the definition for \( n \)-tuples is \( (x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_n) \) if and only if \( x_i = y_i\) for all \( i \in \{1, 2, \ldots, n\} \). For infinite sequences, \((x_1, x_2, \ldots) = (y_1, y_2, \ldots) \) if and only if \( x_i = y_i \) for all \( i \in \N_+ \).

Cartesian products are named for René Descartes. If \(S_i = S\) for each \(i\), then the Cartesian product set can be written compactly as \(S^n\), a Cartesian power. In particular, recall that \(\R\) denotes the set of real numbers so that \(\R^n\) the Euclidean set of order \(n\), named after Euclid, of course. The elements of \(\{0, 1\}^n\) are called bit strings of length \(n\). As the name suggests, we sometimes represent elements of this product set as strings rather than sequences (that is, we omit the parentheses and commas). Since the coordinates just take two values, there is no risk of confusion.

When \( S_i = S \) for \( i \in \N_+ \), the Cartesian product set is sometimes written as a Cartesian power as \( S^\infty \) or as \( S^{\N_+} \). An explanation for the last notation, as well as a much more general construction can be given in terms of functions. Also, notation similar to that of general union and intersection is often used for Cartesian product, with \( \prod \) as the operator. So \[ \prod_{i=1}^n S_i = S_1 \times S_2 \times \cdots \times S_n, \quad \prod_{i=1}^\infty S_i = S_1 \times S_2 \times \cdots \]

Rules for Product Sets

We will now see how the set operations relate to the Cartesian product operation. Suppose that \(S\) and \(T\) are sets and that \(A \subseteq S\), \(B \subseteq S\) and \(C \subseteq T\), \(D \subseteq T\). The sets in this subsection are subsets of \(S \times T\).

The most important rules that relate Cartesian product with union, intersection, and difference are the distributive rules:

In general, the product of unions is larger than the corresponding union of products.

So in particular it follows that \((A \times C) \cup (B \times D) \subseteq (A \cup B) \times (C \cup D)\). On the other hand, the product of intersections is the same as the corresponding intersection of products.

In general, the product of differences is smaller than the corresponding difference of products.

So in particular it follows that \((A \setminus B) \times (C \setminus D) \subseteq (A \times C) \setminus (B \times D)\),

Projections and Cross Sections

In this discussion, suppose again that \( S \) and \( T \) are nonempty sets, and that \( C \subseteq S \times T \).

Note that \( C_x \subseteq T \) for \( x \in S \) and \( C^y \subseteq S \) for \( y \in T \).

The projections are the unions of the appropriate cross sections.

Cross sections are preserved under the set operations. We state the result for cross sections at \( x \in S \). By symmetry, of course, analgous results hold for cross sections at \( y \in T \).

For projections, the results are a bit more complicated. We give the results for projections onto \( T \); naturally the results for projections onto \( S \) are analogous.

It's easy to see that equality does not hold in general in parts (b) and (c). In part (b) for example, suppose that \( A_1, \; A_2 \subseteq S \) are nonempty and disjoint and \( B \subseteq T \) is nonempty. Let \( C = A_1 \times B \) and \( D = A_2 \times B \). Then \( C \cap D = \emptyset \) so \( (C \cap D)_T = \emptyset \). But \( C_T = D_T = B \). In part (c) for example, suppose that \( A \) is a nonempty proper subset of \( S \) and \( B \) is a nonempty proper subset of \( T \). Let \( C = A \times B \). Then \( C_T = B \) so \( (C_T)^c = B^c \). On the other hand, \( C^c = (A^c \times B) \cup (A \times B^c) \cup (A^c \times B^c) \), so \( (C^c)_T = T \).

Cross sections and projections will be extended to general product sets in the section on functions.

Mathematical Spaces

In mathematics, the term space usually refer to a universal set together with other mathematical structures defined on the set. The structures could be operators, relations, or collections of subsets for example. You are probably familiar with the concept of a vector space, consisting of a set of vectors together with (at least) operations of addition and scalar multiplication. We will see other examples in this chapter: measurable spaces measurable spaces, measure spaces), and (topological spaces. Ultimately, this text is about the study of probability spaces, beginning in Chapter 2. The universal set in a mathematical space is sometimes referred to as the base set.

Computational Exercises

Subsets of \( \R \)

Coins and Dice

Cards

A standard card deck can be modeled by the Cartesian product set \[ D = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, j, q, k\} \times \{\clubsuit, \diamondsuit, \heartsuit, \spadesuit\} \] where the first coordinate encodes the denomination or kind (ace, 2–10, jack, queen, king) and where the second coordinate encodes the suit (clubs, diamonds, hearts, spades). Sometimes we represent a card as a string rather than an ordered pair (for example \(q \heartsuit\) for the queen of hearts). For the problems in this subsection, the card deck \(D\) is the universal set.

A bridge hand is a subset of \( D \) with 13 cards. Often bridge hands are described by giving the cross sections by suit.

By contrast, it is usually more useful to describe a poker hand by giving the cross sections by denomination. In the usual version of draw poker, a hand is a subset of \( D \) with 5 cards.

The poker hand in the last exercise is known as a dead man's hand. Legend has it that Wild Bill Hickock held this hand at the time of his murder in 1876.

General unions and intersections

For the problems in this subsection, the universal set is \(\R\).

Subsets of \( \R^2 \)