We'll begin going through operations that we can perform on sets with one that is related to our discussion of tuples from last class.
Definition 3.1. 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.
Definition 3.2. 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\}.$$
Example 3.3. 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} $$
If we recall our predicates $E$ and $L$ from the other day, then we can define (assuming the domain for our interpretation $\mathcal I$ is $\mathbb N$): \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.
Definition 3.4. 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\}.$$
Definition 3.5. 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 = U \setminus 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, 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.
Theorem 3.6 (De Morgan's laws). 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}
There are two approaches to proving that two sets $S$ and $T$ are equal, so we will use one for the top identity and another for the bottom identity. The first and more general method is to show that $S \subseteq T$ and $T \subseteq S$. Then, by definition $S = T$. This mirrors how you would prove an "if and only if" statement. Let's jump back to logic world and recall that an "if and only if" statement is of the form $S$ if and only if $T$ and means that $S \rightarrow T$ and $T \rightarrow S$. The correspondence between sets world and logic world then becomes very obvious.
How does one prove a statement of the form $S \rightarrow T$? We can look to the corresponding inference, $(S \vdash T) \vdash S \rightarrow T)$, rule for a hint. What the first part of the proof says is that we need to show that a proof starting with the premise $S$ can conclude with $T$. Once we can do that, we have shown $\vdash S \rightarrow T$. In standard English mathematical terminology, we assume $S$ and prove $T$ with that assumption. In a formal deduction proof, this would appear as a subproof, kind of like the proof of a lemma.
Now, the second way to show that $S$ and $T$ are equal are to take advantage of the definitions of the operations being performed and to "lift" the corresponding propositional logic equivalences. This is more straightforward than the first method of proving the subset inclusions, but this really only works when your sets are obviously defined by basic set operations. Once you start dealing with more complicated sets, it's often necessary to prove set equality using the first method, which is why it is more general.
Proof. First, we will show that $\overline{A \cap B} = \overline A \cup \overline B$.
We will begin by showing $\overline{A \cap B} \subseteq \overline A \cup \overline B$. Let $x \in \overline{A \cap B}$. Then $x \not \in A \cap B$ by definition. Expressed as a logical statement, this is $\neg(x \in A \cap B)$. By definition of intersection, we have $\neg(x \in A \wedge x \in B)$. Applying De Morgan's laws, we get $\neg(x \in A) \vee \neg(x \in B)$. By definition, this gives us $x \not \in A \vee x \not \in B$. Then by definition of set complement, we have $x \in \overline A \vee x \in \overline B$. Applying the definition of union gives us $x \in \overline A \cup \overline B$. Therefore, $\overline{A \cup B} \subseteq \overline A \cap \overline B$.
Next, we will show $\overline A \cup \overline B \subseteq \overline{A \cap B}$. Let $x \in \overline A \cup \overline B$. By definition of union, this means $x \in \overline A \vee x \in \overline B$. By definition of set membership, this means $x \not \in A \vee x \not \in B$. But this is just the negation of membership, so this means $\neg (x \in A) \vee \neg (x \in B)$ and by applying De Morgan's laws, we have $\neg(x \in a \wedge x \in B)$. By definition of intersection, we get $\neg(x \in A \cap B)$ and by definition of negation, we have $x \not \in A \cap B$. But this is $x \in \overline{A \cap B}$ by definition of complement. Thus, we have shown $\overline A \cup \overline B \subseteq \overline{A \cap B}$.
We have shown $\overline{A \cup B} = \overline A \cap \overline B$.
Now, we will show that $\overline{A \cup B} = \overline A \cap \overline B$. We have \begin{align*} \overline{A \cup B} &= \{x \mid x \neq A \cup B\} &\text{definition of complement} \\ &= \{x \mid \neg(x \in A \cup B)\} &\text{definition of set membership} \\ &= \{x \mid \neg(x \in A \vee x \in B)\} &\text{definition of union} \\ &= \{x \mid \neg(x \in A) \wedge \neg(x \in B)\} &\text{De Morgan's laws} \\ &= \{x \mid x \not\in A \wedge x \not\in B\} &\text{definition of set membership} \\ &= \{x \mid x \in \overline A \wedge x \in \overline B\} &\text{definition of complement} \\ &= \{x \mid x \in \overline A \cap \overline B\} &\text{definition of intersection} \\ &= \overline A \cap \overline B &\text{set definition} \\ \end{align*} $$\tag*{$\Box$}$$
As mentioned before, many of the logical equivalences from Definition 1.8 can be proved similarly and would make good exercises.
Definition 3.7. 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\}.$$
Since we've found corresponding operations for each of our four logical connectives, there is obviously not a direct analogue for set difference. However, some manipulation of logical formulas may lead to another interesting correspondence.
Theorem 3.8 (Inclusion-Exclusion). 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.
Definition 3.9. We say two sets $S$ and $T$ are disjoint if $S \cap T = \emptyset$.
Lemma 3.10. 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.
Definition 3.11. Let $A_i$ be a family of sets, with $1 \leq i \leq n$. We define \begin{align*} \bigcup_{i=1}^n A_i &= A_1 \cup A_2 \cup \cdots \cup A_n, \\ \bigcap_{i=1}^n A_i &= A_1 \cap A_2 \cap \cdots \cap A_n. \\ \end{align*}
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.
Definition 3.12. 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.
Definition 3.13. 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.
Definition 3.14. 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.
Definition 3.15. 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.$$
Example 3.16. 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$.
Definition.3.17. 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.
Definition 3.18. A function $f:A \to B$ is onto or surjective if $\forall y \in B, \exists x \in A, f(x) = y$.
Example 3.19. 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.
Let's consider the idea of inverses of functions. At first glance, this seems pretty easy, since all we need to do is "work backwards". If we look at a relation $R \subseteq A \times B$, we can do this pretty easily by defining $$R^{-1} = \{(b,a) \in B \times A \mid (a,b) \in R\}.$$ We run into a problem very quickly if we want to do this with functions: the relation that we get by applying this trick to functions doesn't need to be a function! Instead, we define what are called one-sided inverses. To do this, we return to the world of relations to define an operation.
Definition 3.20. If $R \subseteq A \times B$ and $S \subseteq B \times C$, then the join of $R$ and $S$ is a relation on $A \times C$, $$S \circ R = \{(a,c) \in A \times C \mid \exists b \in B, (a,b) \in R \wedge (b,c) \in S\}.$$ Since functions are relations, we can define joins on functions as well. It turns out that this is really just function composition: if you have functions $f:A \to B$ and $g: B \to C$, then the join of the two functions when viewed as a relation gives us the composition of the functions $g \circ f: A \to C$. That brings us to the following definition for inverses.
Definition 3.21. Consider a function $f:A \to B$. Then the function $g:B \to A$ is a left inverse of $f$ if $\forall x \in A, g(f(x)) = x$. Similarly, $g$ is a right inverse of $f$ if $\forall y \in B, f(g(y)) = y$.
Typically, the left inverse is the one we think of as "the" inverse of a function, so we drop the "left" when the context is clear.
Definition 3.22. 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$.