CMSC 27100 — Lecture 13

Sets

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.

We very briefly introduced the idea of sets earlier when discussing modular arithmetic. They were a nice way to describe "collections" of things. However, they are much more than that. Modern mathematics happens to be built on the idea that everything is a set. Everything. Functions? Sets. Numbers? Sets. Problems? Sets.

Even before our formal introduction to them, we've also already seen sets sneak into our discussions a few times.

• We refer to the natural numbers $\mathbb N$ as a set.
• When discussing the domain of discourse in logic, we refer to the domain as a set of items.

Recall the following definition.

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 the main thing we want to know is whether some thing belongs to a particular set or not. This is the membership problem: given an item $x$ and a set $S$, is $x \in S$?

At first, it seems kind of trivial to determine whether something is in a set or not, but we'll see that because of how we can define sets, this turns out to be kind of an ur-problem—because set theory is so fundamental, you can formulate any mathematical problem as a question of set membership. We'll see that this has consequences, particularly for computer science.

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.

Here are some more sets you may have seen before.

Here, we introduce some notation for more complicated definitions. We can define sets using comprehensions, also called set-builder notation.

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. The answer here is that you'd need to represent such a set using an iterator, which is necessarily computational rather than just descriptive.)

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.

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.

Consider the set $\{n \in \mathbb N \mid \exists a,b,c \in \mathbb N, a^n + b^n = c^n \wedge a,b,c \gt 0 \wedge n \geq 3 \}$. For hundreds of years, it was not known which elements were members of this set or even whether there was anything in here. This raises a few important points: just because you have a definiton doesn't mean that it's easy to tell whether there are any elements that satisfy that definition. Showing that an item is or isn't a member of a set requires proof.

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$.

Consider the sets $A = \{a,c\}$ and $B = \{a,\Box,3,c\}$. We have $A \subseteq A$ and $A \subseteq B$ but $B \not \subseteq A$.

Here's a proposition about divisors. Suppose $a$ and $b$ are integers. Then $a \mid b$ if and only if every divisor of $a$ is a divisor of $b$. We can rephrase this using sets: $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.

In this class, we will use $\subseteq$ for subset. If you must, use $\subsetneq$ for proper subset. But I would recommend never relying only on notation for this—it is good practice to mention explicitly when you are considering a proper subset.

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. And if we look at the definitions carefully, they point to a connection between set theory and logic that we'll explore further.

Set operations

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}(4) = \{1,2,4\}$ and $B = \operatorname{Div}(6) = \{1,2,3,6\}$. Then

• $A \cup B = \{1,2,3,4,6\}$,
• $A \cap B = \{1,2\}$,
• $\overline A = \mathbb N \setminus \{1,2,4\}$,

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.

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\}.$$

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\}.$$

We observe that having we can try to translate some statemenets 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.

Products and tuples

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]

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}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}$.

Relations

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 how we 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}$. 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.

We can 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:

1. Reflexivity: $\forall a \in S, (a,a) \in R$.
2. Symmetry: $\forall a,b \in S, (a,b) \in R \rightarrow (b,a) \in R$.
3. Transitivity: $\forall a,b,c \in S, (a,b) \in R \wedge (b,c) \in R \rightarrow (a,c) \in R$.

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

• total if $\forall a \in A, \exists b \in B, (a,b) \in R$. That is, the relation is defined on every element in the domain.
• single-valued if $\forall a \in A, \forall b_1, b_2 \in B, (a, b_1) \in R \wedge (a,b_2) \in R \rightarrow b_1 = b_2$. That is, the relation associates each element in the domain with one element in the co-domain.

Let $A = \{\Box, \triangle, \bigcirc \}$ and $B = \{1,3,5\}$.

• The relation $\{(\Box, 3), (\Box, 5)\}$ is not total (not every element of $A$ participates) and it is not single-valued ($\Box$ is paired with two values).
• The relation $\{(\Box, 3), (\Box, 5), (\triangle, 1), (\bigcirc, 1)\}$ is total (every element of $A$ participates) and it is not single-valued ($\Box$ is paired with more than one value).
• The relation $\{(\Box, 3), (\bigcirc, 3)\}$ is not total ($\triangle$ doesn't participate) but it is single-valued (every element of $A$ is paired with only one value).
• The relation $\{(\Box, 3), (\triangle, 1), (\bigcirc, 3)\}$ is both total and single-valued.

The kinds of relations that we will be discussing are those that are both total and single-valued. These relations are called functions