2 Some notes on set theory
In these notes we treat sets rather informally, in the sense that we may set up non-existing sets if we are not careful. Most mathematicians in everyday practice uses the same style of set theory. They are able to avoid pathological examples that may occur by knowing how these examples can occur. Russell’s paradox is one example.
2.1 Sets and their elements
A set is a fundamental concept in mathematics, representing a collection of distinct objects considered as a whole. Here is an example:
\[ S = \{ 1, 2, 3 \} \quad \leftarrow \text{a simple set}. \]
This is the set of the numbers 1, 2, and 3. These numbers are then elements of \(S\):
\[ 1 \in S \quad \leftarrow \text{1 is an element of $S$} \]
However, any other mathematical objects than 1, 2, and 3 is not an element of \(S\):
\[ 0 \notin S \quad \leftarrow \text{0 is not an element of $S$}. \]
The ordering of the elements of \(S\) does not matter. Thus \(\{1,2\}\) denotes the same set as \(\{2,1\}\).
\[ S = \{1,2,3\} = \{2,1,3\} = \{2,3,1\} \quad \leftarrow \text{unordered} \]
2.2 The empty set
There is a special set called the empty set,
\[ \emptyset = \{\, \}, \] the set with no members. The statement \(x \in \emptyset\) is always false.
2.3 Subsets
A set \(S\) may be a subset of another set \(T\), written
\[ S \subset T \quad \leftarrow \text{$S$ is a subset of $T$}, \]
which means that
\[ x \in S \implies x \in T. \]
Here, the “\(\implies\)” arrow is read “implies” and relates two statements:
\[ P \implies Q \quad \leftarrow \text{if $P$ is true then $Q$ is true} \]
2.4 Subset vs. element of a set
It is important to take note of the distinction between \(x\) being an element of \(S\), and \(x\) being a subset of \(S\). For example,
\[ 1 \in \{1, 2\}, \quad \{1\} \subset \{1, 2\} \]
are different true statements.
2.5 Equality of sets
Two sets \(S\) and \(T\) are equal if they contain exactly the same elements:
\[ S = T \iff (x \in S \iff x \in T) \]
Here, the parenthesis signifies that what is inside is equivalent to \(S=T\).
Equivalently, we have the following characterization:
\[ S = T \iff (S \subset T \quad\text{and} \quad T \subset S). \]
2.6 Sets defined by conditions
We have seen one way to define a set: listing its elements. Another way to define a set is to select elements by a condition on another set. For example, if we are given a set such as
\[ S = \{1, 2, 3, 4\} \]
we can define a new set by filtering elements, e.g.,
\[ T = \{ x \in S \mid x \; \text{is even} \} = \{2, 4 \}. \]
Thus, if \(\varphi(x)\) is a statement that is either true or false depending on what \(x\) is, the notation
\[ T = \{ x \in S \mid \varphi(x) \} \]
denotes the subset of \(S\) where \(\varphi\) evaluates to true. (In Chapter 1 we saw that using such expressions may lead to inconsistencies.)
2.7 Union of sets
Given two sets \(S\) and \(T\) we can define the union \(S \cup T\): The set that is the combination of all the elements of \(S\) and \(T\):
\[ S \cup T = \{ x \mid x \in S \;\text{or}\; x \in T \}. \]
For example,
\[ \begin{align} S &= \{0, 1, 2\} \\ T &= \{ 0, 2, 3\} \\ S \cup T &= \{ 0, 1, 2, 3\} \end{align} \]
2.8 Intersection of sets
Given two sets \(S\) and \(T\), we can form the intersection \(S \cap T\): The set that contains the elements common to both:
\[ S \cap T = \{ x \mid x \in S \; \text{and} \; x \in T \}. \]
For example,
\[ \begin{align} S &= \{0, 1, 2\} \\ T &= \{ 0, 2, 3\} \\ S \cap T &= \{ 0, 2\} \end{align} \]
The intersection may end up empty, if \(S\) and \(T\) have no common elements:
\[ \{ 0, 1, 2\} \cap \{ 3, 4 \} = \emptyset . \]
2.9 Set difference
If we have two sets \(S\) and \(T\), we can form the set difference \(S \setminus T\), obtained by removing from \(S\) all elements that are also in \(T\):
\[ S \setminus T = \{ x \in S \mid x \notin T \} \]
For example,
\[ \{ 4, 5, 6 \} \setminus \{3, 4, 5\} = \{6 \}. \]