This book, like almost every other modern mathematics book, develops its subject matter assuming a knowledge of elementary set theory. This assumption is often not justified.
Before we move into the last part of number theoretic results, involving modular arithmetic, we need to talk a bit about sets. Up to now, sets are a bit mysterious, but important since in some cases we've been alluding to them. Modern mathematics happens to be built on the idea that everything is a set. Everything. Functions? Sets. Numbers? Sets. Problems? Sets.
We've also already seen sets sneak into our discussions a few times.
So what is a set?
A set is an unordered collection of objects. If $S$ is a set and $a$ is a member of $S$, then we write $a \in S$, which is read "$a$ is an element of $S$". Similarly, if $a$ is not a member of $S$, then we write $a \not \in S$.
Here, the term objects is used loosely. Often, we'll just stick to numbers, but just like our discussion of the domain in logic, these can really be anything: books, trees, other sets, or anything else.
These basic definitions tell us what sets are used for and what we want to know about them. We want to be able to describe collections of things and we want to know whether something belongs to a particular set or not. This is the membership problem: given an item $x$ and a set $S$, is $x \in S$?
Note that since sets are unordered, this means that $\{1,2,3\}$ and $\{3,2,1\}$ are the same set. Furthermore, since an element is either a member or not a member of a set, each element occurs in a set at most once. This means that $\{2,1,3,2\}$ is really just $\{1,2,3\}$.
The set $\{\}$ containing no elements is the empty set and is denoted by $\emptyset = \{\}$.
In light of the above remark about objects in sets, note that $\{\emptyset\}$ is not the same as $\emptyset = \{\}$. The set $\{\emptyset\}$ is actually the set containing the empty set, which means it is not empty; it contains one element: the empty set.
Since we want to be able to describe collections, we need to talk about how to define sets. There are two common ways. First, we can just list the elements of the set, like $\{1, 2, 3\}$. This is easy to do for finite sets. For infinite sets, we can do something like $\{1, 2, 3, \dots\}$ and usually, that's enough for us to understand that this is the set containing all natural numbers.
For more complicated definitions, we define sets using comprehensions, also called set-builder notation. We have already seen an example of this.
The set $\{am + bn \mid a,b \in \mathbb Z\}$ from the proof of Bézout's identity is based on given integers $m$ and $n$. This reads as our set containing items of the form $am + bn$, where $a$ and $b$ are integers.
Similar to what we did above, if we wanted to define the set of even natural numbers, we can write something like $\{2,4,6,\dots\}$. Using comprehensions, we can also write $$\{n \in \mathbb N \mid \exists m \in \mathbb N, n = 2 \cdot m \},$$ which says that we want the set of all natural numbers $n$ such that $n$ can be expressed as $2 \cdot m$ for some natural number $m$. That, of course, turns out to be the even natural numbers.
Some notational issues you may have noticed. I've said before that in logical sentences that we typically don't write things like $\exists n \in \mathbb Z, a \cdot n = b$, but this seems to be exactly what we did above. This is because we're not really working in logic anymore—we're doing set theory. In this context, we do use this shorthand because it's not as clear what the domain should be and we do have a notion of what sets actually are now.
By the way, this is where the idea of comprehensions in Python come from—notice the syntax is not so different.
{n for n in ℕ if n % 2 == 0}(Obviously, this code doesn't work because ℕ isn't anything that's defined. Of course, you can define your favourite collection as ℕ since Python supports unicode names. There's also an interesting question of how to represent sets that are infinitely large in Python, which is not straightforward)
We can do more complicated things with this, since there aren't very many hard rules about what kinds of conditions we can or cannot place on our sets. For instance, we can define the set $$\{n \in \mathbb N \mid \exists m \in \mathbb N, (2 \cdot m = n) \wedge (\forall k \in \mathbb N, n \neq k^2) \}.$$ Sometimes, we don't even bother with that level of formality and just write something like $$\{n \in \mathbb N \mid \text{$n$ is even and not a square}\}.$$ This means that we have a lot of power in how we want to define our sets. Something crucial to note here is that definition is not the same as construction—when we define a set, we're not saying that we know how to construct them. In fact, there are many sets that we can define that we can't compute (a truth that is at the root of computer science).
In other words, one can think of set theory, like logic, as being about expression. We use set theory to describe certain structures, but this doesn't necessarily tell us how they're constructed. (This turns out to be an issue, which led to the development of type theory)
For example, here is a useful set for us to work with.
Let $a$ be an integer. We define the set $\operatorname{Div}(a)$ to be the set of divisors of $a$. That is, $\operatorname{Div}(a) = \{d \in \mathbb Z \mid (d \mid a)\}$.
We can consider the set $\operatorname{Div}(6)$. This set contains the divisors of 6, which we can work out easily enough. This means that an equivalent description of the set can be described as $\{1,2,3,6\}$.
Again, definitions of sets are descriptions. We want the set of divisors of $a$. This description doesn't tell us how to construct this set.
This means that we can get into trouble if we're not careful about how we define sets. Bertrand Russell noticed this problem, leading to the following famous example: $$S = \{T \mid T \not \in T\}.$$ If we let something like this happen, then we get to conclude $S \in S \leftrightarrow S \not \in S$, which is very bad if we want mathematics to be consistent (when Russell communicated this to Gottlob Frege, who was trying to formalize mathematics based on set theory, he was quite spooked).
So we can define sets. Recall that the typical question to ask is whether an element is or is not in a set. We can extend this question to talk about how sets are related to one another.
Two sets $A$ and $B$ are equal if and only if they have the same elements. That is, $$A = B \leftrightarrow (\forall x, x \in A \leftrightarrow x \in B).$$
A set $S$ is a subset of $T$, written $S \subseteq T$, when every element of $S$ belongs to $T$. That is, \[S \subseteq T \leftrightarrow \forall x (x \in S \rightarrow x \in T).\] A set $S$ is a proper subset of a set $T$, written $S \subsetneq T$, when $S$ is a subset of $T$ and there exists an element of $T$ which does not belong to $S$.
We can use this to rephrase one of the propositions we've seen before.
Let $a$ and $b$ be integers. Then $a \mid b$ if and only if $\operatorname{div}(a) \subseteq \operatorname{div}(b)$.
You may notice that sometimes $\subset$ is used for proper subset. This works quite nicely with $\subseteq$ meaning subset. However, we'll avoid this particular notation because there are many other mathematicians who use $\subset$ to mean (not necessarily a proper) subset. Instead, we will use $\subseteq$ and $\subsetneq$ to keep things clear.
From the above, we note that by definition, we have $S \subseteq S$ and if $S = T$, we have $S \subseteq T$ and $T \subseteq S$. This second definition gives us an alternate characterization of two sets that are equal. However, if we look at the definitions carefully, they point to a connection between set theory and logic that we'll explore further.
Recall that sets are unordered collections and don't contain multiples of elements. But what if order does matter? We can get there by defining an operation that will allow us to combine sets in a certain way.
The cartesian product of $n$ sets $A_1, A_2, \dots, A_n$, denoted $A_1 \times A_2 \times \cdots \times A_n$ is defined $$A_1 \times A_2 \times \cdots \times A_n = \{(a_1, a_2, \dots, a_n) \mid a_i \in A_i, i = 1, 2, \dots, n\}.$$ We call an element of $A_1 \times \cdots \times A_n$ an $n$-tuple, or a tuple for short. We call 2-tuples (ordered) pairs.
Observe that since tuples are ordered, we have $(a_1, \dots, a_n) = (b_1, \dots, b_n)$ if and only if $a_i = b_i$ for $i = 1, \dots, n$.
As a side note, we claimed earlier that everything in mathematics is just some kind of set, so how would we define tuples using sets? To keep things simple, we'll consider the definition of the pair first. We can define $(x,y)$ to be the set $\{\{x\}, \{x,y\}\}$. In this way, we can distinguish $x$ and $y$ and we have a way to determine the order in which they appear. This definition is due to Kuratowski in 1921. We can then generalize this definition for arity $n \gt 2$.
Everything is a set and it turns out that the definitions of predicates we vaguely danced around earlier are defined much more concretely once we know some set theory. Suppose we have an interpretation $\mathcal I$, which is just what we'll call how we define our domain and the meaning of our predicates. We want to distinguish the symbols from how we're interpreting them, since we can take the same formula made up of the same symbols and apply a different interpretation to them. Don't worry too much about this because we won't be using this again.
First, the domain is a set; let's call it $\mathcal D$. Then we can define a $k$-ary predicate $P$ under our interpretation $\mathcal I$ as a set of $k$-tuples $(a_1, \dots, a_k)$. In other words, $P^\mathcal I \subseteq \mathcal D^k$. Then we can define the following: $$P(x_1, \dots, x_k) = \begin{cases}T & \text{if $(x_1^\mathcal I, \dots, x_k^\mathcal I) \in P^\mathcal I$,} \\ F & \text{if $(x_1^\mathcal I, \dots, x_k^\mathcal I) \not \in P^\mathcal I$.} \end{cases} $$
Suppose we have predicates $E(x)$ for "$x$ is even" and $L(x,y)$ for "$x$ is less than $y$" and our domain is $\mathbb N$. We can define $E$ and $L$ in an interpretation $\mathcal I$ as follows: \begin{align*} E^\mathcal I &= \{n \in \mathbb N \mid \exists m \in \mathbb N, n = 2m\} \\ L^\mathcal I &= \{\langle x,y \rangle \in \mathbb N^2 \mid x \lt y\}. \end{align*}
In other words, we can view set membership as analogous to truth values. Here, we see that for a predicate $P$, we have that $P(x)$ is true iff $x \in P^{\mathcal I}$. This is one reason why set membership is the big question in set theory and points to a correspondence between what we did in logic and set theory. We can do this with more complicated statements. For instance, we can see that a statement in first-order logic like $\forall x (P(x) \rightarrow Q(x))$ can now be interpreted in set theory as $P^{\mathcal I} \subseteq Q^{\mathcal I}$.
To drive the point home, we introduce the boolean set operations.
The union of two sets $S$ and $T$, denoted $S \cup T$ is defined $$S \cup T = \{x \mid x \in S \vee x \in T\}.$$ The intersection of two sets $S$ and $T$, denoted $S \cap T$, is defined $$S \cap T = \{x \mid x \in S \wedge x \in T\}.$$ The complement of a set $S$, written $\overline S$, is the set of all elements not in $S$, $$\overline S = \{x \mid x \not \in S\}.$$
Notice how the definitions of these sets involves some familiar logical connectives. (Also notice that $\rightarrow$ was taken care of by $\subseteq$, which we saw above)
Let $A = \operatorname{Div}(4) = \{1,2,4\}$ and $B = \operatorname{Div}(6) = \{1,2,3,6\}$. Then
Notice here that intersection happens to give us a nice definition for the set of common divisors of two numbers.
Let's explain the last one. We can also define $\overline S$ relative to a universal set $U$ by $\overline S = \{x \in U \mid x \not \in S\}$. If we wanted to get much more formal and delve into the world of axiomatic set theory, we would have to place some conditions on what $U$ can or can't be. However, for our purposes, this is fine and the notion of the universal set corresponds nicely with the notion of the domain from first-order logic.
This means we can translate some equivalences of propositional logic to set theory.
For two sets $A$ and $B$, \begin{align} \overline{A \cup B} &= \overline A \cap \overline B, \\ \overline{A \cap B} &= \overline A \cup \overline B. \end{align}
Another common operation is set difference.
The difference of two sets $S$ and $T$, denoted $S \setminus T$, is defined $$S \setminus T = \{x \mid x \in S \wedge x \not \in T\}.$$
Using this, we can say things like $\overline S = U \setminus S$ where $U$ is a universe. This checks out, because by defintiion, we have $$U \setminus S = \{x \mid x \in U \wedge x \not \in S\}.$$
Let's see a proof involving sets.
For all sets $A$ and $B$, $A \setminus B = A \cap \overline B$.
This proposition says that set difference can be expressed via more typical boolean set operations. This seems pretty obvious if you consider the definition for a moment. This is analogous to the idea that you only need a handful of boolean operations, whether in set theory or logic, to say everything you would want to say about sets/propositions.
Since we need to show equality, we use double set inclusion to prove this. Recall that set inclusion is analogous to implication and equality is analogous to "if and only if" or equivalence. So a double inclusion proof is really the set theoretic version of an "iff" proof.
First, we will show that $A \setminus B \subseteq A \cap \overline B$. Let $x \in A \setminus B$ be an arbitrary element. Then $x \in A$ and $x \not \in B$. Since $x \not \in B$, we have $x \in \overline B$. Therefore, $x \in A$ and $x \in \overline B$, so $x \in A \cap \overline B$. Since $x$ was arbitrary, we have $A \setminus B \subseteq A \cap \overline B$.
Now, we show that $A \cap \overline B \subseteq A \setminus B$. We let $x \in A \cap \overline B$ be an arbitrary element. Then $x \in A$ and $x \in \overline B$. But $x \in \overline B$ means that $x \not \in B$. So $x \in A$ and $x \not \in B$. But this is the definition of set difference, so $x \in A \setminus B$. Therefore, $A \cap \overline B \subseteq A \setminus B$.
Therefore, $A \setminus B = A \cap \overline B$.
To lead into the next section on modular arithmetic, let's go back to the discussion of predicates and set theory. We can view binary predicates as a special case of something we've seen a lot in math.
A relation $R$ with domain $X$ and co-domain $Y$ is a subset of $X \times Y$.
Typically, we think of relations, say $x \sim y$, as operations that tell us about something $x$ and $y$. However, the set theoretic definition of a relation is just a subset of the cartesian product of some sets, so it is a set of pairs of items. Specifically, it's the set of all pairs of items that make the relation "true".
The comparisons that we use, like $=, \neq, \lt$ and so on are really relations! For example, we can define $=$ on the integers as the relation \[= = \{(a,a) \mid a \in \mathbb Z\}.\] This looks kind of goofy because we're not used to thinking of $=$ as a name of something and because we tend to use $=$ infix. If we give equality a name like $\operatorname{eq}$, then we would write things like \[\operatorname{eq} = \{(a,a) \mid a \in \mathbb Z\}\] and we would write $x = y$ as $\operatorname{eq}(x,y)$ or $(x,y) \in \operatorname{eq}$. And to keep hammering this point home, this set is a description of things that are equal but it doesn't tell us how to determine this.
More relevant is the idea that divisibility is a relation. We can define this in the following way \[\mid = \{(a,b) \mid \exists n \in \mathbb Z, a \cdot n = b\}.\]
We proved earlier in a discussion that divisibility is transitive: that $a \mid b \wedge b \mid c \rightarrow a \mid c$. Transitivity is a property of relations.
We say that a relation $R$ is transitive if for all elements $a, b, c$, that $(a,b) \in R$ and $(b,c) \in R$ implies that $(a,c) \in R$.
Alternatively, we can write things like \[\forall a,b,c (R(a,b) \wedge R(b,c) \rightarrow R(a,c))\] or \[\forall a,b,c (aRb \wedge bRc \rightarrow aRc)\] where we pretend $R$ is an infix operator for our relation.