Sets
Remark. Probability and statistics describe events, outcomes, and parameters as sets. This page collects the definitions of sets that the Morrison Lab’s probability and statistics notes build on. The Functions page defines functions between sets, and the Expressions and Algorithms page defines the expressions that write functions down and the algorithms that compute them.
Definition 1 (Set) A set [1] is a collection of distinct objects, called its elements. We write \(a \in A\) when \(a\) is an element of the set \(A\), and \(a \notin A\) when it is not. Two sets are equal when they have exactly the same elements.
Remark 1 (Naive and formal set theory). Definition 1 is the informal (“naive”) notion of a set, which is all these notes need. Formal set theory states axioms for sets instead [1]. For example, the last sentence of Definition 1, that two sets are equal when they have exactly the same elements, is one of those axioms, the axiom of extensionality.
Example 1 (Sets of die rolls) The possible results of rolling a six-sided die form the set \({\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\), with \(3 \in {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\) and \(7 \notin {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\). The sets \({\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\) and \({\mathopen{}\left\{3, 2, 1\right\}\mathclose{}}\) are equal, because they have the same elements; the order in which the elements are listed does not matter.
Definition 2 (Roster notation) Writing a set by listing its elements between braces, as in \({\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\), is called roster notation [1]. An ellipsis, “\(\ldots\)”, can stand for elements that follow a clear pattern, as in \({\mathopen{}\left\{10, 20, 30, \ldots, 90\right\}\mathclose{}}\).
Example 2 (Rosters of vowels and odd integers)
In roster notation, the vowels of English are \({\mathopen{}\left\{a, e, i, o, u\right\}\mathclose{}}\), and the odd integers from \(1\) to \(99\) are \({\mathopen{}\left\{1, 3, 5, \ldots, 99\right\}\mathclose{}}\), where the ellipsis stands for the odd integers from \(7\) to \(97\). Listing an element twice does not add an element: \({\mathopen{}\left\{a, a, e\right\}\mathclose{}}\) and \({\mathopen{}\left\{a, e\right\}\mathclose{}}\) are the same set, since they have the same elements.
Definition 3 (Set-builder notation) For a set \(A\) and a statement \(P(x)\) about an element \(x\), set-builder notation [2] \({\mathopen{}\left\{x \in A : P(x)\right\}\mathclose{}}\) denotes the set of elements \(x\) of \(A\) for which \(P(x)\) is true.
Example 3 (Even die rolls in set-builder notation) \({\mathopen{}\left\{x \in {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}} : x \text{ is even}\right\}\mathclose{}} = {\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) is the set of even rolls, and \({\mathopen{}\left\{x \in \mathbb{R}: x > 0\right\}\mathclose{}}\) is the set of positive real numbers.
Definition 4 (Set-builder notation with an expression) For a set \(A\) and a rule \(f(x)\) that gives an object for each element \(x\) of \(A\), the notation \({\mathopen{}\left\{f(x) : x \in A\right\}\mathclose{}}\) stands for the set of the objects \(f(x)\) for \(x \in A\) [2]. That is, an object \(y\) is an element of \({\mathopen{}\left\{f(x) : x \in A\right\}\mathclose{}}\) when \(y = f(x)\) for some \(x \in A\).
Example 4 (Squaring die rolls)
Squaring each possible roll of a six-sided die gives the set
\[{\mathopen{}\left\{x^2 : x \in {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\right\}\mathclose{}} = {\mathopen{}\left\{1, 4, 9, 16, 25, 36\right\}\mathclose{}},\]
written in set-builder notation with an expression. Two choices of \(x\) can give the same \(x^2\), and that object is then one element of the set: \({\mathopen{}\left\{x^2 : x \in {\mathopen{}\left\{-2, -1, 0, 1, 2\right\}\mathclose{}}\right\}\mathclose{}} = {\mathopen{}\left\{0, 1, 4\right\}\mathclose{}}\), since \((-2)^2 = 2^2\) and \((-1)^2 = 1^2\).
Definition 5 (Subset) A set \(A\) is a subset [3] of a set \(B\), written \(A \subseteq B\), if every element of \(A\) is an element of \(B\).
Example 5 (Even die rolls) The even die rolls form a subset of the possible rolls: \({\mathopen{}\left\{2, 4, 6\right\}\mathclose{}} \subseteq {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\), because each of \(2\), \(4\), and \(6\) is a possible roll. The set \({\mathopen{}\left\{2, 4, 7\right\}\mathclose{}}\) is not a subset of \({\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\), because \(7\) is not a possible roll.
Theorem 1 (Every set is a subset of itself) For every set \(A\), \(A \subseteq A\).
Proof. Every element of \(A\) is an element of \(A\), which is Definition 5 with \(B = A\).
Remark 2 (The symbol \(\subset\)). Sources disagree about the symbol \(\subset\): some use it for “subset” (\(\subseteq\)), and others for “strict subset” (\(\subsetneq\)) [3]. For example, \({\mathopen{}\left\{1, 2\right\}\mathclose{}} \subset {\mathopen{}\left\{1, 2\right\}\mathclose{}}\) is true in the first reading, because \({\mathopen{}\left\{1, 2\right\}\mathclose{}} \subseteq {\mathopen{}\left\{1, 2\right\}\mathclose{}}\), and false in the second, because the two sets are equal. These notes avoid \(\subset\) and write \(\subseteq\) or \(\subsetneq\).
Definition 7 (Superset) A set \(B\) is a superset of a set \(A\), written \(B \supseteq A\), if every element of \(A\) is an element of \(B\).
Remark 3 (Superset and subset). \(B \supseteq A\) means the same thing as \(A \subseteq B\) (subset). For example, \({\mathopen{}\left\{1, 2, 3\right\}\mathclose{}} \supseteq {\mathopen{}\left\{1, 3\right\}\mathclose{}}\), and \({\mathopen{}\left\{1, 3\right\}\mathclose{}} \subseteq {\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\). But \({\mathopen{}\left\{1, 3\right\}\mathclose{}}\) is not a superset of \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\), because \(2 \in {\mathopen{}\left\{1, 2\right\}\mathclose{}}\) and \(2 \notin {\mathopen{}\left\{1, 3\right\}\mathclose{}}\).
Definition 8 (Strict superset) A set \(B\) is a strict superset of a set \(A\), written \(B \supsetneq A\), if \(B\) is a superset of \(A\) and \(B \neq A\).
Remark 4 (Strict superset and strict subset). \(B \supsetneq A\) means the same thing as \(A \subsetneq B\) (strict subset). For example, \({\mathopen{}\left\{1, 2, 3\right\}\mathclose{}} \supsetneq {\mathopen{}\left\{1, 3\right\}\mathclose{}}\), because \({\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\) contains \(2\) and \({\mathopen{}\left\{1, 3\right\}\mathclose{}}\) does not.
Example 6 (Strict subsets and supersets of die rolls) For the even rolls \(A = {\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) and the possible rolls \(B = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\):
- \(A \subsetneq B\), because \(A \subseteq B\) (Example 5) and \(1 \in B\) but \(1 \notin A\), so \(A \neq B\);
- \(B \supseteq A\) and \(B \supsetneq A\), for the same reasons;
- \(B \subseteq B\), but \(B\) is not a strict subset of itself, because \(B = B\); likewise \(B \supseteq B\), but \(B\) is not a strict superset of itself, because \(B = B\).
Definition 9 (Empty set) The empty set [4], denoted \(\emptyset\), is the set that has no elements.
Remark 5 (Other notation for the empty set). Other sources write \({\mathopen{}\left\{\right\}\mathclose{}}\) for \(\emptyset\) [4]. Some sources call it the null set, but in measure theory a “null set” usually means a set of measure zero, which need not be empty. For example, the interval \([0, 0] = {\mathopen{}\left\{0\right\}\mathclose{}}\) has length \(0 - 0 = 0\), so it is a null set in that sense, but it is not empty, because \(0 \in {\mathopen{}\left\{0\right\}\mathclose{}}\).
Example 7 (Impossible die rolls) No roll of a six-sided die is greater than 6, so \({\mathopen{}\left\{x \in {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}} : x > 6\right\}\mathclose{}} = \emptyset\).
Example 8 (Every impossible die roll is even) The set of die rolls greater than 6 is \(\emptyset\) (Example 7). So “every die roll greater than 6 is even” is vacuously true, and so is “every die roll greater than 6 is odd”: there is no such roll to fail either statement.
Theorem 2 (There is only one empty set) If \(E_1\) and \(E_2\) are sets with no elements, then \(E_1 = E_2\).
Proof. Neither set has any elements, so every element of \(E_1\) is an element of \(E_2\) and vice versa, vacuously. Sets with the same elements are equal (Definition 1).
Theorem 3 (The empty set is a subset of every set) For every set \(A\), \(\emptyset \subseteq A\).
Proof. By Definition 5, \(\emptyset \subseteq A\) fails only if some element of \(\emptyset\) is not in \(A\). The empty set has no elements, so no such element exists.
Example 9 (The power set of a two-element set)
The power set of \({\mathopen{}\left\{0, 1\right\}\mathclose{}}\) has four elements:
\[{\mathcal{P}\mathopen{}\left({\mathopen{}\left\{0, 1\right\}\mathclose{}}\right)\mathclose{}} = {\mathopen{}\left\{\emptyset, {\mathopen{}\left\{0\right\}\mathclose{}}, {\mathopen{}\left\{1\right\}\mathclose{}}, {\mathopen{}\left\{0, 1\right\}\mathclose{}}\right\}\mathclose{}}\]
It contains the empty set, since the empty set is a subset of every set by Theorem 3, and it contains \({\mathopen{}\left\{0, 1\right\}\mathclose{}}\) itself, by Theorem 1. Its elements are sets: \({\mathopen{}\left\{0\right\}\mathclose{}} \in {\mathcal{P}\mathopen{}\left({\mathopen{}\left\{0, 1\right\}\mathclose{}}\right)\mathclose{}}\), but \(0 \notin {\mathcal{P}\mathopen{}\left({\mathopen{}\left\{0, 1\right\}\mathclose{}}\right)\mathclose{}}\).
Definition 12 (Lower bound and upper bound) For a subset \(S \subseteq \mathbb{R}\) of the real numbers, a real number \(a\) is a lower bound of \(S\) if \(a \le x\) for every \(x \in S\), and a real number \(b\) is an upper bound of \(S\) if \(x \le b\) for every \(x \in S\); each is a bound of \(S\).
Definition 13 (Interval) An interval [7] is a subset of the real numbers that consists of all real numbers between two bounds \(a \le b\) (Definition 12), possibly including one or both bounds, or of all real numbers on one side of a single bound, or all of \(\mathbb{R}\). The bounds \(a\) and \(b\) that define the interval are its endpoints.
Definition 14 (Closed interval) For real numbers \(a \le b\), the closed interval is the interval (Definition 13) \([a, b] \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a \le x \le b\right\}\mathclose{}}\) that includes both bounds (Definition 12).
Definition 15 (Open interval) For real numbers \(a \le b\), the open interval is the interval (Definition 13) \((a, b) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a < x < b\right\}\mathclose{}}\) that includes neither bound (Definition 12).
Definition 16 (Half-open intervals) For real numbers \(a \le b\), the half-open intervals are the intervals (Definition 13) \([a, b) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a \le x < b\right\}\mathclose{}}\) and \((a, b] \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a < x \le b\right\}\mathclose{}}\) that include one bound (Definition 12) and not the other.
Definition 17 (Unbounded intervals) For real numbers \(a\) and \(b\), the unbounded intervals are the intervals (Definition 13) with at most one bound (Definition 12):
- \([a, \infty) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: x \ge a\right\}\mathclose{}}\) and \((a, \infty) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: x > a\right\}\mathclose{}}\);
- \((-\infty, b] \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: x \le b\right\}\mathclose{}}\) and \((-\infty, b) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: x < b\right\}\mathclose{}}\);
- \((-\infty, \infty) \stackrel{\text{def}}{=}\mathbb{R}\).
Remark 6 (Brackets and parentheses in interval notation). In the notation for an interval, a bracket marks an endpoint that belongs to the interval, while a parenthesis marks an endpoint that is excluded. The symbols \(\infty\), \(-\infty\) denote no real number, so they always get a parenthesis.
Example 10 (Which numbers are in an interval)
- \(1 \in [1, 2]\), but \(1 \notin (1, 2)\).
- \(2 \in (1, 2]\), but \(2 \notin [1, 2)\).
- \(1.5\) is in all four of \([1, 2]\), \((1, 2)\), \([1, 2)\), and \((1, 2]\).
- \([0, \infty)\) is the set of non-negative real numbers: \(0 \in [0, \infty)\) and \(1000 \in [0, \infty)\), but \(-0.1 \notin [0, \infty)\).
Definition 18 (Collection of sets, family of sets) A collection of sets (also called a family of sets) [8] is a set whose elements are themselves sets.
Example 11 (The collection of all subsets of a two-element set) The subsets of \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\) are \(\emptyset\), \({\mathopen{}\left\{1\right\}\mathclose{}}\), \({\mathopen{}\left\{2\right\}\mathclose{}}\), and \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\) (Theorem 3 and Theorem 1 give the first and the last), so the collection of all subsets of \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\) is
\[{\mathopen{}\left\{\emptyset, {\mathopen{}\left\{1\right\}\mathclose{}}, {\mathopen{}\left\{2\right\}\mathclose{}}, {\mathopen{}\left\{1, 2\right\}\mathclose{}}\right\}\mathclose{}}\]
It has four elements, each of them a set. The collection \({\mathopen{}\left\{\emptyset\right\}\mathclose{}}\) has one element, the empty set, so it is not equal to \(\emptyset\), which has none.
Definition 19 (Label) A label is a name or symbol attached to an object, so that we can refer to the object and tell it apart from other objects.
Example 12 (Labels) The numbers \(1, 2, 3\) can label three students in a class list. Then “student 2” refers to one particular student. The letters \(A\) and \(B\) can label two sets.
Example 13 (Index sets) The set \(\{1, \ldots, n\}\) labels the entries of a vector with \(n\) entries. The set of nonnegative real numbers can label moments in time.
Example 14 (Indexed families) The entries \(x_1, \ldots, x_n\) of a vector are an indexed family of numbers, with index set \(\{1, \ldots, n\}\). The functions \(f_\theta\), one for each parameter value \(\theta\) in a parameter set, are an indexed family of functions.
1 Combining sets
Definition 22 (Union) The union [11] of sets \(A\) and \(B\), written \(A \cup B\), is the set of elements that are in \(A\), in \(B\), or in both:
\[A \cup B \stackrel{\text{def}}{=}{\mathopen{}\left\{x : x \in A \text{ or } x \in B\right\}\mathclose{}}\]
Definition 23 (Union of a family of sets) Let \(I\) be a set of indices, such as \(\mathopen{}\left\{1, \ldots, n\right\}\mathclose{}\) or \(\mathopen{}\left\{1, 2, 3, \ldots\right\}\mathclose{}\), and let \(A_i\) be a set for each \(i \in I\). The union of the sets \(A_i\), written \(\bigcup_{i \in I} A_i\), is the set of elements that are in at least one \(A_i\). For \(I = \mathopen{}\left\{1, \ldots, n\right\}\mathclose{}\), it is also written \(\bigcup_{i=1}^{n} A_i\) or \(A_1 \cup \cdots \cup A_n\), and for \(I = \mathopen{}\left\{1, 2, 3, \ldots\right\}\mathclose{}\), it is written \(\bigcup_{i=1}^{\infty} A_i\).
Definition 24 (Intersection) The intersection [12] of sets \(A\) and \(B\), written \(A \cap B\), is the set of elements that are in both \(A\) and \(B\):
\[A \cap B \stackrel{\text{def}}{=}{\mathopen{}\left\{x : x \in A \text{ and } x \in B\right\}\mathclose{}}\]
Definition 25 (Intersection of a family of sets) Let \(I\) be a nonempty set of indices, such as \(\mathopen{}\left\{1, \ldots, n\right\}\mathclose{}\) or \(\mathopen{}\left\{1, 2, 3, \ldots\right\}\mathclose{}\), and let \(A_i\) be a set for each \(i \in I\). The intersection of the sets \(A_i\), written \(\bigcap_{i \in I} A_i\), is the set of elements that are in every \(A_i\). For \(I = \mathopen{}\left\{1, \ldots, n\right\}\mathclose{}\), it is also written \(\bigcap_{i=1}^{n} A_i\) or \(A_1 \cap \cdots \cap A_n\), and for \(I = \mathopen{}\left\{1, 2, 3, \ldots\right\}\mathclose{}\), it is written \(\bigcap_{i=1}^{\infty} A_i\).
Definition 26 (Set difference) The set difference [13] of sets \(A\) and \(B\), written \(A \setminus B\), is the set of elements of \(A\) that are not in \(B\):
\[A \setminus B \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in A : x \notin B\right\}\mathclose{}}\]
Definition 27 (Complement) Let \(A\) be a subset of a set \(S\). The complement [13] of \(A\) in \(S\) is the set difference (Definition 26) \(S \setminus A\): the elements of \(S\) that are not in \(A\). When the set \(S\) is clear from context, the complement of \(A\) is written \(A^c\):
\[A^c \stackrel{\text{def}}{=}S \setminus A = {\mathopen{}\left\{x \in S : x \notin A\right\}\mathclose{}}\]
Example 15 (Complements of sets of die rolls) Let \(S = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\) be the possible rolls of a die.
- The complement of the even rolls \(A = {\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) is \(A^c = {\mathopen{}\left\{1, 3, 5\right\}\mathclose{}}\), the odd rolls.
- The complement of \(S\) itself is \(S^c = \emptyset\), and the complement of \(\emptyset\) is \(\emptyset^c = S\).
The complement depends on \(S\): in \(S = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\), the complement of \({\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) is \({\mathopen{}\left\{1, 3, 5\right\}\mathclose{}}\), but in \(S = {\mathopen{}\left\{2, 4, 6, 8\right\}\mathclose{}}\), it is \({\mathopen{}\left\{8\right\}\mathclose{}}\).
Example 16 (Combining sets of die rolls) Let \(A = {\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) (the even rolls) and \(B = {\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\) (the rolls of at most 3). Then:
- \(A \cup B = {\mathopen{}\left\{1, 2, 3, 4, 6\right\}\mathclose{}}\), the rolls that are even or at most 3;
- \(A \cap B = {\mathopen{}\left\{2\right\}\mathclose{}}\), the only roll that is both;
- \(A \setminus B = {\mathopen{}\left\{4, 6\right\}\mathclose{}}\), the even rolls greater than 3;
- \({\mathopen{}\left\{2, 4, 6\right\}\mathclose{}} \cap {\mathopen{}\left\{1, 3, 5\right\}\mathclose{}} = \emptyset\): no roll is both even and odd.
Example 17 (Unions and intersections of many sets)
\[ \begin{aligned} \bigcup_{i=1}^{3} {\mathopen{}\left\{i, i + 1\right\}\mathclose{}} &= {\mathopen{}\left\{1, 2\right\}\mathclose{}} \cup {\mathopen{}\left\{2, 3\right\}\mathclose{}} \cup {\mathopen{}\left\{3, 4\right\}\mathclose{}} \\ &= {\mathopen{}\left\{1, 2, 3, 4\right\}\mathclose{}}. \end{aligned} \]
\(\bigcup_{i=1}^{\infty} {\mathopen{}\left\{i\right\}\mathclose{}} = \mathbb{N}\): each natural number \(n\) is in the set \({\mathopen{}\left\{n\right\}\mathclose{}}\), and each set \({\mathopen{}\left\{i\right\}\mathclose{}}\) contains only the natural number \(i\).
\(\bigcap_{i=1}^{\infty} [0, 1/i] = {\mathopen{}\left\{0\right\}\mathclose{}}\): \(0\) is in every interval \([0, 1/i]\); a number \(x > 0\) is not in \([0, 1/i]\) once \(i > 1/x\); and a number \(x < 0\) is in none of them.
Theorem 4 (De Morgan’s laws) Let \(S\) be a set, let \(I\) be a nonempty set of indices, and let \(A_i\) be a subset of \(S\) for each \(i \in I\). Then the complement of a union is the intersection of the complements, [14] and the complement of an intersection is the union of the complements:
\[ \begin{aligned} S \setminus \bigcup_{i \in I} A_i &= \bigcap_{i \in I} (S \setminus A_i) \\ S \setminus \bigcap_{i \in I} A_i &= \bigcup_{i \in I} (S \setminus A_i) \end{aligned} \]
With the complement notation of Definition 27, these read \(\mathopen{}\left(\bigcup_{i \in I} A_i\right)\mathclose{}^c = \bigcap_{i \in I} A_i^c\) and \(\mathopen{}\left(\bigcap_{i \in I} A_i\right)\mathclose{}^c = \bigcup_{i \in I} A_i^c\).
Proof. Two sets are equal when they have the same elements (Definition 1), so it is enough to show that an element \(x\) is in the left-hand side if and only if (\(\iff\)) it is in the right-hand side. For the first law:
\[ \begin{aligned} x \in S \setminus \bigcup_{i \in I} A_i &\iff x \in S \text{ and } x \notin \bigcup_{i \in I} A_i && \text{(}\href{#def-set-difference}{\text{Definition~26}}\text{)} \\ &\iff x \in S \text{ and } x \notin A_i \text{ for every } i \in I && \text{(}\href{#def-union}{\text{Definition~22}}\text{)} \\ &\iff x \in S \setminus A_i \text{ for every } i \in I && \text{(}\href{#def-set-difference}{\text{Definition~26}}\text{)} \\ &\iff x \in \bigcap_{i \in I} (S \setminus A_i) && \text{(}\href{#def-intersection}{\text{Definition~24}}\text{)} \end{aligned} \]
For the second law:
\[ \begin{aligned} x \in S \setminus \bigcap_{i \in I} A_i &\iff x \in S \text{ and } x \notin \bigcap_{i \in I} A_i && \text{(}\href{#def-set-difference}{\text{Definition~26}}\text{)} \\ &\iff x \in S \text{ and } x \notin A_i \text{ for some } i \in I && \text{(}\href{#def-intersection}{\text{Definition~24}}\text{)} \\ &\iff x \in S \setminus A_i \text{ for some } i \in I && \text{(}\href{#def-set-difference}{\text{Definition~26}}\text{)} \\ &\iff x \in \bigcup_{i \in I} (S \setminus A_i) && \text{(}\href{#def-union}{\text{Definition~22}}\text{)} \end{aligned} \]
Example 18 (De Morgan’s laws for die rolls) In \(S = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\), let \(A = {\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) and \(B = {\mathopen{}\left\{1, 2, 3\right\}\mathclose{}}\), as in Example 16, so \(A^c = {\mathopen{}\left\{1, 3, 5\right\}\mathclose{}}\) and \(B^c = {\mathopen{}\left\{4, 5, 6\right\}\mathclose{}}\).
\[ \begin{aligned} (A \cup B)^c &= {\mathopen{}\left\{1, 2, 3, 4, 6\right\}\mathclose{}}^c \\ &= {\mathopen{}\left\{5\right\}\mathclose{}}, \end{aligned} \]
and
\[ \begin{aligned} A^c \cap B^c &= {\mathopen{}\left\{1, 3, 5\right\}\mathclose{}} \cap {\mathopen{}\left\{4, 5, 6\right\}\mathclose{}} \\ &= {\mathopen{}\left\{5\right\}\mathclose{}}. \end{aligned} \]
\[ \begin{aligned} (A \cap B)^c &= {\mathopen{}\left\{2\right\}\mathclose{}}^c \\ &= {\mathopen{}\left\{1, 3, 4, 5, 6\right\}\mathclose{}}, \end{aligned} \]
and
\[ \begin{aligned} A^c \cup B^c &= {\mathopen{}\left\{1, 3, 5\right\}\mathclose{}} \cup {\mathopen{}\left\{4, 5, 6\right\}\mathclose{}} \\ &= {\mathopen{}\left\{1, 3, 4, 5, 6\right\}\mathclose{}}. \end{aligned} \]
Definition 28 (Disjoint sets) Two sets \(A\) and \(B\) are disjoint if their intersection is the empty set:
\[A \cap B = \emptyset\]
Example 19 (Two disjoint sets of die rolls) For the die rolls \(D = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\) (sets of die rolls), the sets \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\) and \({\mathopen{}\left\{5, 6\right\}\mathclose{}}\) are disjoint: no roll is in both. The sets \({\mathopen{}\left\{2, 4, 6\right\}\mathclose{}}\) and \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\) are not, because \(2\) is in both.
Example 20 (Low, middle and high die rolls) For the die rolls \(D = {\mathopen{}\left\{1, 2, 3, 4, 5, 6\right\}\mathclose{}}\) (sets of die rolls), the sets \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\), \({\mathopen{}\left\{3, 4\right\}\mathclose{}}\) and \({\mathopen{}\left\{5, 6\right\}\mathclose{}}\) are pairwise disjoint: no roll is in more than one of them. The sets \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\), \({\mathopen{}\left\{3, 4\right\}\mathclose{}}\) and \({\mathopen{}\left\{2, 5\right\}\mathclose{}}\) are not, because \(2\) is in both the first and the third.
Definition 30 (Ordered pair) An ordered pair [16] \((a, b)\) is a pair of objects listed in order, with \(a\) first and \(b\) second; two ordered pairs are equal, \((a, b) = (c, d)\), when \(a = c\) and \(b = d\).
Definition 31 (Cartesian product) The Cartesian product [17] of sets \(A\) and \(B\), written \(A \times B\), is the set of ordered pairs whose first entry is in \(A\) and whose second entry is in \(B\):
\[A \times B \stackrel{\text{def}}{=}{\mathopen{}\left\{(a, b) : a \in A \text{ and } b \in B\right\}\mathclose{}}\]
Example 21 (Cartesian products)
- \({\mathopen{}\left\{1, 2\right\}\mathclose{}} \times {\mathopen{}\left\{5, 6\right\}\mathclose{}} = {\mathopen{}\left\{(1, 5), (1, 6), (2, 5), (2, 6)\right\}\mathclose{}}\). The pair \((5, 1)\) is not in it, because its first entry, \(5\), is not in \({\mathopen{}\left\{1, 2\right\}\mathclose{}}\); so \((1, 5) \ne (5, 1)\).
- The results of rolling a die twice form \({\mathopen{}\left\{1, \ldots, 6\right\}\mathclose{}} \times {\mathopen{}\left\{1, \ldots, 6\right\}\mathclose{}}\), which has \(6 \cdot 6 = 36\) elements, such as \((3, 5)\): a 3 on the first roll and a 5 on the second.
- \([0, 2] \times [0, 3]\) is the set of points \((x, y)\) in the plane with \(0 \le x \le 2\) and \(0 \le y \le 3\): a rectangle of width \(2\) and height \(3\).
Definition 32 (Tuple) For a natural number \(n\), an \(n\)-tuple [18] \((a_1, a_2, \ldots, a_n)\) is a list of \(n\) objects in order. Two \(n\)-tuples are equal when their entries are equal in each position.
Example 22 (Dates as tuples)
A calendar date can be written as a \(3\)-tuple (year, month, day), such as \((2027, 1, 4)\) for 4 January 2027. The \(3\)-tuples \((2027, 1, 4)\) and \((2027, 4, 1)\) are not the same, because their second entries differ, and they name different days. An ordered pair is a \(2\)-tuple.
Definition 33 (Cartesian product of several sets) For a natural number \(n\) and sets \(A_1, A_2, \ldots, A_n\), the Cartesian product [17] \(A_1 \times A_2 \times \cdots \times A_n\) is the set of \(n\)-tuples whose \(i\)th entry is in \(A_i\) for each \(i\):
\[A_1 \times \cdots \times A_n \stackrel{\text{def}}{=}{\mathopen{}\left\{(a_1, \ldots, a_n) : a_i \in A_i \text{ for each } i\right\}\mathclose{}}\]
Example 23 (Three coin flips)
Let \(C = {\mathopen{}\left\{H, T\right\}\mathclose{}}\) be the faces of a coin. The ways three flips can come out form the Cartesian product \(C \times C \times C\), whose elements are the eight \(3\)-tuples
\[(H, H, H), (H, H, T), (H, T, H), (H, T, T), (T, H, H), (T, H, T), (T, T, H), (T, T, T).\]
For example, \((H, T, T)\) is heads on the first flip and tails on the second and third.
2 Extended non-negative real numbers
Definition 34 (Extended non-negative real numbers) The extended non-negative real numbers, written \([0, \infty]\), are the non-negative real numbers together with an extra element \(\infty\) that is greater than every real number:
\[[0, \infty] \stackrel{\text{def}}{=}[0, \infty) \cup {\mathopen{}\left\{\infty\right\}\mathclose{}}\]
Addition extends to \([0, \infty]\) by setting
\[ \begin{aligned} x + \infty &= \infty + x \\ &= \infty \end{aligned} \]
for every \(x \in [0, \infty]\).
Remark 7 (Arithmetic with \(\infty\)). \(\infty\) is not a real number, so some real-number arithmetic does not extend to it: \(\infty - \infty\) is left undefined, and \(\infty + 1 = \infty + 2\) does not imply \(1 = 2\). Measure theory uses \([0, \infty]\) because the size of a set, such as the length of the whole real line, can be infinite [19].
Example 24 (Adding with \(\infty\)) In \([0, \infty]\), \(2 + 3 = 5\) as usual, while \(2 + \infty = \infty\) and \(\infty + \infty = \infty\).
3 Further reading
These books and articles treat sets and the logic behind them in more depth.
- Devlin [20] is an undergraduate introduction to axiomatic set theory. It covers the axioms of set theory, ordinals, and cardinals, which go well beyond the countable sets and functions in these notes.
- Halmos [21] is a short, informal treatment of the same axioms, covering relations, functions, families of sets, and cardinal numbers.
- Enderton [22] is a standard introduction to mathematical logic. Its first chapter collects the facts about sets, relations, and functions that the later chapters use.
- Barker-Plummer et al. [23] teaches propositional and first-order logic, the language behind statements such as “for every set \(A\) there exists…”.
Definitions on this page
- Definition 1 (Set)
- Definition 2 (Roster notation)
- Definition 3 (Set-builder notation)
- Definition 4 (Set-builder notation with an expression)
- Definition 5 (Subset)
- Definition 6 (Strict subset, proper subset)
- Definition 7 (Superset)
- Definition 8 (Strict superset)
- Definition 9 (Empty set)
- Definition 10 (Vacuous truth)
- Definition 11 (Power set)
- Definition 12 (Lower bound and upper bound)
- Definition 13 (Interval)
- Definition 14 (Closed interval)
- Definition 15 (Open interval)
- Definition 16 (Half-open intervals)
- Definition 17 (Unbounded intervals)
- Definition 18 (Collection of sets, family of sets)
- Definition 19 (Label)
- Definition 20 (Index set)
- Definition 21 (Indexed family)
- Definition 22 (Union)
- Definition 23 (Union of a family of sets)
- Definition 24 (Intersection)
- Definition 25 (Intersection of a family of sets)
- Definition 26 (Set difference)
- Definition 27 (Complement)
- Definition 28 (Disjoint sets)
- Definition 29 (Pairwise disjoint sets, mutually disjoint sets)
- Definition 30 (Ordered pair)
- Definition 31 (Cartesian product)
- Definition 32 (Tuple)
- Definition 33 (Cartesian product of several sets)
- Definition 34 (Extended non-negative real numbers)