π Changes in this PR: State Machines and Finite Automata, Calendar, Contrapositive and Contradiction, Inference and Direct Proof, Logical Equivalence and Negation, Functional Programming, Graphs, Proving Non-Conditional Statements, Mathematical Induction, Loop Invariants, Predicates and Quantifiers, Propositional Logic, Recurrence Relations and Growth Rates, Recursion, Relations, Proofs with Sets, Sets, WWU CSCI 201 Syllabus, Trees, Expressions and Algorithms, Functions, Growth Rates, Math for Computer Science, Induction and Recursion, Notation, Number Systems, Proof Writing, Relations, Sets
π‘ Tip: If change highlighting is glitchy, add the no-preview-highlights label to this PR to disable it.
Definition 1 (Set) A set 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.
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 (Wikipedia contributors 2026n). 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 (Wikipedia contributors 2026o) \({\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\) (Wikipedia contributors 2026o). 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 (Wikipedia contributors 2026p) 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\).
Definition 6 (Strict subset, proper subset) A set \(A\) is a strict subset (also called a proper subset) of a set \(B\), written \(A \subsetneq B\), if \(A\) is a subset of \(B\) and \(A \neq B\).
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\).
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\).
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\).
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\).
Definition 10 (Vacuous truth) A statement of the form βevery element of \(A\) has property \(P\)β is vacuously true (Wikipedia contributors 2026s) when \(A\) is the empty set: \(A\) has no elements, so no element of \(A\) fails to have property \(P\).
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.
Definition 11 (Power set) The power set (Wikipedia contributors 2026m) of a set \(A\), written \({\mathcal{P}\mathopen{}\left(A\right)\mathclose{}}\), is the set of all subsets of \(A\):
\[{\mathcal{P}\mathopen{}\left(A\right)\mathclose{}} \stackrel{\text{def}}{=}{\mathopen{}\left\{S : S \subseteq A\right\}\mathclose{}}\]
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 (Wikipedia contributors 2026k) 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}\).
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) (Wikipedia contributors 2026g) 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.
Definition 20 (Index set) An index set (Wikipedia contributors 2026h) is a set whose elements are used as labels for objects. Each element of the index set is called an index.
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.
Definition 21 (Indexed family) An indexed family (Wikipedia contributors 2026i) is a collection of objects, one for each element of a given index set. The object for the index \(i\) is written \(a_i\).
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.
Combining sets
Definition 22 (Union) The union (Wikipedia contributors 2026r) 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 (Wikipedia contributors 2026j) 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 (Wikipedia contributors 2026b) 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 (Wikipedia contributors 2026b) 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, (Wikipedia contributors 2026c) 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. Each step applies the definition named at its right: set difference (Definition 26), union (Definition 22) or intersection (Definition 24). 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{(set difference)} \\
&\iff x \in S \text{ and } x \notin A_i \text{ for every } i \in I
&& \text{(union)} \\
&\iff x \in S \setminus A_i \text{ for every } i \in I
&& \text{(set difference)} \\
&\iff x \in \bigcap_{i \in I} (S \setminus A_i)
&& \text{(intersection)}
\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{(set difference)} \\
&\iff x \in S \text{ and } x \notin A_i \text{ for some } i \in I
&& \text{(intersection)} \\
&\iff x \in S \setminus A_i \text{ for some } i \in I
&& \text{(set difference)} \\
&\iff x \in \bigcup_{i \in I} (S \setminus A_i)
&& \text{(union)}
\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.
Definition 29 (Pairwise disjoint sets, mutually disjoint sets) Some sets \(A_1, A_2, \ldots\) (a list that may end or go on without end) are pairwise disjoint (Wikipedia contributors 2026d) (also called mutually disjoint) when every two of them are disjoint:
\[A_i \cap A_j = \emptyset \quad \text{for all } i \neq j\]
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 (Wikipedia contributors 2026l) \((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 (Wikipedia contributors 2026a) 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 (Wikipedia contributors 2026q) \((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 (Wikipedia contributors 2026a) \(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.
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]\).
Example 24 (Adding with \(\infty\)) In \([0, \infty]\), \(2 + 3 = 5\) as usual, while \(2 + \infty = \infty\) and \(\infty + \infty = \infty\).
Further reading
These books and articles treat sets and the logic behind them in more depth.
- Devlin (1993) 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 (1974) is a short, informal treatment of the same axioms, covering relations, functions, families of sets, and cardinal numbers.
- Enderton (2001) 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. (2011) teaches propositional and first-order logic, the language behind statements such as βfor every set \(A\) there existsβ¦β.
References
Barker-Plummer, Dave, Jon Barwise, and John Etchemendy. 2011.
Language, Proof and Logic. 2nd ed. CSLI Publications.
https://www.amazon.com/dp/1575866323.
Devlin, Keith. 1993.
The Joy of Sets: Fundamentals of Contemporary Set Theory. 2nd ed. Undergraduate Texts in Mathematics. Springer.
https://doi.org/10.1007/978-1-4612-0903-4.
Enderton, Herbert B. 2001.
A Mathematical Introduction to Logic. 2nd ed. Academic Press.
https://doi.org/10.1016/C2009-0-22107-6.
Halmos, Paul R. 1974.
Naive Set Theory. Undergraduate Texts in Mathematics. Springer.
https://doi.org/10.1007/978-1-4757-1645-0.
Wikipedia contributors. 2026a.
Cartesian Product β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Cartesian_product.
Wikipedia contributors. 2026b.
Complement (Set Theory) β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Complement_(set_theory).
Wikipedia contributors. 2026c.
De Morganβs Laws β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/De_Morgan%27s_laws.
Wikipedia contributors. 2026d.
Disjoint Sets β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Disjoint_sets.
Wikipedia contributors. 2026e.
Empty Set β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Empty_set.
Wikipedia contributors. 2026f.
Extended Real Number Line β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Extended_real_number_line.
Wikipedia contributors. 2026g.
Family of Sets β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Family_of_sets.
Wikipedia contributors. 2026h.
Index Set β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Index_set.
Wikipedia contributors. 2026i.
Indexed Family β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Indexed_family.
Wikipedia contributors. 2026j.
Intersection (Set Theory) β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Intersection_(set_theory).
Wikipedia contributors. 2026k.
Interval (Mathematics) β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Interval_(mathematics).
Wikipedia contributors. 2026l.
Ordered Pair β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Ordered_pair.
Wikipedia contributors. 2026m.
Power Set β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Power_set.
Wikipedia contributors. 2026n.
Set (Mathematics) β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Set_(mathematics).
Wikipedia contributors. 2026o.
Set-Builder Notation β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Set-builder_notation.
Wikipedia contributors. 2026p.
Subset β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Subset.
Wikipedia contributors. 2026q.
Tuple β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Tuple.
Wikipedia contributors. 2026r.
Union (Set Theory) β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Union_(set_theory).
Wikipedia contributors. 2026s.
Vacuous Truth β Wikipedia, the Free Encyclopedia.
https://en.wikipedia.org/wiki/Vacuous_truth.
Back to top