Now that we've defined the language of first-order logic, we can move on to talking about set theory. Modern mathematics happens to be built on the idea that everything is a set. Everything. Functions? Sets. Numbers? Sets. Problems? Sets. Sets? Sets. So, it's important to familiarize ourselves with the basics of sets and how they work.
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$. Similarly, if $a$ is not a member of $S$, then we write $a \not \in S$.
Here, objects is used loosely. Often, we'll just stick to numbers, but these can really be anything: books, trees, other sets, or anything else.
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.
There are two common ways to define sets. 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.
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.
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. Without any further restrictions on what we can say when defining sets, this puts us in the realm of naive set theory. This system was devised by Georg Cantor and later, Gottlob Frege as part of his quest to formalize a foundation for mathematics.
However, 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 \iff S \not \in S$, which is very bad if we want mathematics to be consistent (when Russell communicated this to Frege, he was quite spooked). This led to the development of axiomatic set theory. For our purposes, we won't need to delve into axiomatic set theory, but it is important to note that when we talk about set theory being the basis of all mathematics, what we really mean is the axiomatic set theory.
Two sets $A$ and $B$ are equal if and only if they have the same elements. That is, $$A = B \iff (\forall x, x \in A \iff x \in B).$$
A set $S$ is a subset of $T$, written $S \subseteq T$, when every element of $S$ belongs to $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$.
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.
The cardinality of a set $S$ is the number of elements in $S$ and is denoted $|S|$. If $S$ is finite, then this will be a natural number. So, the size of the set $\{1,2,4,8\}$ would be $|\{1,2,4,8\}| = 4$.
If $S$ is an infinite set, then things are a bit trickier. The cardinality of the natural numbers is defined to be $|\mathbb N| = \aleph_0$, while the cardinality of the real numbers is $|\mathbb R| = 2^{\aleph_0}$. Here, we reach into the Hebrew alphabet for $\aleph$ (aleph). Anyhow, the cardinalities of $\mathbb N$ and $\mathbb R$ are clearly not the same, a fact famously proved by Cantor in 1891. There are many infinite sets that have cardinality $\aleph_0$, such as the set of even natural numbers $\{n \mid \exists m \in \mathbb N, n = 2\cdot m\}$ or the set of rational numbers $\mathbb Q = \{\frac m n \mid \exists m,n \in \mathbb N\}$. There are also many sets with cardinality $2^{\aleph_0}$. This brings us to a fun problem for you to think about in your spare time: are there any infinite sets that have cardinality strictly between $|\mathbb N| = \aleph_0$ and $|\mathbb R| = 2^{\aleph_0}$?
The power set of a set $A$ is the set containing all of the subsets of $A$, $$\mathcal P(A) = \{S \mid S \subseteq A\}.$$
If $A$ is a finite set, then $|\mathcal P(A)| = 2^{|A|}$.
We will prove this later, in a few ways. However, because of this fact, you'll sometimes see the power set of a set $A$ denoted by $2^A$. This also gives you some insight about why it might be that $|\mathbb R| = 2^{\aleph_0}$.
Recall that sets are unordered collections and don't contain multiples of elements. But what if order does matter? We need to define another structure to work with.
An $n$-tuple $(a_1, a_2, \dots, a_n)$ is an ordered collection that has $a_1$ as its first element, $a_2$ as its second element, $\dots$, and $a_n$ as its $n$th element. An ordered pair is a 2-tuple.
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$.
We'll begin going through operations that we can perform on sets with one that is related to our discussion of tuples.
The cartesian product of two sets $A$ and $B$ is $$A \times B = \{(a,b) \mid a \in A, b \in B\}.$$
We can generalize this to products of $n$ sets.
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\}.$$
Everything is a set and it turns out that the definitions of predicates I vaguely danced around earlier are defined much more concretely once we know some set theory. Suppose I 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*}
This definition actually points to a correspondence between what we did in logic and the set operations we'll now define. In some cases, the correspondence is very obvious because the definitions themselves are taken right from logic.
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\}.$$
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.
So far, we have $\vee, \wedge, \neg$ covered (since $x \not \in S$ is $\neg (x \in S)$), but what about $\rightarrow$? This turns out to be something we defined last class: subset. Recall that $A \subseteq B$ if $\forall x (x \in A \rightarrow x \in B)$. The correspondence is right there in the definition, hiding in plain sight.
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\}.$$
A final important property of sets is to talk about the size of the sets after performing some operations on them. The following is a basic, but important property.
For all finite sets $A$ and $B$, $|A \cup B| = |A| + |B| - |A \cap B|$.
A simple proof of this goes like this: we count all of the elements in $A$ and then count all of the elements of $B$. However, if there are elements in both $A$ and $B$, we've counted them twice, so we have to take out $|A \cap B|$ from our count.
We say two sets $S$ and $T$ are disjoint if $S \cap T = \emptyset$.
If $A$ and $B$ are disjoint sets, then $|A \cup B| = |A| + |B|$.
This is easy to see, since the intersection of $A$ and $B$ is empty.
You may have learned various definitions of what is or isn't a function. Typically, we think of functions in a very calculus kind of way, where we assign a value $x$ to some other value based on some expression like $x^2$. Then, we come across more complicated functions, that are defined piecewise, or maybe weird functions like the Heaviside function or the parity function. Here, we'll make use of the set theory concepts we've just defined to work towards a general definition for functions.
A relation $R$ with domain $X$ and co-domain $Y$ is a subset of $X \times Y$.
We can see from the definition that a relation really is just a subset of the cartesian product of some sets. In other words, it's a set of tuples. This also resembles the set-theoretic definition of predicates from above and it's not entirely a coincidence that we think of $k$-ary predicates as relations.
A relation $R \subseteq A \times B$ is total if $\forall a \in A, \exists b \in B, R(a,b)$. A relation $R$ is single-valued if $\forall a \in A, \forall b_1, b_2 \in B, R(a, b_1) \wedge R(a,b_2) \rightarrow b_1 = b_2$.
These properties lead us right to a definition for functions.
A function $f : A \to B$ is a total, single-valued relation with domain $A$ and co-domain $B$. The set $B$ is also called the range of $f$.
Again, based on the definition, a function is really just a relation that satisfy the properties we just defined, totality and single-valued-ness. And if we go further, a function is just a set, like everything else in mathematics. The restrictions on the domain and co-domain of the function tracks with our intuitive understanding of functions that we may have learned earlier. For instance, totality guarantees that a function gives us something for every value we throw at it, while single-valuedness guarantees that our function will only give us one possible output for every input that we give it.
We also have different kinds of functions that are important and worth distinguishing.
A function $f:A \to B$ is one-to-one or injective if $$\forall x, y \in A, f(x) = f(y) \rightarrow x = y.$$
The successor function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x+1$ is one-to-one. On the other hand, the function $g:\mathbb N \to \mathbb N$ defined by $g(x) = \left\lfloor \frac x 2 \right\rfloor$ is not one-to-one, since for any even natural number $m$, we have $g(m) = g(m+1)$ but $m \neq m+1$.
The image of a function $f : A \to B$ is the set $\operatorname{im} f = \{f(x) \mid x \in A\}$.
Clearly, $\operatorname{im} f \subseteq \operatorname{rng} f$. However, it is not always the case that $\operatorname{im} f = \operatorname{rng} f$. If it is, we get another special kind of function.
A function $f:A \to B$ is onto or surjective if $\forall y \in B, \exists x \in A, f(x) = y$.
The function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x^2$ is not surjective (for instance, there is no natural number $n$ such that $n^2 = 2$). On the other hand, the function $g(x) = \left\lfloor \frac x 2 \right\rfloor$ from the above example is surjective.
If we combine these two properties, we get an even more special kind of function.
A function $f:A \to B$ is a correspondence or bijection if $f$ is one-to-one and onto.
A correspondence between two sets $A$ and $B$ uniquely pairs each element of $A$ with an element in $B$. This turns out to be how we can determine something like $|\mathbb N| = |2 \mathbb N|$, where $2 \mathbb N$ is the set of even natural numbers. The correspondence from $\mathbb N$ to $2 \mathbb N$ is very simple: it's the function defined by $f(n) = 2n$. Since a correspondence pairs each element in the set, both sets must be the same size. If $B$ were smaller than $A$, then $f$ couldn't be one-to-one, and if $B$ were larger than $A$, then $f$ couldn't be onto. This turns out to be how Cantor shows that $|\mathbb R| \gt |\mathbb N|$, by showing that there are real numbers that would be "missed" by any function that one claimed to be a correspondence from $\mathbb N$ to $\mathbb R$.