Our motivation for sets is about how to def
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}(36) = \{1, 2, 3, 4, 6, 9, 12, 18, 36\}$ and $B = \operatorname{Div}(32) = \{1, 2, 4, 8, 16, 32\}$. Then
Notice here that intersection happens to give us a nice definition for the set of common divisors of two numbers.
Python sets have the same operations available to them via shorthand.
>>> div = lambda a: {d for d in range(1,a+1) if a % d == 0}
>>> A = div(36)
>>> B = div(32)
>>> A, B
({1, 2, 3, 4, 6, 9, 12, 18, 36}, {1, 2, 4, 8, 16, 32})
>>> A | B # union
{1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 32, 36}
>>> A & B # intersection
{1, 2, 4}
Complement is a bit difficult to deal with.
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 dive 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 then to say that we want the set of elements not in a set $S$ is to say that we want the set of elements in the universe except those in $S$, hence the difference of the two sets.
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\}.$$
Let $A = \operatorname{Div}(36)$ and $B = \operatorname{Div}(32)$. Then
>>> A - B
{3, 6, 9, 12, 18, 36}
>>> B - A
{8, 16, 32}
Something you might notice about the difference operation is that you really could have just expressed it by using intersection and complement.
Using this, we can say things like $\overline S = U \setminus S$ where $U$ is a universe. This checks out, because by definition, we have $$U \setminus S = \{x \mid x \in U \wedge x \not \in S\}.$$
As noted before, expressing an infinite set is not really possible with built-in Python sets. However, there are libraries that allow for this. One popular library for this is SymPy, a symbolic computation system. Such implementations allow us to work with infinite sets without having to explicitly enumerate all objects contained in the set.
>>> from sympy import S, FiniteSet
>>> S.Naturals0 - A
Complement(Naturals0, {1, 2, 3, 4, 6, 9, 12, 18, 36})
>>> 12 in S.Naturals0 - A
False
>>> 17 in S.Naturals0 - A
True
>>> FiniteSet(2,3,6) <= S.Naturals0 - A
False
>>> FiniteSet(11, 17, 230) <= S.Naturals0 - A
True
We observe that having we can try to translate some statements from 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}
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$.
From our discussion above, there seems to be an interesting connection between logic and sets. Recall that we saw with boolean connectives that every boolean “function” can be described using only $\neg$ and one of $\vee$ or $\wedge$. So the boolean set operations that we have are “enough” to express all the usual functions. But where is $\rightarrow$?
It turns out $\rightarrow$ and $\leftrightarrow$ have a more fundamental relationship: as the subset relation and equality. Consider a predicate $\mathsf P$. We can define a set $P$ in the following way: \[P = \{x \mid \text{$\mathsf P(x)$ is true}\}.\] This seems a bit silly, but what we’ve essentially done is we’ve turned the question of whether $\mathsf P(x)$ is true or false into the question of whether $x \in P$ or not. This on its own is not that interesting, but consider how we might express $n$-ary predicates in the same way.
Recall that sets are unordered collections and don’t contain multiples of elements. But for $n$-ary predicates, order does matter. So in order to represent these predicates, we need a new kind of structure to consider. We can get there by defining an operation that will allow us to combine sets in a way in which order matters.
The cartesian product of $n$ sets $A_1, A_2, \dots, 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$.
One way to think about these is as tuples in Python that have the type
tuple[A1,A2,...,An]
Let $A = \operatorname{Div}(4)$, $B = \operatorname{Div}(5)$, and $C = \{-1,1\}$.
>>> from itertools import product
>>> div = lambda a: {d for d in range(1,a+1) if a % d == 0}
>>> A = div(4)
>>> B = div(5)
>>> C = {-1, 1}
>>> product(A, B, C)
<itertools.product at 0x11bc0bd80>
>>> set(product(A, B, C))
{(1, 1, -1), (1, 1, 1), (1, 5, -1), (1, 5, 1), (2, 1, -1), (2, 1, 1),
(2, 5, -1), (2, 5, 1), (4, 1, -1), (4, 1, 1), (4, 5, -1), (4, 5, 1)}
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 really is a set and it turns out that the set theoretic definitions of predicates we just discussed are really how they are defined. 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} \mathsf{True} & \text{if $(x_1^\mathcal I, \dots, x_k^\mathcal I) \in P^\mathcal I$,} \\ \mathsf{False} & \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}$.
Let’s go back to the discussion of predicates and set theory. The fact that we can view predicates as $n$-tuples is not just a neat trick. This is what allows us to formally define relations.
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}$.
If we were working in a finite domain, like $\mathbb Z_3$, then we can even list everything in the set: \[\operatorname{eq}_3 = \{(0,0), (1,1), (2,2)\}.\]
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$, if $(a,b) \in R$ and $(b,c) \in R$ then $(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)) \text{ or } \forall a,b,c (a \mathop R b \wedge b \mathop R c \rightarrow a \mathop R c)\] where we pretend $R$ is an infix operator for our relation.
This allows us to do things like recast our discussion of equivalence relations in set theoretic terms.
A relation $R \subseteq S \times S$ is an equivalence relation if $R$ satisfies the following:
However, there are other kinds of relations we can talk about. First, let’s introduce the following properties that we may want our relations to have.
A relation $R \subseteq A \times B$ is
Let $A = \{\Box, \triangle, \bigcirc \}$ and $B = \{1,3,5\}$.
The kinds of relations that we will be discussing are those that are both total and single-valued. These relations are called functions.
To talk about counting, we need to talk about functions. 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, or maybe functions defined over vectors. Here, we’ll make use of the set theory concepts we’ve just defined to work towards a general 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$.
We can think of addition as a function $+ : \mathbb Z \times \mathbb Z \to \mathbb Z$. So we can view $+$ as a set that contains pairs, where the first component is a pair of integers $(x,y)$ and the second component is the integer $x+y$. For example, $((2,3), 5) \in +$, but $((-3, 9), 4) \not \in +$.
One sees this a bit more clearly in a finite domain like $\mathbb Z_3$. We have \begin{align*} +_3 = \{&((0, 0), 0), ((0, 1), 1), ((0, 2), 2), ((1, 0), 1), ((1, 1), 2), ((1, 2), 3), \\ & ((2, 0), 2), ((2, 1), 3), ((2, 2), 4)\}. \end{align*}
In other words, a function is really just a relation that satisfy the properties we just defined, totality and single-valued-ness. And so 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.
Technically, totality is not a strict requirement for functions—there are such things as partial functions, which aren’t defined for all values of the domain. For example, if $f : \mathbb R \to \mathbb R$ is defined by $f(x) = \frac 1 x$, then $f$ is not defined at $0$. In our case, we should say that we really care about total functions. This has some consequences in computability theory.
This is important to keep in mind because this goes back to the idea of description versus computation. From this perspective, there is nothing that says when defining a function we have to say how to compute it. This is but another form of the central question of computer science: we are given function definitions and we define algorithms to compute those functions.
Notice that the terminology of functions in programming confuses things—what programming languages call functions are really particular implementations of algorithms that compute functions. Of course, this makes sense because there’s no sense in writing code for a function you can’t compute.
We also have different kinds of functions that are important and worth distinguishing.
A function $f:A \to B$ is injective if $\forall x, y \in A, f(x) = f(y) \rightarrow x = y$. Injective functions are also called one-to-one.
The successor function $\operatorname{succ} :\mathbb N \to \mathbb N$ defined by $\operatorname{succ} (x) = x+1$ is injective. This can also be described as the set \[\operatorname{succ} = \{(0,1), (1,2), (2,3), (3,4), \dots \}\] 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 injective, since for any even natural number $m$, we have $g(m) = g(m+1)$ but $m \neq m+1$. We can also view this as \[\left\lfloor \frac \cdot 2 \right\rfloor = \{(0,0), (1,0), (2,1), (3,1), (4,2), (5,2), \dots\}\]
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 surjective if $\forall y \in B, \exists x \in A, f(x) = y$. Surjective functions are also called onto.
The function $f:\mathbb N \to \mathbb N$ defined by $f(x) = x^2$ is not surjective. To see this, we have \[\cdot^2 = \{(0,0), (1,1), (2,4), (3,9), (4,16), \dots \}\] So for instance, there is no natural number $n$ such that $n^2 = 2$—there’s no pair $(n,2)$ for any $n \in \mathbb N$. 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 bijective or a bijection if $f$ is both injective and surjective. Bijective functions are also called correspondences.