Set Theory
In this document, we will give a brief introduction to the theory at the core of mathematics: set theory. This theory studies the notion of a set, its properties and the operations that can be defined on it. Set theory is inherently axiomatic; that is, it is defined through a collection of primitive postulates called axioms, which are taken as the starting assumptions of the theory.
Throughout this guide, we will introduce the foundation of set theory, its operations and some of its most important results.
Set
Let’s start by its definition:
A set is a collection of distinct objects called elements.
As you can see, the definition is somewhat informal: the notion of a collection is not itself defined here in terms of more primitive concepts. This is because, rather than attempting to give a complete definition of what a set “really is”, we take the notion of a set as a primitive and describe its properties through axioms.
There are essentially two common ways of defining a set: by enumerating its elements or by describing a property shared by the elements of the set. An example of the latter is:
$$ \{ n \in \mathbb{N} \mid 1 \leq n \leq 5 \} $$
The resulting set contains every natural number between one and five. In other words, the previous set is equivalent to the one below:
$$ \{ 1, 2, 3, 4, 5 \} $$
There is a special set called the empty set (denoted by $\emptyset$) that contains no elements. This set is unique.
Belonging
In the previous section, we used the symbol $\in$ without explaining its meaning. This symbol means "[…] is an element of" and it’s used to express that a certain object belongs to a set. In other words:
An object $a$ belongs to a set $A$ if it is an element of $A$.
In that case, we write $a \in A$. Just like before, the notion of belonging is taken as primitive in axiomatic set theory. Its properties are determined by the axioms of the theory.
If a certain object $a$ does not belong to a set $A$, we use the following notation instead: $$ a \notin A $$
Inclusion
Let $A$ and $B$ be two sets. We say that $A$ is included in $B$ if every element of $A$ is also an element of $B$.
When a set $A$ is included in $B$, we say that $A$ is a subset of $B$. We can distinguish between two kind of inclusion:
- Non-strict inclusion: every element of $A$ is also an element of $B$. In this case, we write $A \subseteq B$;
- Proper inclusion: every element of $A$ is also an element of $B$, but the two sets are not equal; that is, there exists at least one element of $B$ which is not an element of $A$. In this case, we write $A \subset B$.
Thus, we can state that for every set $A$: $$ A \subseteq A $$
Moreover, if $A \neq \emptyset$, then:
$$ \emptyset \subset A $$
Belonging versus inclusion
It is worth noting the difference between the concept of belonging and the concept of inclusion, since the two relations are not the same.
The former is a property of an element and a set, while the latter is a relation between two sets. Therefore, we can say that
$$ 5 \in \mathbb{N} $$
but not that
$$ 5 \subset \mathbb{N} $$
The latter statement is not false; rather, it is not meaningful. A proposition that does make sense while being false is the following:
$$ \sqrt{-1} \in \mathbb{R} $$
Another example:
$$ \{ 4, 5 \} \subset \{ 1, 2, 3, 4, 5 \} $$
This proposition does make sense and is also true.
Set operations
Let’s now look at some of the fundamental operations that we can perform on two given sets. For the rest of this guide, we will graphically represent sets using circles.
Union
Given two sets $A$ and $B$, their union ($\cup$) is the set formed by the elements that belong to $A$, to $B$ or to both.
That is:
Let’s look at an example:
$$ A = \{ 1, 2, 3 \}, \ \ B = \{ 1, 3, 5 \}, \\ A \cup B = \{ 1, 2, 3, 5 \} $$
As you can see, duplicate elements get included only one time in the resulting set.
Intersection
Given two sets $A$ and $B$, their intersection ($\cap$) is the set formed by the elements that belong to both $A$ and $B$.
That is:
For example:
$$ A = \{ 1, 2, 3 \}, \ \ B = \{ 1, 3, 5 \}, \\ A \cap B = \{ 1, 3 \} $$
Difference
Given two sets $A$ and $B$, their difference ($\setminus$) is the set formed by the elements that belong to $A$ but not to $B$.
That is:
For example:
$$ A = \{ 1, 2, 3 \}, \ \ B = \{ 1, 3, 5 \}, \\ A \setminus B = \{ 2 \} $$
Cartesian product
Given two sets $A$ and $B$, their cartesian product ($\times$) is the set formed by the ordered pairs $(a,b)$ where $a \in A$ and $b \in B$. In other words:
$$ A \times B := \{ (a,b) \mid a \in A, b \in B \} $$
For example:
$$ A = \{ 1,2 \}, \ \ B = \{ 3, 4 \}\\ A \times B = \{ (1,3),(1,4),(2,3),(2,4) \} $$
More generally:
$$ A_1 \times \dots \times A_n \{(a_1,\dots,a_n) \mid a_i \in A_i,\ 1 \leq i \leq n\} $$
Cardinality
The cardinality of a given set is a number that measures its “size”; that is, the number of elements it contains. Given a finite set $A$, we denote its cardinality with $|A|$.
For example:
$$ A = \{ 1, 2, 3, 4,5 \}, \ \ |A| = 5 $$
For infinite sets, instead, cardinality cannot be represented by an ordinary natural number. Instead, we use cardinal numbers (first, second, third, etc.) to distinguish between different sizes of infinity. For instance, the set $\mathbb{N}$ of all natural numbers has cardinality:
$$ | \mathbb{N} | = \aleph_0 $$
We denote this order of infinity using the Hebrew letter $\aleph$ (aleph) with the number $0$ and we read it as ‘aleph-null’.
Countably infinite sets
Not every infinite set has the same cardinality and thus we can distinguish between different orders of infinity. As we saw, the smallest infinite cardinality is $\aleph_0$. In particular, an infinite set has cardinality $\aleph_0$ if there exists a bijection between that set ans the set of natural numbers $\mathbb{N}$. That is, there exists a function:
$$ f : A \to \mathbb{N} $$
that is both injective (one-to-one) and surjective (onto).
Intuitively, such a function assigns a distinct natural number to every element of $A$. In this way, the elements of $A$ can be placed in a sequence and enumerated. When such a correspondence exists, we say that the set is countably infinite or simply countable.
Surprisingly enough, we can construct such a correspondence for the set of all integers. Therefore, $\mathbb{Z}$ has the same cardinality as $\mathbb{N}$.
To prove this claim, consider the following bijection $f : \mathbb{N} \to \mathbb{Z}$:
$$ f(n) = \begin{cases} n/2 & \text{if } n \text{ is even}, \\ -(n+1)/2 & \text{if } n \text{ is odd}. \end{cases} $$
This produces the sequence:
$$ 0,-1,1,-2,2,-3,3,\dots $$
and therefore establishes a one-to-one correspondence between $\mathbb{N}$ and $\mathbb{Z}$. Thus:
$$ |\mathbb{Z}| = |\mathbb{N}| = \aleph_0 $$
Cardinality of the set of countable ordinals
Besides $\aleph_0$, there are other aleph numbers used to represent different cardinalities. The next cardinality after $\aleph_0$ is $\aleph_1$, which is defined as the cardinality of the set of all countable ordinals, which is in turn denoted by the ordinal $\omega_1$. This ordinal is the first uncountable ordinal.
Thus, $\aleph_1$ is the smallest uncountable cardinality and, by definition, the smallest cardinality strictly greater than $\aleph_0$.
From here, we could dive into a very deep rabbit hole, but for the purpose of this guide, we will stop here.
Cardinality of the set of real numbers
The set of real numbers $\mathbb{R}$ has a cardinality which is strictly greater than the cardinality of the set of natural numbers $\mathbb{N}$. This is not merely because there are infinitely many real numbers between any two distinct real numbers: the rational numbers $\mathbb{Q}$ have the same property while still being countable. Instead, Cantor’s diagonal argument shows that there is no bijection between $\mathbb{N}$ and $\mathbb{R}$. In other words, $\mathbb{R}$ is uncountable.
In particular, the set $\mathbb{R}$ has the same number of elements as the power set (i.e., the set of all subsets of a given set) of $\mathbb{N}$. We can easily see that for a finite set with $n$ elements, the power set contains exactly $2^n$ elements; this is because for each element, we have two choices when constructing a subset: either include it or not. The analogous result for infinite sets is expressed in terms of cardinal arithmetic. Therefore:
$$ |\mathcal{P}(\mathbb{N})| = 2^{\aleph_0} $$
Since $\mathbb{R}$ and $\mathcal{P}(\mathbb{N})$ have the same cardinality, we define the cardinality of the continuum as:
$$ \mathfrak{c} = |\mathbb{R}| = 2^{\aleph_0} > \aleph_0 $$
And if we assume the continuum hypothesis (which states that there is no cardinality strictly between $\aleph_0$ and $\mathfrak{c}$), then we can write:
$$ \mathfrak{c} = \aleph_1 $$
Last but not least, let’s briefly talk about Cantor’s theorem, which allows us to establish that the cardinality of the continuum is strictly greater than $\aleph_0$. This theorem states that for every set $A$, its power set has strictly greater cardinality than $A$:
$$ |A| < |\mathcal{P}(A)| $$
Applying Cantor’s theorem to $\mathbb{N}$ gives:
$$ \aleph_0 < 2^{\aleph_0} $$
which proves that the real numbers have a strictly greater cardinality than the natural numbers. In other words, the set of all natural numbers has a strictly smaller cardinality than its power set. And, as we have seen, the power set of $\mathbb{N}$ has the same cardinality as $\mathbb{R}$.