Set theory is the foundation of probability and statistics, as it is for almost every branch of mathematics.
First, a set is simply a collection of objects; the objects are referred to as elements of the set. The statement that \(x\) is an element of set \(S\) is written \(x \in S\). By definition, a set is completely determined by its elements; thus sets \(A\) and \(B\) are equal if they have the same elements:
\[ A = B \text{ if and only if } x \in A \iff x \in B \]If \(A\) and \(B\) are sets then \(A\) is a subset of \(B\) if every element of \(A\) is also an element of \(B\):
\[ A \subseteq B \text{ if and only if } x \in A \implies x \in B \]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.
Membership is a primitive, undefined concept in naive set theory. Moreover, sets are usually constructed by either listing the elements of the set or by giving a condition that must be satisfied by the elements of the set. 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.
Let \(R = \{A : A \text{ is a set and } A \notin A\}\). Then \(R \in R\) if and only if \(R \notin R\).
Usually, the sets under discussion in a particular context are all subsets of a 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\).
In contrast to a universal set, the empty set, denoted \(\emptyset\), is the set with no elements.
\(\emptyset \subseteq A\) for every set \(A\).
Suppose that \(A\), \(B\) and \(C\) are subsets of a set \(S\). The subset relation is a partial order on the collection of subsets of \(S\). That is,
If \(S\) is a set, then the set of all subsets of \(S\) is known as the power set of \(S\) and is denoted \(\mathscr{P}(S)\).
The following special sets are used throughout the project, and often play the role of universal sets.
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\).
The union of \(A\) and \(B\) is the set obtained by combining the elements of \(A\) and \(B\).
\[ A \cup B = \{x \in S: x \in A \text{ or } x \in B\} \]The intersection of \(A\) and \(B\) is the set of elements common to both \(A\) and \(B\):
\[ A \cap B = \{x \in S: x \in A \text{ and } x \in B\}\]If the intersection of sets \(A\) and \(B\) is empty, then \(A\) and \(B\) are said to be disjoint: \( A \cap B = \emptyset \)
The set difference of \(B\) and \(A\) is the set of elements that are in \(B\) but not in \(A\):
\[ B \setminus A = \{x \in S: x \in B \text{ and } x \notin A\} \]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. The complement of \(A\) is the set of elements that are not in \(A\):
\[ A^c = \{ x \in S: x \notin A\} \]Note that union, intersection, and difference are binary set operations, while complement is a unary set operation.
In the Venn diagram applet, select each of the following and note the shaded area in the diagram.
In the following problems, \(A\), \(B\), and \(C\) are subsets of a universal set \(S\). The proofs are straightforward, and just use the definitions and basic logic.
\(A \cap B \subseteq A \subseteq A \cup B\).
The identity laws:
The idempotent laws:
The complement laws:
The double complement law: \((A^c)^c = A\)
The commutative laws:
The associative laws:
Thus, we can write \(A \cup B \cup C\) and \(A \cap B \cap C\) without ambiguity.
The distributive laws:
DeMorgan's laws (named after Agustus DeMorgan):
The following statements are equivalent:
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.
\((A \cup B) \setminus (A \cap B) = (A \setminus B) \cup (B \setminus A)\). This set 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.
The elements of \((A \cap B) \cup (A \cup B)^c\) belong to both the given sets or to neither of the sets.
There are 16 different (in general) sets that can be constructed from two given events \(A\) and \(B\).
In the Venn diagram applet, observe the diagram of each of the 16 sets that can be constructed from \(A\) and \(B\) using the set operations.
The operations of union and intersection can easily be extended to a finite or even an infinite collection of sets.
Suppose that \(\mathscr{A}\) is a nonempty collection of subsets of a universal set \(S\). In some cases, the subsets in \(\mathscr{A}\) may be naturally indexed by a nonempty index set \(I\), so that \(\mathscr{A} = \{A_i: i \in I\}\). (In a technical sense, any collection of subsets can be indexed--by itself!)
The union of the collection of sets \(\mathscr{A}\) is the set obtained by combining the elements of the sets in \(\mathscr{A}\):
\[ \bigcup \mathscr{A} = \{x \in S: x \in A \text{ for some } A \in \mathscr{A}\} \]If \(\mathscr{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\} \]The intersection of the collection of sets \(\mathscr{A}\) is the set of elements common to all of the sets in \(\mathscr{A}\):
\[ \bigcap \mathscr{A} = \{x \in S: x \in A \text{ for all } A \in \mathscr{A}\} \]If \(\mathscr{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\} \]The collection of sets \(\mathscr{A}\) is pairwise disjoint if the intersection of any two sets in the collection is empty: \(A \cap B = \emptyset\) for every \(A, \; B \in \mathscr{A}\) with \(A \ne B\). The collection of sets \(\mathscr{A}\) is said to partition a set \(B\) if the collection \(\mathscr{A}\) is pairwise disjoint and \(\bigcup \mathscr{A} = B\). Partitions are intimately related to equivalence relations.
In the following problems, \(\mathscr{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 general distributive laws:
Restate the laws in the notation where the collection \(\mathscr{A}\) is not indexed.
The general De Morgan's laws:
Restate the laws in the notation where the collection \(\mathscr{A}\) is not indexed.
Suppose that the collection \(\mathscr{A}\) partitions \(S\). For any subset \(B\), the collection \(\{A \cap B: A \in \mathscr{A}\}\) partitions \(B\).
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 the exercise below is due to Kazamierz Kuratowski
Define \((a, b) = \{\{a\}, \{a, b\}\}\). This definition captures the defining property of an ordered pair given above.
More generally, two ordered sequences of the same size (finite or infinite) are the same if and only if their corresponding coordinates agree:
\[ (x_1, x_2, \ldots, x_n) = (y_1, y_2, \ldots, y_n) \text{ if and only if } x_i = y_i \text{ for all } i \in \{1, 2, \ldots, n\} \] \[ (x_1, x_2, \ldots ) = (y_1, y_2, \ldots) \text{ if and only if } x_i = y_i \text{ for all } i \in \{1, 2, \ldots\} \]Suppose now that we have a sequence of sets \((S_1, S_2, \ldots, S_n)\). The Cartesian product of the sets (named for René Descartes) is defined as follows:
\[ S_1 \times S_2 \times \cdots \times S_n = \{(x_1, x_2, \ldots, x_n): x_i \in S_i \text{ for } i \in \{1, 2, \ldots, n\}\} \]If \(S_i = S\) for each \(i\), then the product set can be written compactly as \(S^n\). In particular, recall that \(\R\) denotes the set of real numbers so that \(\R^n\) is \(n\)-dimensional Euclidean space, 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. Finally, suppose that we have an infinite sequence of sets \((S_1, S_2, \ldots)\). The Cartesian product of the sets is defined by
\[ S_1 \times S_2 \times \cdots = \{(x_1, x_2, \ldots): x_i \in S_i \text{ for each } i \in \{1, 2, \ldots\}\} \]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 the exercises below 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.
On the other hand, the product of intersections is the same as the corresponding intersection of products.
\[ (A \times C) \cap (B \times D) = (A \cap B) \times (C \cap D) \]In general, the product of differences is smaller than the corresponding difference of products.
Suppose again that \( S \) and \( T \) are sets, and that \( C \subseteq S \times T \). For \( x \in S \) and \( y \in T \), the cross sections at \( x \) and at \( y \) are defined by
\[ C_x = \{y \in T: (x, y) \in C\}, \quad C^y = \{x \in S: (x, y) \in C\} \]Note that \( C_x \subseteq T \) for \( x \in S \) and \( C^y \subseteq S \) for \( y \in T \). We define the projections of \( C \) on \( T \) and onto \( S \) by
\[ C_T = \{t \in T: (x, y) \in C \text{ for some } x \in S\}, \quad C^S = \{x \in S: (x, y) \in C \text{ for some } 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 of \( x \in S \). By symmetry, of course, analgous results hold for cross sections of \( y \in T \).
Suppose that \( C, \; D \subseteq S \times T \). Then for \( x \in T \),
For part (a) note that \( y \in (C \cup D)_x \) if and only if \( (x, y) \in C \cup D \) if and only if \( (x, y) \in C \) or \( (x, y) \in D \) if and only if \( y \in C_x \) or \( y \in D_x \). Part (b) is analogous, replacing or with and. Part (c) is also analagous, replacing or with and not.
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.
Suppose again that \( C, \; D \subseteq S \times T \). Then
For part (a), suppose that \( y \in (C \cup D)_T \). Then there exists \( x \in S \) such that \( (x, y) \in C \cup D \). Hence \( (x, y) \in C \) so \( y \in C_T \), or \( (x, y) \in D \) so \( y \in D_T \). In either case, \( y \in C_T \cup D_T \). Conversely, suppose that \( y \in C_T \cup D_T \). Then \( y \in C_T \) or \( y \in D_T \). If \( y \in C_T \) then there exists \( x \in S \) such that \( (x, y) \in C \). But then \( (x, y) \in C \cup D \) so \( y \in (C \cup D)_T \). Similarly if \( y \in D_T \) then \( y \in (C \cup D)_T \).
For part (b), suppose that \( y \in (C \cap D)_T \). Then there exists \( x \in S \) such that \( (x, y) \in C \cap D \). Hence \( (x, y) \in C \) so \( y \in C_T \) and \( (x, y)\ in D \) so \( y \in D_T \). Therefore \( y \in C_T \cap D_T \).
For part (c), suppose that \( y \in (C_T)^c \). Then \( y \notin C_T \), so for every \( x \in S \), \( (x, y) \notin C \). Fix \( x_0 \in S \). Then \( (x_0, y) \notin C \) so \( (x_0, y) \in C^c \) and therefore \( y \in (C^c)_T \).
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) \), so \( (C^c)_T = T \).
Let \(S = \{1, 2, 3, 4\} \times \{1, 2, 3, 4, 5, 6\}\). This is the set of outcomes when a 4-sided die and a 6-sided die are tossed. Further let \(A = \{(x, y) \in S: x = 2\}\) and \(B = \{(x, y) \in S: x + y = 7\}\). Give each of the following sets in list form:
Let \(S = \{0, 1\}^3\). This is the set of outcomes when a coin is tossed 3 times (0 denotes tails and 1 denotes heads). Further let \(A = \{(x_1, x_2, x_3) \in S: x_2 = 1\}\) and \(B = \{(x_1, x_2, x_3) \in S: x_1 + x_2 + x_3 = 2\}\). Give each of the following sets in list form, using bit-string notation:
Let \(S = \{0, 1\}^2\). This is the set of outcomes when a coin is tossed twice (0 denotes tails and 1 denotes heads). Give \(\mathscr{P}(S)\) in list form.
A standard card deck can be modeled by the 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 problems in this subsection, the card deck \(D\) is the universal set.
Let \(H\) denote the set of hearts and \(F\) the set of face cards. Find
For the problems in this subsection, the universal set is \(\R\).
Let \(A_n = [0, 1 - \frac{1}{n}]\) for \(n \in \N_+\). Find
Let \(A_n = (2 - \frac{1}{n}, 5 + \frac{1}{n})\) for \(n \in \N_+\). Find