1.1 Set theory

A set, informally, is a collection of (mathematical) objects. The objects in a set are called its elements, and we write sets down by listing or describing their elements surrounded with $\{$curly brackets$\}$. For example, the set whose elements are 1,2 and 3 is written $\{1,2,3\}$, and from MATH0003 Analysis 1 you should already be familiar with set-theoretic notation like

\[ \{ x \in \mathbb{R}: x < 0\} \]

meaning the set of all strictly negative real numbers. Often you’ll see a $|$ instead of a : in this ‘set builder notation’, it means the same thing.

One of the amazing things about set theory is that absolutely everything you study in an undergraduate maths degree - whole numbers, real numbers, complex numbers, functions, relations, groups, rings, vectors, matrices, sequences, and so on - can be built starting with the empty set and the axioms of set theory. This is what people mean when they call set theory a foundation for mathematics. As an example, a common way to represent the natural numbers 0,1,2,… as sets is

\[ \emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\},\ldots \]

In MATH0007 however we are going to keep things simple - instead of giving a formal set-theoretic definition of a function, for example, we’ll be happy with an informal description in terms of a rule for mapping one set to another. If you want to learn about formal set theory, (Goldrei 2017) is a fantastic book for self-study and very easy to read.

1.1.1 Set terminology

Definition 1.1 Let A and B be sets.

$x \in A$ means that x is an element of A, and $x\notin A$ means x is not an element of A.
$A \subseteq B$ means every element of A is also an element of B. In this case we say A is a subset of B or A is contained in B.
$A=B$ means $A \subseteq B$ and $B \subseteq A$.
$A \not\subseteq B$ means A is not a subset of B.
$A \subsetneq B$ means A is a subset of B but $A \neq B$. In this case we say A is a proper subset of B.

The definition of equality of sets means that two sets A and B are equal if and only if every element of A is an element of B, and every element of B is an element of A. This has two important consequences. Firstly, for example, \[ \{1,2\} = \{2,1\} \] since every element of $\{1,2\}$ is an element of $\{2,1\}$ and vice versa. So order doesn’t matter for sets. Secondly \[ \{1,2,1\} = \{1,2\} \] — again, the only things that are elements of the set on the left are 1 and 2, the only things that are elements of the set on the right are 1 and 2, so the two sets are equal. For sets, repetition doesn’t matter. This is why we can use sets to reason about unordered collections of objects without repetition.

If A has exactly n distinct elements we write $|A|=n$ and call n the size or cardinality of A. For example, \[|\{1,2\}|=2, |\{1,2,1,3\}|=3.\]

The empty set, written $\emptyset$, is the set with no elements. Therefore $|\emptyset|=0$.

We often use set builder notation (or set comprehension) to describe sets. This is best described with an example. If $\mathbb{N}$ is the set $\{0,1,2,\ldots\}$ of natural numbers, then

\[ \{x \in \mathbb{N} : x < 100\}\]

means ‘the set of all natural numbers which are less than 100’, and

\[ \{x \in \mathbb{N} : \exists p,q \in \mathbb{N} : x = p^2 + q^2\}\]

means ‘the set of all natural numbers which can be written as the sum of two squares.’ Sometimes in set builder notation people use a $|$ instead of a $:$, the meaning is exactly the same.

1.1.2 Combining sets

There are several important ways of combining two (or more) sets.

Definition 1.2 Let A and B be sets:

The union or join of A and B, written $A \cup B$, is $\{x : x \in A \text{ or } x \in B\}$.
The intersection or meet of A and B, written $A \cap B$, is $\{ x : x \in A \text{ and } x \in B\}$.
Two sets A and B are called disjoint if $A \cap B = \emptyset$.
The set difference $A \setminus B$ is $\{x \in A : x \notin B\}$.
If A is a subset of a fixed ‘universe’ $\Omega$, we call $\Omega \setminus A$ the complement of A in $\Omega$ and write it as $A^c$.

Mathematical “or” is always inclusive, so the definition of $A \cup B$ means that it contains everything which is in A, or B, or in both. For example, $\{1,2\}, \cup \{2,3\} = \{1,2,3\}$.

$A \setminus B$ is often pronounced “A take B.”

$Venn diagram for $A\cup B$. Two overlapping circles labelled *A* and *B* represent the sets *A* and *B*. The whole area of both circles is shaded, representing the fact that $A\cup B$ consists of everthing which is either in *A*, or in *B*, or both.$

Figure 1.1: Venn diagram for $A\cup B$. Two overlapping circles labelled A and B represent the sets A and B. The whole area of both circles is shaded, representing the fact that $A\cup B$ consists of everthing which is either in A, or in B, or both.

$Venn diagram for $A\cap B$. Two overlapping circles labelled *A* and *B* represent the sets *A* and *B*. The area where the circles overlap is shaded, representing the fact that $A\cap B$ consists of everthing which is simultaneously in *A* and in *B*.$

Figure 1.2: Venn diagram for $A\cap B$. Two overlapping circles labelled A and B represent the sets A and B. The area where the circles overlap is shaded, representing the fact that $A\cap B$ consists of everthing which is simultaneously in A and in B.

$Venn diagram for $A\setminus B$. Two overlapping circles labelled *A* and *B* represent the sets *A* and *B*. That part of *A* which does not overlap with *B* is shaded, representing the fact that $A\setminus B$ consists of everthing which is in *A* but not in *B*.$

Figure 1.3: Venn diagram for $A\setminus B$. Two overlapping circles labelled A and B represent the sets A and B. That part of A which does not overlap with B is shaded, representing the fact that $A\setminus B$ consists of everthing which is in A but not in B.

Venn diagram for $A^c$. Two overlapping circles labelled *A* and *B* represent the sets *A* and *B*. Everything outside *A* is shaded, representing the fact that $A^c$ is everything which is not in *A*.

Figure 1.4: Venn diagram for $A^c$. Two overlapping circles labelled A and B represent the sets A and B. Everything outside A is shaded, representing the fact that $A^c$ is everything which is not in A.

As practise in using the definition of set equality, let’s prove a simple result about complements:

Lemma 1.1 Let A be a subset of a set $\Omega$. Then $(A^c)^c = A$.

To prove two sets X and Y are equal we often use the definition of set equality: to check X = Y first we show $X \subseteq Y$ and then we show $Y \subseteq X$. To prove $X \subseteq Y$ we show that any $x \in X$ is also in Y, and to prove $Y \subseteq X$ we show any $y \in Y$ is also in X.

Proof. First we’ll show $A \subseteq (A^c)^c$. Let $a \in A$. Then $a \notin A^c$ by definition of complement, so $a \in (A^c)^c$ again by the definition of complement.

Now let $x \in (A^c)^c$. Then $x \notin A^c$, so $x \in A$.

1.1.3 Laws for union and intersection

It’s useful to write down some results about how $\cup$, $\cap$, and $\setminus$ interact with each other. The first result is called De Morgan’s laws:

Theorem 1.1 Let A and B be subsets of a set $\Omega$. Then

$(A\cup B)^c = A^c \cap B^c$, and
$(A \cap B)^c = A^c \cup B^c$.

Before we prove this, here are two figures illustrating De Morgan’s laws. In the first you should notice that the shaded area, which is everything outside $A \cup B$, could also be obtained by colouring those parts of the diagram which are not part of A and not part of B. In the second you see that the shaded area, which is everything outside $A \cap B$, could also be obtained by colouring everything which is either not part of A or not part of B.

$Venn diagram for $(A\cup B)^c$. Two overlapping circles represent the sets *A* and *B*. The area outside the two circles, representing the complement of $A\cup B$, is shaded.$

Figure 1.5: Venn diagram for $(A\cup B)^c$. Two overlapping circles represent the sets A and B. The area outside the two circles, representing the complement of $A\cup B$, is shaded.

$Venn diagram for $(A \cap B)^c$. Two overlapping circles represent the sets *A* and *B*. Everything outside the part where the circles overlap is shaded, representing the complement of $A \cap B$.$

Figure 1.6: Venn diagram for $(A \cap B)^c$. Two overlapping circles represent the sets A and B. Everything outside the part where the circles overlap is shaded, representing the complement of $A \cap B$.

Proof.

1. First we’ll show $(A \cup B)^c \subseteq A^c \cap B^c$. Let $x \in (A \cup B)^c$. Then $x \notin A \cup B$, so $x \notin A$ and $x \notin B$. This means $x \in A^c$ and $x \in B^c$, so $x \in A^c \cap B^c$.

Now we show $A^c \cap B^c \subseteq (A \cup B)^c$. Let $x \in A^c \cap B^c$. Then $x \in A^c$ and $x \in B^c$, so $x \notin A$ and $x \notin B$, so $x \notin A \cup B$. Therefore $x \in (A\cup B)^c$.

We’ve shown $(A \cup B)^c \subseteq A^c \cap B^c$ and $A^c \cap B^c \subseteq (A \cup B)^c$, so $(A \cup B)^c = A^c \cap B^c$.

2. You could prove this in the same way we proved part 1. Alternatively, the previous result with $A^c$ in place of A and $B^c$ in place of B gives $(A^c \cup B^c)^c = A \cap B$, because $A^{cc}=A$ and $B^{cc}=B$ by Lemma 1.1. Taking complements of both sides gives $A^c \cup B^c = (A \cap B)^c$.

De Morgan’s laws can be generalized to unions and intersections of any number (even an infinite number) of sets. For example, we have

\[\begin{align*} (A_1 \cup A_2 \cup \cdots)^c &= A_1^c \cap A_2^c \cap \cdots \\ (A_1 \cap A_2 \cap \cdots)^c &= A_1^c \cup A_2^c \cup \cdots \end{align*}\]

Here is an example, called the Jacobean Locks problem, which shows how using De Morgan’s laws can make it easier to solve problems with sets.

Example 1.1 A group of 5 housemates, fed up of people stealing from the communal fridge, are going to fit a number of locks to the fridge door and distribute the keys amongst them. Each key will work in one and only one lock, but they can make as many copies of each key as they want. They want to do this in such a way that

no group of two housemates can open the fridge, but
any group of three housemates can open the fridge.

How many locks do they need, and how should the keys be distributed?

Suppose the locks on the fridge are numbered 1, 2, …, L, and let $K_i$ be the set of locks which housemate i can open. Let $\Omega = \{1,2,\ldots,L\}$, so every $K_i$ is a subset of $\Omega$. Let $N_i = K_i^c$, so $N_i$ is the set of keys that person i does not have.

Condition 1 means that for every i and every j we must have

\[ K_i \cup K_j \neq \Omega. \]

By taking complements of both sides and using De Morgan’s laws,

\[\begin{align*} (K_i \cup K_j)^c & \neq \Omega ^c \\ K_i^c \cap K_j^c & \neq \emptyset \\ N_i \cap N_j &\neq \emptyset \end{align*}\]

Condition 2 means that for every distinct i, j, and k we have

\[ K_i \cup K_j \cup K_k = \Omega. \]

By taking complements of both sides and using De Morgan’s laws,

\[\begin{align*} (K_i \cup K_j \cup K_k)^c & = \Omega^c \\ K_i^c \cap K_j^c \cap K_k^c &= \emptyset \\ N_i \cap N_j \cap N_j &= \emptyset \end{align*}\]

So if i and j are distinct, we know that $N_i$ and $N_j$ have an element in common (since $N_i \cap N_j \neq \emptyset$) but that this element doesn’t belong to any other $N_k$ (since $N_i \cap N_j \cap N_k = \emptyset$). There must be at least as many locks as there are pairs of distinct numbers i and j.

You should try working out how many pairs of distinct numbers between 1 and 5 there are. For this number of locks, can you find a way of distributing keys that fulfills conditions 1 and 2?

The distributive laws tell us how $\cap$ and $\cup$ interact:

Theorem 1.2 Let A, B, C be sets. Then

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$, and
$A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$.

Proof. 1. Again, we will show that the set on the left is contained in the set on the right and vice versa.

Left $\subseteq$ right: Let $x \in A \cup (B \cap C)$, so that either $x \in A$ or $x \in B\cap C$ (or both!). We’ll do those two cases separately. In the first case, $x \in A$ then $x \in A \cup B$ and $x \in A \cup C$ so $x \in (A\cup B)\cap (A\cup C)$. In the second, $x \in B\cap C$ so $x \in B$, so $x \in A \cup B$, and $x \in C$, so $x \in A \cup C$. It follows $x \in (A \cup B) \cap (A \cup C)$. We’ve proved the left hand side is contained in the right.

Left $\supseteq$ right: suppose $x \in (A\cup B)\cap (A \cup C)$. If $x \in A$ then certainly $x \in A \cup (B \cap C)$, so let’s suppose $x \notin A$. Since $x \in A \cup B$ and $x\notin A$ we must have $x\in B$. Similarly, $x \in C$. So $x \in B \cap C \subseteq A \cup (B\cap C)$. It follows the right hand side is contained in the left.

2. Let $x \in A \cap (B \cup C)$, so $x \in A$ and $x \in B \cup C$, which tells us either $x \in B$ or $x \in C$. In the first case $x \in A \cap B$, and in the second case $x \in A \cap C$. In either case $x \in (A \cap B) \cup (A \cap C)$, so $A \cap (B \cup C) \subseteq (A \cap B) \cup (A \cap C)$.

Now let $x \in (A \cap B) \cup (A \cap C)$, so either $x \in A \cap B$ or $x \in A \cap C$. In either case $x \in B \cup C$, so $x \in A \cap (B \cup C)$. We’ve shown $(A \cap B) \cup (A \cap C) \subseteq A \cap (B \cup C)$, so we’re done.

Lastly, union and intersection have two properties called commutativity and associativity. They follow straight from the definitions, so we will just list them rather than giving a proof:

Let $A,B,C$ be sets.

(commutativity) $A\cup B=B\cup A$, and $A \cap B = B \cap A$.
(associativity) $A \cup (B \cup C) = (A\cup B) \cup C$, and $A \cap (B\cap C) = (A\cap B)\cap C)$.

The associativity property means we can just write $A \cup B \cup C$ without ambiguity — no need for brackets, just like we can write $1+2+3$ without having to specify which order you do the addition in.

1.1.4 Cartesian products

An ordered pair $\langle a,b\rangle$ is something that has the property that

\[\begin{equation} \langle a,b\rangle = \langle c,d\rangle \text{ if and only if } a=c \text{ and } b=c. \tag{1.1} \end{equation}\]

Sometimes people write $(a,b)$ instead of $\langle a, b\rangle$.

It looks like this is some new construction, but in fact we can express it just using set theory: if you define \[ \langle a,b\rangle = \{ \{a\}, \{a,b\}\} \] it is possible to show that it has the defining property (1.1) of ordered pairs.

Given two sets A and B we define their Cartesian product $A \times B$ by \[ A \times B = \{ \langle a,b\rangle : a \in A, b \in B\}.\] If A and B are finite sets then $|A\times B|= |A||B|$.

1.1.5 Sets in Python

You will be learning some Python in the first half of MATH0011. Python has a built-in set datatype which can be constructed using { and }. Try commands like the following:

A = {1, 2, 1}
B = {1, 2}
A == B  # Python will say 'True'
C = {3, 4}
A.union(C)
A.intersection(C)
len(A)  # tells you the size of A
A <= B  # checks if A is a subset of B
A < B   # checks if A is a proper subset of B
{(a, b) for a in A for b in B} # Cartesian product AxB

There’s one snag, which is that you can’t define the empty set as {} (Python interprets this as an empty dictionary, one of its other built-in types). Instead, you need:

emptyset = set()
A = {1, 2}
C = {3, 4}
A.intersection(C) == emptyset  # True

You can even do set builder notation in Python — it’s called ‘set comprehension.’ Try {x ** 2 for x in range(3)}, for example.

1.1.6 Formal set theory

One of the reasons that formal set theory exists (and is complicated) is that if we keep treating sets in this informal manner, we eventually run into problems. For example, let

\[ X = \{ x : x \notin x\}\]

so X is the set of all sets which are not members of themselves. Is $X \in X$? Then $X \notin X$ by the defining property of X, a contradiction. So it must be that $X \notin X$, but then it follows that $X \in X$ again by definition of X - we get a contradiction either way! This is called Russell’s paradox. One way round this is to develop set theory using axioms that are permissive enough to allow us to describe all the mathematics we want to do inside set theory, but restrictive enough to avoid the kind of set-formation that gave rise to Russell’s paradox. The usual system is called Zermelo-Fraenkel set theory, or ZF for short. If you want to know more, a good book is Derek Goldrei’s Classic Set Theory.

References

Goldrei, DC. 2017. Classic Set Theory: For Guided Independent Study. Routledge.