Introduction to set theory

Set theory is the language of the modern foundation of mathematics, as discussed in chapter 1. It is unsurprising, then, that it arises throughout the study of mathematics. We will use set theory extensively in chapter 3 on probability theory.

The axioms of ZFC set theory were introduced in chapter 1. Instead of proceeding in the pure mathematics way of introducing and proving theorems, we will opt for a more applied approach in which we begin with some simple definitions and include basic operations. A more thorough and still readable treatment is given by Ciesielski (1997) and a very gentle version by Enderton (1977).

A set is a collection of objects. Set theory gives us a way to describe these collections. Often, the objects in a set are numbers or sets of numbers. However, a set could represent collections of zebras and trees and hairballs. For instance, here are some sets: \[\begin{aligned} \{1,5,\pi\} && \{\text{zebra named ``Calvin''},\text{ a burnt cheeto}\} && \{\{1,2\},\{5,\text{hippo},7\},62\}.\end{aligned}\]

A field is a set with special structure. This structure is provided by the addition (\(+\)) and multiplication (\(\times\)) operators and their inverses subtraction (\(-\)) and division (\(\div\)). The quintessential example of a field is the set of real numbers \(\mathbb{R}\), which admits these operators, making it a field. The reals \(\mathbb{R}\), the complex numbers \(\mathbb{C}\), the integers \(\mathbb{Z}\), and the natural numbers¹ \(\mathbb{N}\) are the fields we typically consider.

Set membership is the belonging of an object to a set. It is denoted with the symbol \(\in\), which can be read “is an element of,” for element \(x\) and set \(X\): \[\begin{aligned} x \in X.\end{aligned}\] For instance, we might say \(7\in\{1,7,2\}\) or \(4\notin\{1,7,2\}\). Or, we might declare that \(a\) is a real number by stating: \(x\in\mathbb{R}\).

Set operations can be used to construct new sets from established sets. We consider a few common set operations, now.

The union \(\cup\) of sets is the set containing all the elements of the original sets (no repetition allowed). The union of sets \(A\) and \(B\) is denoted \(A\cup B\). For instance, let \(A = \{1,2,3\}\) and \(B = \{-1,3\}\); then \[\begin{aligned} A \cup B = \{1,2,3,-1\}.\end{aligned}\]

The intersection \(\cap\) of sets is a set containing the elements common to all the original sets. The intersection of sets \(A\) and \(B\) is denoted \(A\cap B\). For instance, let \(A = \{1,2,3\}\) and \(B = \{2,3,4\}\); then \[\begin{aligned} A \cap B = \{2,3\}.\end{aligned}\]

If two sets have no elements in common, the intersection is the empty set \(\varnothing= \{\}\), the unique set with no elements.

The set difference of two sets \(A\) and \(B\) is the set of elements in \(A\) that aren’t also in \(B\). It is denoted \(A\setminus B\). For instance, let \(A = \{1,2,3\}\) and \(B = \{2,3,4\}\). Then \[\begin{aligned} A \setminus B = \{1\} && B \setminus A = \{4\}.\end{aligned}\]

A subset \(\subseteq\) of a set is a set, the elements of which are contained in the original set. If the two sets are equal, one is still considered a subset of the other. We call a subset that is not equal to the other set a proper subset \(\subset\). For instance, let \(A = \{1,2,3\}\) and \(B = \{1,2\}\). Then \[\begin{aligned} B \subseteq A && B \subset A && A \subseteq A.\end{aligned}\]

The complement of a subset is a set of elements of the original set that aren’t in the subset. For instance, if \(B \subseteq A\), then the complement of \(B\), denoted \(\overline{B}\) is \[\begin{aligned} \overline{B} = A \setminus B.\end{aligned}\]

The cartesian product of two sets \(A\) and \(B\) is denoted \(A \times B\) and is the set of all ordered pairs \((a,b)\) where \(a \in A\) and \(b \in B\). It’s worthwhile considering the following notation for this definition: \[\begin{aligned} A \times B = \{ (a,b) \mid a \in A \text{ and } b \in B \}\end{aligned}\] which means “the cartesian product of \(A\) and \(B\) is the ordered pair \((a,b)\) such that \(a \in A\) and \(b \in B\)” in set-builder notation (Wikipedia 2019).

Let \(A\) and \(B\) be sets. A map or function \(f\) from \(A\) to \(B\) is an assignment of some element \(a\in A\) to each element \(b\in B\). The function is denoted \(f: A \rightarrow B\) and we say that \(f\) maps each element \(a\in A\) to an element \(f(a)\in B\) called the value of \(a\) under \(f\), or \(a \mapsto f(a)\). We say that \(f\) has domain \(A\) and codomain \(B\). The image of \(f\) is the subset of its codomain \(B\) that contains the values of all elements mapped by \(f\) from its domain \(A\).