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.
1 Sets
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 (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 2 (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 3 (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 3 (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 3 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 5 (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 6 (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 4 (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 3) 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 7 (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 5 (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 6 (Every impossible die roll is even) The set of die rolls greater than 6 is \(\emptyset\) (Example 5). 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 3, \(\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.
Definition 9 (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 10 (Interval) An interval [6] is a subset of the real numbers that consists of all real numbers between two bounds \(a \le b\) (Definition 9), 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 11 (Closed interval) For real numbers \(a \le b\), the closed interval is the interval (Definition 10) \([a, b] \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a \le x \le b\right\}\mathclose{}}\) that includes both bounds (Definition 9).
Definition 12 (Open interval) For real numbers \(a \le b\), the open interval is the interval (Definition 10) \((a, b) \stackrel{\text{def}}{=}{\mathopen{}\left\{x \in \mathbb{R}: a < x < b\right\}\mathclose{}}\) that includes neither bound (Definition 9).
Definition 13 (Half-open intervals) For real numbers \(a \le b\), the half-open intervals are the intervals (Definition 10) \([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 9) and not the other.
Definition 14 (Unbounded intervals) For real numbers \(a\) and \(b\), the unbounded intervals are the intervals (Definition 10) with at most one bound (Definition 9):
- \([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 7 (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 15 (Collection of sets, family of sets) A collection of sets (also called a family of sets) [7] is a set whose elements are themselves sets.
Example 8 (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 16 (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 9 (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 10 (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 11 (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.
2 Combining sets
Definition 19 (Union) The union [10] 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 20 (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 21 (Intersection) The intersection [11] 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 22 (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 23 (Set difference) The set difference [12] 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 24 (Complement) Let \(A\) be a subset of a set \(S\). The complement [12] of \(A\) in \(S\) is the set difference (Definition 23) \(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 12 (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 13 (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 14 (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, [13] 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 24, 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~23}}\text{)} \\ &\iff x \in S \text{ and } x \notin A_i \text{ for every } i \in I && \text{(}\href{#def-union}{\text{Definition~19}}\text{)} \\ &\iff x \in S \setminus A_i \text{ for every } i \in I && \text{(}\href{#def-set-difference}{\text{Definition~23}}\text{)} \\ &\iff x \in \bigcap_{i \in I} (S \setminus A_i) && \text{(}\href{#def-intersection}{\text{Definition~21}}\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~23}}\text{)} \\ &\iff x \in S \text{ and } x \notin A_i \text{ for some } i \in I && \text{(}\href{#def-intersection}{\text{Definition~21}}\text{)} \\ &\iff x \in S \setminus A_i \text{ for some } i \in I && \text{(}\href{#def-set-difference}{\text{Definition~23}}\text{)} \\ &\iff x \in \bigcup_{i \in I} (S \setminus A_i) && \text{(}\href{#def-union}{\text{Definition~19}}\text{)} \end{aligned} \]
Example 15 (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 13, 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 25 (Disjoint sets) Two sets \(A\) and \(B\) are disjoint if their intersection is the empty set:
\[A \cap B = \emptyset\]
Example 16 (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 17 (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 27 (Ordered pair) An ordered pair [15] \((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 28 (Cartesian product) The Cartesian product [16] 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 18 (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\).
3 Extended non-negative real numbers
Definition 29 (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 [17].
Example 19 (Adding with \(\infty\)) In \([0, \infty]\), \(2 + 3 = 5\) as usual, while \(2 + \infty = \infty\) and \(\infty + \infty = \infty\).
4 Further reading
These books and articles treat sets and the logic behind them in more depth.
- Devlin [18] 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 [19] is a short, informal treatment of the same axioms, covering relations, functions, families of sets, and cardinal numbers.
- Enderton [20] 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. [21] teaches propositional and first-order logic, the language behind statements such as “for every set \(A\) there exists…”.