2 Sets
2.1 Basic definitions
Sets collect mathematical objects and form the foundation of modern mathematics. We begin with the following definition.
Definition 2.1 (Sets) Following Cantor (1895), a set \(M\) is defined as “a collection into a whole of definite, distinct objects \(m\) of our intuition or of our thought (which are called the elements of the set)”. We write \[\begin{equation} m \in M \mbox{ or } m \notin M, \end{equation}\] to express that \(m\) is an element or not an element of \(M\), respectively.
There are at least the following ways of defining sets:
- Listing the elements in curly braces, for example \(M := \{1,2,3\}\).
- Specifying the properties of the elements, for example \(M := \{x \in \mathbb{N}|x < 4\}\).
- Equating the set with another uniquely defined set, for example \(M := \mathbb{N}_3\).
The notation \(\{x \in \mathbb{N}|x < 4\}\) is read as “\(x \in \mathbb{N}\) such that \(x < 4\)”, where the meaning of \(\mathbb{N}\) will be explained below. It is important to recognize that sets are unordered mathematical objects, that is, the order in which the elements of a set are listed does not matter. For example, \(\{1,2,3\}\), \(\{1,3,2\}\), and \(\{2,3,1\}\) denote the same set, namely the set of the first three natural numbers.
Basic relations between several sets are fixed in the next definition.
Definition 2.2 (Subsets and set equality) Let \(M\) and \(N\) be two sets.
- A set \(M\) is called a subset of a set \(N\) if, for every element \(m \in M\), we also have \(m \in N\). If \(M\) is a subset of \(N\), we write \[\begin{equation} M \subseteq N \end{equation}\] and call \(M\) a subset of \(N\) and \(N\) a superset of \(M\).
- A set \(M\) is called a proper subset of a set \(N\) if, for every element \(m \in M\), we also have \(m \in N\), but there is at least one element \(n \in N\) for which \(n \notin M\). If \(M\) is a proper subset of \(N\), we write \[\begin{equation} M \subset N. \end{equation}\]
- Two sets \(M\) and \(N\) are called equal if, for every element \(m \in M\), we also have \(m \in N\), and if, for every element \(n \in N\), we also have \(n \in M\). If the sets \(M\) and \(N\) are equal, we write \[\begin{equation} M = N. \end{equation}\]
Example 2.1 (Subsets and set equality) For example, consider the sets \(M := \{1\}\), \(N := \{1,2\}\), and \(O := \{1,2\}\). Then, by the definitions above, \(M \subset N\), because \(1 \in M\) and \(1 \in N\), but \(2 \in N\) and \(2 \notin M\). Furthermore, \(N \subseteq O\), because \(1 \in N\) and \(1 \in O\), as well as \(2 \in N\) and \(2 \in O\), and there is no element of \(O\) that is not in \(N\). Likewise, \(O \subseteq N\), because \(1 \in O\) and \(1 \in N\), as well as \(2 \in O\) and \(2 \in N\), and there is no element of \(N\) that is not in \(O\). Finally, we even have \(N = O\), because, for every element \(n \in N\), we also have \(n \in O\), and at the same time, for every element \(o \in O\), we also have \(o \in N\). We represent these relations schematically by means of Venn-Euler diagrams in Figure 2.1.
An important property of a set is the number of elements it contains. This is called the cardinality of the set.
Definition 2.3 (Cardinality) The number of elements of a set \(M\) is called its cardinality and is denoted by \(|M|\).
A special set is the set without elements.
Definition 2.4 (Empty set) A set with cardinality zero is called the empty set and is denoted by \(\emptyset\).
As examples, let \(M := \{1,2,3\}\), \(N = \{a,b,c,d\}\), and \(O := \emptyset\). Then \(|M| = 3\), \(|N| = 4\), and \(|O| = 0\).
For every set, one can consider the set of all subsets of this set. This leads to the important concept of the power set.
Definition 2.5 (Power set) The set of all subsets of a set \(M\) is called the power set of \(M\) and is denoted by \(\mathcal{P}(M)\).
Note that the empty subset of \(M\) and \(M\) itself are always elements of \(\mathcal{P}(M)\). Intuitively, each subset of \(M\) corresponds to a selection of elements from \(M\). Selecting no elements gives the empty set, whereas selecting all elements gives \(M\) itself. The power set systematically includes all these possible selections.
Example 2.2 (Power sets) We consider the power sets of sets with zero, one, two, and three elements.
Let \(M_0 := \emptyset\) be the empty set. Then \[\begin{equation} \mathcal{P}(M_0) = \{\emptyset\}. \end{equation}\]
Let \(M_1 := \{a\}\) be a one-element set. Then \[\begin{equation} \mathcal{P}(M_1) = \{\emptyset,\{a\}\}. \end{equation}\]
Let \(M_2 := \{a,b\}\). Then \(M_2\) has both one-element and two-element subsets, and \[\begin{equation} \mathcal{P}(M_2) = \{\emptyset,\{a\}, \{b\}, \{a,b\}\}. \end{equation}\]
Finally, let \(M_3 := \{a,b,c\}\). Then \(M_3\) has one-element, two-element, and three-element subsets, and \[\begin{equation} \mathcal{P}(M_3) = \{\emptyset, \{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},\{a,b,c\}\}. \end{equation}\]
Theorem 2.1 (Cardinality of the power set) Given a set \(M\) with cardinality \(|M| = n\), and let \(\mathcal{P}(M)\) be its power set. Then \(|\mathcal{P}(M)| = 2^n\).
Proof. To prove the statement of the theorem, we associate each element \(P\) of the power set of \(M\) uniquely with a binary sequence of length \(n\), where the entry at the \(i\)-th position represents whether the \(i\)-th element of \(M\) is an element of \(P\) or not. For example, let \(M := \{m_1,m_2,m_3\}\) and \(P := \{m_2,m_3\}\). Then \(P\) corresponds to the binary sequence \(011\). The empty set \(P := \emptyset\) corresponds to the binary sequence \(000\), and the original set \(P = M\) corresponds to the binary sequence \(111\). Thus the question is how many unique binary sequences of length \(n\) there are. Since each element of the sequence has two possible states, there are \(n\) factors \(2 \cdot 2 \cdots 2\), that is, \(2^n\).
In the examples above, we have the cases
- \(|M_0| = 0 \Rightarrow |\mathcal{P}(M_0)| = 2^0 = 1\),
- \(|M_1| = 1 \Rightarrow |\mathcal{P}(M_1)| = 2^1 = 2\),
- \(|M_2| = 2 \Rightarrow |\mathcal{P}(M_2)| = 2^2 = 4\),
- \(|M_3| = 3 \Rightarrow |\mathcal{P}(M_3)| = 2^3 = 8\),
as can be verified by counting the elements of the corresponding power sets.
2.2 Operations
Two sets can be combined with one another in different ways. The result of such a combination is another set. We call the combination of two sets a set operation and give the following definitions.
Definition 2.6 (Set operations) Let \(M\) and \(N\) be two sets.
The union of \(M\) and \(N\) is defined as the set \[\begin{equation} M \cup N := \{x | x \in M \lor x \in N\}, \end{equation}\] where, according to the definition of disjunction, \(\lor\) is understood as non-exclusive or, that is, and/or.
The intersection of \(M\) and \(N\) is defined as the set \[\begin{equation} M \cap N := \{x | x \in M \land x \in N\}. \end{equation}\] If \(M\) and \(N\) satisfy \(M \cap N = \emptyset\), then \(M\) and \(N\) are called disjoint.
The difference of \(M\) and \(N\) is defined as the set \[\begin{equation} M\setminus N := \{x | x \in M \land x \notin N\}. \end{equation}\]
The symmetric difference of \(M\) and \(N\) is defined as the set \[\begin{equation} M \Delta N := \{x|(x \in M \lor x \in N) \land x \notin M \cap N\}. \end{equation}\] The symmetric difference can therefore be understood as an exclusive or.
Example 2.3 (Set operations) As an example, consider the sets \(M := \{1,2,3\}\) and \(N := \{2,3,4,5\}\). Then
- \(M \cup N = \{1,2,3,4,5\}\), because \(1 \in M\), \(2 \in M\), \(3 \in M\), \(4 \in N\), and \(5 \in N\).
- \(M \cap N = \{2,3\}\), because only for \(2\) and \(3\) do we have \(2 \in M, 3 \in M\) and also \(2 \in N, 3 \in N\). For \(1\), we only have \(1 \in M\), and for \(4\) and \(5\), we only have \(4 \in N\) and \(5 \in N\).
- \(M \setminus N = \{1\}\), because \(1 \in M\), but \(1 \notin N\), and \(2 \in M\), but also \(2 \in N\).
- \(N \setminus M = \{4,5\}\), because \(4 \in N\) and \(5 \in N\), but \(4 \notin M\) and \(5 \notin M\). This shows in particular that the difference of \(M\) and \(N\) is not symmetric, that is, it is not necessarily the case that \(M\setminus N\) equals \(N \setminus M\).
- \(M \Delta N = \{1,4,5\}\), because \(1 \in M\), but \(1 \notin \{2,3\}\), \(2 \in M\), but \(2 \in \{2,3\}\), \(3 \in M\), but \(3 \in \{2,3\}\), \(4 \in N\), but \(4 \notin \{2,3\}\), and \(5 \in N\), but \(5 \notin \{2,3\}\).
Figure 2.2 visualizes the set operations considered in this example.
The following associative and distributive laws hold for operations involving three sets. The associative laws allow us to choose the grouping freely in repeated unions or intersections. The distributive laws describe the interplay between union and intersection.
Theorem 2.2 (Associative and distributive laws for union and intersection) Let \(M,N,O\) be sets. Then the following hold.
Associative law of union \[\begin{equation} (M\cup N)\cup O=M\cup(N\cup O). \end{equation}\]
Associative law of intersection \[\begin{equation} (M\cap N)\cap O=M\cap(N\cap O). \end{equation}\]
Distributive law of intersection over union \[\begin{equation} M\cap(N\cup O)=(M\cap N)\cup(M\cap O). \end{equation}\]
Distributive law of union over intersection \[\begin{equation} M\cup(N\cap O)=(M\cup N)\cap(M\cup O). \end{equation}\]
Proof. . First, let \(x\in(M\cup N)\cup O\). Then \(x\in M\cup N\) or \(x\in O\). Thus \(x\) belongs to at least one of the sets \(M,N,O\). Hence \(x\in M\) or \(x\in N\cup O\), and therefore \[\begin{equation} (M\cup N)\cup O\subseteq M\cup(N\cup O). \end{equation}\] Conversely, let \(x\in M\cup(N\cup O)\). Then \(x\in M\) or \(x\in N\cup O\). Again, \(x\) belongs to at least one of the sets \(M,N,O\). Hence \(x\in M\cup N\) or \(x\in O\), and therefore \[\begin{equation} M\cup(N\cup O)\subseteq(M\cup N)\cup O. \end{equation}\] Taken together, this gives \[\begin{equation} (M\cup N)\cup O=M\cup(N\cup O). \end{equation}\]
. First, let \(x\in(M\cap N)\cap O\). Then \(x\in M\cap N\) and \(x\in O\). Thus \(x\in M\), \(x\in N\), and \(x\in O\). Hence \(x\in M\) and \(x\in N\cap O\), and therefore \[\begin{equation} (M\cap N)\cap O\subseteq M\cap(N\cap O). \end{equation}\] Conversely, let \(x\in M\cap(N\cap O)\). Then \(x\in M\) and \(x\in N\cap O\). Again, \(x\in M\), \(x\in N\), and \(x\in O\). Hence \(x\in M\cap N\) and \(x\in O\), and therefore \[\begin{equation} M\cap(N\cap O)\subseteq(M\cap N)\cap O. \end{equation}\] Taken together, this gives \[\begin{equation} (M\cap N)\cap O=M\cap(N\cap O). \end{equation}\]
. First, let \(x\in M\cap(N\cup O)\). Then \(x\in M\) and also \(x\in N\) or \(x\in O\). In the first case, \(x\in M\cap N\), and in the second case, \(x\in M\cap O\). Thus \[\begin{equation} M\cap(N\cup O)\subseteq(M\cap N)\cup(M\cap O). \end{equation}\] Conversely, let \(x\in(M\cap N)\cup(M\cap O)\). Then \(x\in M\cap N\) or \(x\in M\cap O\). In both cases, \(x\) belongs to \(M\) and to at least one of the sets \(N,O\). Hence \(x\in M\cap(N\cup O)\), and therefore \[\begin{equation} (M\cap N)\cup(M\cap O)\subseteq M\cap(N\cup O). \end{equation}\] Taken together, this gives \[\begin{equation} M\cap(N\cup O)=(M\cap N)\cup(M\cap O). \end{equation}\]
. First, let \(x\in M\cup(N\cap O)\). If \(x\in M\), then \(x\) belongs to both \(M\cup N\) and \(M\cup O\). If \(x\notin M\), we must have \(x\in N\cap O\). In this case, \(x\) also belongs to both \(M\cup N\) and \(M\cup O\). Thus \[\begin{equation} M\cup(N\cap O)\subseteq(M\cup N)\cap(M\cup O). \end{equation}\] Conversely, let \(x\in(M\cup N)\cap(M\cup O)\). If \(x\in M\), then immediately \(x\in M\cup(N\cap O)\). If \(x\notin M\), then \(x\in M\cup N\) implies \(x\in N\), and \(x\in M\cup O\) implies \(x\in O\). Hence \(x\in N\cap O\), so again \(x\in M\cup(N\cap O)\). Thus we also have \[\begin{equation} (M\cup N)\cap(M\cup O)\subseteq M\cup(N\cap O). \end{equation}\] Taken together, this gives \[\begin{equation} M\cup(N\cap O)=(M\cup N)\cap(M\cup O). \end{equation}\]
Definition 2.7 (Complement) Let \(M\) and \(O\) be sets with \(M \subseteq O\). Then the set \[\begin{equation} M^c := O \setminus M = \{x|x \in O \land x \notin M\} \end{equation}\] is called the complement of \(M\) relative to \(O\).
In Definition 2.7, \(O\) is also called the universal set or universe. The complement \(M^c\) contains all elements of this universe that do not belong to \(M\). In general, the difference \(A \setminus B\) of two arbitrary sets defined in Definition 2.6 is also called the relative complement of \(B\) in \(A\). Here, \(B\) need not be a subset of \(A\). If a universe \(O\) is fixed and \(M \subseteq O\), Definition 2.7 applies. To distinguish the two concepts, \(M^c = O \setminus M\) is also called the absolute complement of \(M\), a special case of the relative complement. The term absolute does not mean that the complement is independent of the universe. Rather, the fixed universe is simply not stated explicitly in the notation \(M^c\).
The following figure illustrates the complement of \(M\) relative to \(O\).
Theorem 2.3 (Properties of complements) Let \(M\) and \(O\) be sets with \(M\subseteq O\), and let \(M^c\) be the complement of \(M\) relative to \(O\). Then
- \(M^c\cup M=O\),
- \(M^c\cap M=\emptyset\),
- \((M^c)^c=M\).
Both complements in statement 3 are taken relative to the same universal set \(O\).
Proof. . We establish equality of the sets by proving both inclusions. First, let \(x\in M^c\cup M\). By the definition of union, \(x\in M^c\) or \(x\in M\). In the first case, the definition of the complement implies \(x\in O\). In the second case, \(M\subseteq O\) also implies \(x\in O\). Hence \[\begin{equation} M^c\cup M\subseteq O. \end{equation}\] Conversely, let \(o\in O\). Then either \(o\in M\) or \(o\notin M\). In the first case, \(o\in M^c\cup M\). In the second case, the definition of the complement gives \(o\in M^c\), so again \(o\in M^c\cup M\). Thus we also have \[\begin{equation} O\subseteq M^c\cup M. \end{equation}\] Taken together, this gives \(M^c\cup M=O\).
. Suppose there were an element \(x\in M^c\cap M\). By the definition of intersection, both \(x\in M^c\) and \(x\in M\) would have to hold. However, by the definition of the complement, \(x\in M^c\) implies \(x\notin M\). This is a contradiction. The intersection \(M^c\cap M\) therefore contains no elements, so \[\begin{equation} M^c\cap M=\emptyset. \end{equation}\]
. First, let \(x\in(M^c)^c\). By the definition of the complement, we have \(x\in O\) and \(x\notin M^c\). If \(x\notin M\), then \(x\in O\) would imply \(x\in M^c\). This contradicts \(x\notin M^c\). Hence \(x\in M\), and therefore \[\begin{equation} (M^c)^c\subseteq M. \end{equation}\] Conversely, let \(m\in M\). Since \(M\subseteq O\), we have \(m\in O\). Also, \(m\notin M^c\), since the complement of \(M\) contains only elements that do not belong to \(M\). The definition of the complement therefore implies \(m\in(M^c)^c\). Thus we also have \[\begin{equation} M\subseteq(M^c)^c. \end{equation}\] Taken together, this gives \((M^c)^c=M\).
The following statements describe how sets can be decomposed into disjoint subsets. Figure 2.4 illustrates the three decompositions.
Theorem 2.4 (Disjoint decompositions of sets) Let \(M,N\), and \(O\) be sets with \(M\subseteq O\) and \(N\subseteq O\). The complements of \(M\) and \(N\) are taken relative to \(O\). Then the following hold.
If \(M\subseteq N\), then \[\begin{equation} N = M\cup(N\cap M^c) \mbox{ and } M\cap(N\cap M^c) = \emptyset. \end{equation}\]
We have \[\begin{equation} M = (M\cap N)\cup(M\cap N^c) \mbox{ and } (M\cap N)\cap(M\cap N^c) = \emptyset. \end{equation}\]
We have \[\begin{equation} M\cup N = (M\cap N^c)\cup N \mbox{ and } (M\cap N^c)\cap N = \emptyset. \end{equation}\]
Proof. . Let \(M\subseteq N\). We first prove equality of the sets. Let \(n\in N\). There are two possibilities. If \(n\in M\), then \(n\in M\cup(N\cap M^c)\). If \(n\notin M\), then \(n\in N\subseteq O\) implies \(n\in M^c\). Together with \(n\in N\), this gives \(n\in N\cap M^c\), so again \(n\in M\cup(N\cap M^c)\). Thus \[\begin{equation} N\subseteq M\cup(N\cap M^c). \end{equation}\] Conversely, let \(x\in M\cup(N\cap M^c)\). Then \(x\in M\) or \(x\in N\cap M^c\). In the first case, \(M\subseteq N\) implies \(x\in N\). In the second case, \(x\in N\) follows directly from the definition of intersection. Thus we also have \[\begin{equation} M\cup(N\cap M^c)\subseteq N. \end{equation}\] Taken together, these inclusions establish the claimed equality of sets.
To prove disjointness, suppose there were an element \(x\in M\cap(N\cap M^c)\). Then, in particular, both \(x\in M\) and \(x\in M^c\) would hold. This is impossible by the definition of the complement. Hence \[\begin{equation} M\cap(N\cap M^c)=\emptyset. \end{equation}\]
. First, let \(m\in M\). If \(m\in N\), then \(m\in M\cap N\). If \(m\notin N\), then \(m\in M\subseteq O\) implies \(m\in N^c\), and hence \(m\in M\cap N^c\). In both cases, \(m\in(M\cap N)\cup(M\cap N^c)\). This proves \[\begin{equation} M\subseteq(M\cap N)\cup(M\cap N^c) \end{equation}\] Conversely, let \(x\in(M\cap N)\cup(M\cap N^c)\). Then \(x\) belongs to at least one of the sets \(M\cap N\) and \(M\cap N^c\). In both cases, the definition of intersection implies \(x\in M\). Thus we also have \[\begin{equation} (M\cap N)\cup(M\cap N^c)\subseteq M. \end{equation}\] Taken together, these inclusions establish the claimed equality of sets.
If there were an element \(x\in(M\cap N)\cap(M\cap N^c)\), then, in particular, both \(x\in N\) and \(x\in N^c\) would hold. This is impossible by the definition of the complement. Hence \[\begin{equation} (M\cap N)\cap(M\cap N^c)=\emptyset. \end{equation}\]
. First, let \(x\in M\cup N\). If \(x\in N\), then immediately \(x\in(M\cap N^c)\cup N\). If \(x\notin N\), then \(x\in M\cup N\) implies \(x\in M\). Since \(M\subseteq O\), we also have \(x\in O\), and hence \(x\in N^c\). Thus \(x\in M\cap N^c\), so again \(x\in(M\cap N^c)\cup N\). Therefore \[\begin{equation} M\cup N\subseteq(M\cap N^c)\cup N. \end{equation}\] Conversely, let \(x\in(M\cap N^c)\cup N\). Then \(x\in M\cap N^c\) or \(x\in N\). In the first case, \(x\in M\), and hence \(x\in M\cup N\). In the second case, we also have \(x\in M\cup N\). Thus \[\begin{equation} (M\cap N^c)\cup N\subseteq M\cup N. \end{equation}\] Taken together, these inclusions establish the claimed equality of sets.
If there were an element \(x\in(M\cap N^c)\cap N\), both \(x\in N^c\) and \(x\in N\) would hold. This is impossible by the definition of the complement. Hence \[\begin{equation} (M\cap N^c)\cap N=\emptyset. \end{equation}\]
Theorem 2.5 (De Morgan’s laws) Let \(M,N\), and \(O\) be sets with \(M\subseteq O\) and \(N\subseteq O\). All complements are taken relative to \(O\). Then
- \((M\cap N)^c=M^c\cup N^c\),
- \((M\cup N)^c=M^c\cap N^c\).
Proof. . We establish equality of the sets by proving both inclusions. First, let \(x\in(M\cap N)^c\). By the definition of the complement, \(x\in O\) and \(x\notin M\cap N\). Thus \(x\in M\) and \(x\in N\) cannot hold simultaneously. Hence \(x\notin M\) or \(x\notin N\). Since \(x\in O\), this implies \(x\in M^c\) or \(x\in N^c\), that is, \(x\in M^c\cup N^c\). Thus \[\begin{equation} (M\cap N)^c\subseteq M^c\cup N^c. \end{equation}\]
Conversely, let \(x\in M^c\cup N^c\). Then \(x\in M^c\) or \(x\in N^c\). In both cases, \(x\in O\). In the first case, \(x\notin M\), and in the second case, \(x\notin N\). In either case, \(x\) cannot belong to the intersection \(M\cap N\). Hence \(x\in(M\cap N)^c\), and therefore \[\begin{equation} M^c\cup N^c\subseteq(M\cap N)^c. \end{equation}\] Taken together, this gives \((M\cap N)^c=M^c\cup N^c\).
. First, let \(x\in(M\cup N)^c\). By the definition of the complement, we have \(x\in O\) and \(x\notin M\cup N\). Thus \(x\) belongs to neither \(M\) nor \(N\). Since \(x\in O\), this implies \(x\in M^c\) and \(x\in N^c\), that is, \(x\in M^c\cap N^c\). Hence \[\begin{equation} (M\cup N)^c\subseteq M^c\cap N^c. \end{equation}\]
Conversely, let \(x\in M^c\cap N^c\). Then \(x\in M^c\) and \(x\in N^c\). By the definition of the complement, \(x\in O\), \(x\notin M\), and \(x\notin N\). Hence \(x\notin M\cup N\), and therefore \(x\in(M\cup N)^c\). Thus we also have \[\begin{equation} M^c\cap N^c\subseteq(M\cup N)^c. \end{equation}\] Taken together, this gives \((M\cup N)^c=M^c\cap N^c\).
We use an abbreviated notation for operations involving several sets.
Definition 2.8 (Operations on multiple sets) Let \(n \in \mathbb{N}\) and let \(M_1,\ldots,M_n\) be sets. We denote
the union of multiple sets by \[\begin{equation} \bigcup_{i = 1}^{n} M_i := M_1 \cup M_2 \cup \cdots \cup M_n, \end{equation}\]
the intersection of multiple sets by \[\begin{equation} \bigcap_{i = 1}^{n} M_i := M_1 \cap M_2 \cap \cdots \cap M_n. \end{equation}\]
Here,
- the symbols \(\bigcup\) and \(\bigcap\) stand for the respective set operation,
- the subscript \(i = 1\) specifies the running index and the starting index,
- the superscript \(n\) specifies the final index, and
- \(M_1,\ldots,M_n\) are the sets involved in the operation.
The union contains all elements that belong to at least one of the sets \(M_i\). The intersection contains all elements that belong to every set \(M_i\).
The indices must be specified unambiguously. However, the name of the running index is irrelevant to the result of the set operation. For example, \[\begin{equation} \bigcup_{i = 1}^{n} M_i = \bigcup_{j = 1}^{n} M_j. \end{equation}\]
Sometimes the running index is specified as an element of an index set. For example, if \(I := \{1,5,7\}\), then \[\begin{equation} \bigcup_{i \in I} M_i := M_1 \cup M_5 \cup M_7. \end{equation}\] We use the corresponding notation for the intersection of multiple sets as well.
This notation also extends to countably infinitely many sets \(A_1,A_2,\ldots\). Their union \(\bigcup_{i=1}^{\infty}A_i\) contains exactly those elements that belong to at least one of the sets \(A_i\). Correspondingly, the intersection \(\bigcap_{i=1}^{\infty}M_i\) contains exactly those elements that belong to every set \(M_i\).
Theorem 2.6 (Countable distributivity) Let \(A_1,A_2,\ldots\) and \(B\) be sets. Then \[\begin{equation} \left(\bigcup_{i=1}^{\infty}A_i\right)\cap B = \bigcup_{i=1}^{\infty}(A_i\cap B). \end{equation}\]
Proof. First, let \[\begin{equation} x\in\left(\bigcup_{i=1}^{\infty}A_i\right)\cap B. \end{equation}\] Then \(x\in B\), and there exists an \(i\in\mathbb{N}\) such that \(x\in A_i\). For this \(i\), we have \(x\in A_i\cap B\). Hence \[\begin{equation} x\in\bigcup_{i=1}^{\infty}(A_i\cap B). \end{equation}\] Thus \[\begin{equation} \left(\bigcup_{i=1}^{\infty}A_i\right)\cap B \subseteq \bigcup_{i=1}^{\infty}(A_i\cap B). \end{equation}\]
Conversely, let \[\begin{equation} x\in\bigcup_{i=1}^{\infty}(A_i\cap B). \end{equation}\] Then there exists an \(i\in\mathbb{N}\) such that \(x\in A_i\cap B\). For this \(i\), both \(x\in A_i\) and \(x\in B\) hold. Hence \(x\) belongs to the union of the \(A_i\) and also to \(B\). Thus \[\begin{equation} \bigcup_{i=1}^{\infty}(A_i\cap B) \subseteq \left(\bigcup_{i=1}^{\infty}A_i\right)\cap B. \end{equation}\] Taken together, this gives \[\begin{equation} \left(\bigcup_{i=1}^{\infty}A_i\right)\cap B = \bigcup_{i=1}^{\infty}(A_i\cap B). \end{equation}\]
Theorem 2.7 (Intersections of disjoint sets) Let \(M,N,O\) be sets with \(M\cap N=\emptyset\). Then \[\begin{equation} (M\cap O)\cap(N\cap O)=\emptyset. \end{equation}\]
Proof. If there were an element \[\begin{equation} x\in(M\cap O)\cap(N\cap O), \end{equation}\] then, in particular, \(x\in M\) and \(x\in N\) would hold. Thus \(x\in M\cap N\), contradicting the assumed disjointness. Hence \[\begin{equation} (M\cap O)\cap(N\cap O)=\emptyset. \end{equation}\]
Theorem 2.8 (Countable De Morgan’s laws) Let \(M_1,M_2,\ldots\subseteq O\). All complements are taken relative to the universal set \(O\). Then the following hold.
We have \[\begin{equation} \left(\bigcap_{i=1}^{\infty}M_i\right)^c =\bigcup_{i=1}^{\infty}M_i^c. \end{equation}\]
We have \[\begin{equation} \left(\bigcup_{i=1}^{\infty}M_i\right)^c =\bigcap_{i=1}^{\infty}M_i^c. \end{equation}\]
Proof. . First, let \[\begin{equation} x\in\left(\bigcap_{i=1}^{\infty}M_i\right)^c. \end{equation}\] Then \(x\) belongs to \(O\), but not to every set \(M_i\). Thus there exists an \(i\in\mathbb{N}\) such that \(x\notin M_i\). For this \(i\), we have \(x\in M_i^c\). Hence \[\begin{equation} \left(\bigcap_{i=1}^{\infty}M_i\right)^c \subseteq\bigcup_{i=1}^{\infty}M_i^c. \end{equation}\] Conversely, let \[\begin{equation} x\in\bigcup_{i=1}^{\infty}M_i^c. \end{equation}\] Then there exists an \(i\in\mathbb{N}\) such that \(x\in M_i^c\). Thus \(x\in O\) and \(x\notin M_i\). Hence \(x\) does not belong to the intersection of all \(M_i\), but does belong to its complement relative to \(O\). Thus we also have \[\begin{equation} \bigcup_{i=1}^{\infty}M_i^c \subseteq\left(\bigcap_{i=1}^{\infty}M_i\right)^c. \end{equation}\] Taken together, this gives \[\begin{equation} \left(\bigcap_{i=1}^{\infty}M_i\right)^c =\bigcup_{i=1}^{\infty}M_i^c. \end{equation}\]
. First, let \[\begin{equation} x\in\left(\bigcup_{i=1}^{\infty}M_i\right)^c. \end{equation}\] Then \(x\) belongs to \(O\), but to none of the sets \(M_i\). Hence \(x\in M_i^c\) for every \(i\in\mathbb{N}\). Thus \[\begin{equation} \left(\bigcup_{i=1}^{\infty}M_i\right)^c \subseteq\bigcap_{i=1}^{\infty}M_i^c. \end{equation}\] Conversely, let \[\begin{equation} x\in\bigcap_{i=1}^{\infty}M_i^c. \end{equation}\] Then \(x\in M_i^c\) for every \(i\in\mathbb{N}\). Thus \(x\) belongs to \(O\) and to none of the sets \(M_i\). Hence \(x\) belongs to the complement of their union. Thus we also have \[\begin{equation} \bigcap_{i=1}^{\infty}M_i^c \subseteq\left(\bigcup_{i=1}^{\infty}M_i\right)^c. \end{equation}\] Taken together, this gives \[\begin{equation} \left(\bigcup_{i=1}^{\infty}M_i\right)^c =\bigcap_{i=1}^{\infty}M_i^c. \end{equation}\]
Finally, we introduce the concept of a partition of a set.
Definition 2.9 (Partition) Let \(M\) be a set, and let \(P := \{N_i\}\) be a set of sets \(N_i\) with \(i = 1,...,n\), such that \[\begin{equation} \left(M = \cup_{i=1}^n N_i\right) \land \left(N_i \cap N_j = \emptyset \mbox{ for } i,j = 1,...,n \mbox{ and } i \neq j \right). \end{equation}\] Then \(P\) is called a partition of \(M\).
The partition of a set therefore corresponds to splitting the set into disjoint subsets. Partitions are generally not unique, that is, there are usually several ways to partition a given set.
As an example, consider the set \(M := \{1,2,3,4,5,6\}\). Then \(P_1 := \{\{1\}, \{2,3,4,5,6\}\}\), \(P_2 := \{\{1,2,3\}, \{4,5,6\}\}\), and \(P_3 := \{\{1,2\},\{3,4\}, \{5,6\}\}\) are three possible partitions of \(M\). Figure 2.5 visualizes the partitions considered in this example.
2.3 Special sets
Number sets
In natural science, one attempts to describe phenomena of the world that are intuitively identified as discrete or continuous by means of numbers. Depending on the type of phenomenon, different number sets are suitable for this purpose. Mathematics provides, among others, the number sets given in the following definition.
Definition 2.10 (Number sets) The following denote:
- \(\mathbb{N}\,\,\, := \{1,2,3,...\}\) the natural numbers,
- \(\mathbb{N}_n := \{1,2,3,...,n\}\) the natural numbers of order \(n\),
- \(\mathbb{N}^0 := \mathbb{N} \cup \{0\}\) the natural numbers and zero,
- \(\mathbb{Z}\,\,\, := \{...,-3,-2,-1,0,1,2,3...\}\) the integers,
- \(\mathbb{Q}\,\,\, := \{\frac{p}{q}|p \in \mathbb{Z}, q \in \mathbb{N}\}\) the rational numbers,
- \(\mathbb{R}\,\,\,\) the real numbers, and
- \(\mathbb{C}\,\,\, := \{a + ib|a,b\in \mathbb{R}, i := \sqrt{-1} \}\) the complex numbers.
Natural numbers and integers are suitable for quantifying discrete phenomena. Rational numbers and especially real numbers are suitable for quantifying continuous phenomena. The successive extension of these number sets can be motivated intuitively by equations that cannot always be solved in the smaller set. For example, \(5 + x = 3\) has no solution in \(\mathbb{N}^0\), but has the solution \(x = -2\) in \(\mathbb{Z}\). In particular, negative integers allow unrestricted subtraction of natural numbers. The equation \(2x = 5\) has no solution in \(\mathbb{Z}\), but has the solution \(x = \frac{5}{2}\) in \(\mathbb{Q}\). The equation \(x^2 = 1 + 1\) leads to the positive solution \(x = \sqrt{2}\). Geometrically, \(\sqrt{2}\) is the length of the hypotenuse of a right triangle whose legs both have length \(1\), as Figure 2.6 shows. Although this triangle can be drawn and its hypotenuse measured, rational numbers do not suffice to describe its exact length. Real numbers are needed, as we show below. Finally, \(x^2 = -1\) has no solution in \(\mathbb{R}\), because the square of a real number is always nonnegative. In \(\mathbb{C}\), however, it has the solutions \(x = i\) and \(x = -i\), where the imaginary unit \(i\) satisfies \(i^2 = -1\).
The real numbers comprise the rational numbers and the so-called irrational numbers \(\mathbb{R} \setminus \mathbb{Q}\). Rational numbers can be expressed as fractions of integers and natural numbers. They include all integers and all positive and negative decimals with terminating or repeating decimal expansions, for example \(-\frac{9}{10} = -0.9\), \(\frac{1}{3} = 0.\bar{3}\), and \(\frac{196}{100} = 1.96\). Between any two distinct rational numbers lie infinitely many other rational numbers. In particular, for \(a,b \in \mathbb{Q}\) with \(a < b\), the rational number \(\frac{a+b}{2}\) lies between them, and this argument can be repeated arbitrarily often between the resulting numbers. Likewise, infinitely many real numbers lie between any two distinct real numbers. Irrational numbers, by contrast, cannot be expressed as rational numbers. Examples include Euler’s number \(e \approx 2.71\), the circle constant \(\pi \approx 3.14\), and the square root of \(2\), \(\sqrt{2} \approx 1.41\).
The real numbers contain the natural numbers, integers, and rational numbers as subsets. In particular, \(\mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}\). There are therefore very many real numbers. In fact, Cantor (1874) proved that there are more real numbers than natural numbers, although both sets are infinite. This property is called the uncountability of the real numbers. We examine it further in Chapter 4. Positive infinity \(\infty\) and negative infinity \(-\infty\), however, are not numbers with which one can calculate in standard mathematics. They do not belong to the number sets defined above, so \(\infty \notin \mathbb{R}\) and \(-\infty \notin \mathbb{R}\). Finally, complex numbers are suitable for describing two-dimensional continuous phenomena. Values of the first dimension are represented by the real part \(a\), and values of the second by the imaginary part \(b\) of a complex number. Complex numbers are used, for example, in modeling physical phenomena and in Fourier analysis.
The standard set for describing continuous phenomena is certainly the real numbers, even though real numbers are generally approximated by rational numbers in everyday life and especially in numerical mathematics. We return to the nature of real numbers at various points. Here, we first show that the rational numbers indeed do not suffice to solve \(x^2 = 2\) for \(x\), because the square root of \(2\) is not rational.
Theorem 2.9 (Irrationality of \(\sqrt{2}\)) The square root of \(2\) is not a rational number, \[\begin{equation} \sqrt{2} \notin \mathbb{Q} \end{equation}\]
Proof. Using the notation for proof by contradiction from Section 1.5, we want to show that for the propositions (A) \(x = \sqrt{2}\) and (B) \(x \notin \mathbb{Q}\), the implication \(A \Rightarrow B\) holds. Following Abbott (2015) (Chapter 1), we prove this by contradiction, showing that the assumption \((\neg B) \land A\) leads to a false statement.
Here, \(\neg B\) is the proposition \(x \in \mathbb{Q}\). Thus, there are \(p,q \in \mathbb{Z}\) with \(q \neq 0\) such that \[\begin{equation} x = \frac{p}{q} \end{equation}\] holds. Without loss of generality, we choose this fraction in lowest terms, so that \(p\) and \(q\) are relatively prime. Otherwise, numerator and denominator could be divided by a common integer divisor greater than \(1\). For example, \(12/9\) can be reduced to \(4/3\) by dividing by the common divisor \(3\).
Under the assumption \((\neg B) \land A\), both \(x = p/q\) and \(x^2 = 2\) hold. Therefore, \[\begin{equation}\label{eq-wurzel-zwei-annahme} \left(\frac{p}{q}\right)^2 = 2. \end{equation}\] Rearranging equation \(\eqref{eq-wurzel-zwei-annahme}\) gives \[\begin{equation}\label{eq-wurzel-zwei-p-gerade} \left(\frac{p}{q}\right)^2 = 2 \Leftrightarrow \frac{p^2}{q^2} = 2 \Leftrightarrow p^2 = 2q^2. \end{equation}\] It follows that \(p^2\) is divisible by \(2\) and is therefore even. Hence \(p\) must also be even, since an integer with an even square is always even, as shown in Example 1.5 in Chapter 1. We can therefore write \(p = 2r\) for some \(r \in \mathbb{Z}\). Substitution into the last equality in \(\eqref{eq-wurzel-zwei-p-gerade}\) gives \[\begin{equation} p^2 = 2q^2 \Leftrightarrow (2r)^2 = 2q^2 \Leftrightarrow 4r^2 = 2q^2 \Leftrightarrow 2r^2 = q^2. \end{equation}\] The last equality shows that \(q^2\) is even. Thus, \(q\) is also even. Both \(p\) and \(q\) are therefore divisible by \(2\), contradicting the assumption that \(p\) and \(q\) are relatively prime.
The assumption \((\neg B) \land A\) therefore leads to a contradiction. It is consequently false, and hence \[\begin{equation} x = \sqrt{2} \Rightarrow x \notin \mathbb{Q}. \end{equation}\] This proves that \(\sqrt{2}\) is not a rational number.
Important subsets of the real numbers are the so-called intervals. We give the following definitions.
Intervals
Definition 2.11 (Intervals) Connected subsets of the real numbers are called intervals. For \(a,b\in \mathbb{R}\), one distinguishes
- the closed interval \[\begin{equation} [a,b] := \{x \in \mathbb{R}|a \le x \le b\}, \end{equation}\]
- the open interval \[\begin{equation} ]a,b[ := \{x \in \mathbb{R}|a < x < b\}, \end{equation}\]
- and the half-open intervals \[\begin{equation} ]a,b] := \{x \in \mathbb{R}| a < x \le b\} \mbox{ and } [a,b[ := \{x \in \mathbb{R}| a \le x < b\}. \end{equation}\]
As examples, Figure 2.7 graphically represents the intervals \([1,2]\), \(]1,2]\), \([1,2[\), and \(]1,2[\). Here one imagines the real numbers as a continuous number line and must in each case note whether the left and right endpoints are part of the interval or not. As mentioned above, positive infinity (\(\infty\)) and negative infinity \(-\infty\) are not elements of \(\mathbb{R}\). Thus one always writes \(]-\infty,b]\) or \(]-\infty,b[\) and \(]a,\infty[\) or \([a,\infty[\), as well as \(\mathbb{R} = ]-\infty, \infty[\).
Cartesian products
Often one wants to quantitatively describe several independent properties of a phenomenon at the same time. For this purpose, the one-dimensional number sets defined above can be extended to multidimensional number sets by forming Cartesian products. The elements of Cartesian products are called ordered tuples or vectors.
Definition 2.12 (Cartesian products) Let \(M\) and \(N\) be two sets. Then the Cartesian product of the sets \(M\) and \(N\) is the set of all ordered tuples \((m,n)\) with \(m \in M\) and \(n \in N\), formally \[\begin{equation} M \times N := \{(m,n)|m\in M, n \in N \}. \end{equation}\]
The Cartesian product of a set \(M\) with itself is denoted by \[\begin{equation} M^2 := M \times M. \end{equation}\] Furthermore, let \(M_1,\ldots,M_n\) be sets. The Cartesian product of the sets \(M_1,\ldots,M_n\) is the set of all ordered \(n\)-tuples \((m_1,\ldots,m_n)\) with \(m_i \in M_i\) for \(i = 1,\ldots,n\), formally \[\begin{equation} \times_{i = 1}^{n} M_i := M_1 \times \cdots \times M_n := \{(m_1,\ldots,m_n) | m_i \in M_i \text{ for } i = 1,\ldots,n\}. \end{equation}\] The \(n\)-fold Cartesian product of a set \(M\) with itself is denoted by \[\begin{equation} M^n := \times_{i = 1}^{n} M := \{(m_1,\ldots,m_n) | m_i \in M \text{ for } i = 1,\ldots,n\}. \end{equation}\]
In contrast to sets, the tuples introduced in Definition 2.12 are ordered. This means, for example, that for sets we have \(\{1,2\} = \{2,1\}\), but for tuples we have \((1,2) \neq (2,1)\).
Example 2.4 (Cartesian products) Let \(M := \{1,2\}\) and \(N := \{1,2,3\}\). Then the Cartesian product \(M\times N\) is given by \[\begin{equation} M \times N := \{(1,1), (1,2), (1,3), (2,1), (2,2), (2,3)\} \end{equation}\] and the Cartesian product \(N \times M\) is given by \[\begin{equation} N \times M := \{(1,1), (1,2), (2,1), (2,2), (3,1), (3,2)\}. \end{equation}\] The Cartesian product is therefore generally not commutative. It need not be the case that \(M \times N = N \times M\). The sets \(M \times N \neq N \times M\) in this example can be constructed using Table 2.1 and Table 2.2.
| \((m,n)\) | \(n = 1\) | \(n = 2\) | \(n = 3\) |
|---|---|---|---|
| \(m = 1\) | \((1,1)\) | \((1,2)\) | \((1,3)\) |
| \(m = 2\) | \((2,1)\) | \((2,2)\) | \((2,3)\) |
| \((n,m)\) | \(m = 1\) | \(m = 2\) |
|---|---|---|
| \(n = 1\) | \((1,1)\) | \((1,2)\) |
| \(n = 2\) | \((2,1)\) | \((2,2)\) |
| \(n = 3\) | \((3,1)\) | \((3,2)\) |
\(\mathbb{R}\) to the Power of \(n\)
As described above, the real numbers are particularly suitable for describing continuous phenomena. For the simultaneous description of several aspects of a continuous phenomenon, the set of real tuples of \(n\)-th order, or \(\mathbb{R}\) to the power of \(n\) for short, is correspondingly useful.
Definition 2.13 (Set of real tuples of \(n\)-th order) The \(n\)-fold Cartesian product of the real numbers with themselves is denoted by \[\begin{equation} \mathbb{R}^n := \times_{i = 1}^{n} \mathbb{R} := \{x := (x_1,\ldots,x_n) | x_i \in \mathbb{R} \text{ for } i = 1,\ldots,n\}. \end{equation}\] and is read as “\(\mathbb{R}\) to the power of \(n\)”. We write the elements of \(\mathbb{R}^n\) as columns \[\begin{equation} x := \begin{pmatrix} x_1 \\ \vdots \\ x_n \end{pmatrix} \end{equation}\] and call them \(n\)-dimensional vectors. For distinction, we also call the elements of \(\mathbb{R}^1 = \mathbb{R}\) scalars.
Example 2.5 (Real vectors) Familiar examples of \(\mathbb{R}^n\) are \(\mathbb{R}^1\) as the set of real numbers, \(\mathbb{R}^2\) as the set of real tuples in the model of the two-dimensional plane, and \(\mathbb{R}^3\) as the set of real triples in the model of three-dimensional space. Figure 2.8 illustrates these three cases.
An example of a vector \(x \in \mathbb{R}^4\) is \[\begin{equation} x = \begin{pmatrix} 0.16 \\ 1.76 \\ 0.23 \\ 7.11 \end{pmatrix}. \end{equation}\]
Study questions
- State Cantor’s (1895) definition of a set.
- Name three ways to define a set.
- Explain the expressions \(m \in M\) and \(m \notin M\).
- Explain the expressions \(M \subseteq N\) and \(M \subset N\) for two sets \(M\) and \(N\).
- State the definition of the cardinality of a set.
- State the definition of the power set of a set.
- Let \(M := \{1,2\}\). Determine \(\mathcal{P}(M)\).
- Let \(M := \{1,2\}\) and \(N := \{1,4,5\}\). Determine \(M \cup N\), \(M \cap N\), \(M \setminus N\), and \(M \Delta N\).
- Explain the symbols \(\mathbb{N}\), \(\mathbb{N}_n\), and \(\mathbb{N}^0\).
- Explain the differences between \(\mathbb{N}\) and \(\mathbb{Z}\) and between \(\mathbb{R}\) and \(\mathbb{Q}\).
- State the definitions of closed, open, and half-open intervals.
- Let \(M\) and \(N\) be sets. Explain the notation \(M \times N\).
- State the definition of \(\mathbb{R}^n\).
Study question answers
- See Definition 2.1.
- See Definition 2.1.
- See Definition 2.1.
- See Definition 2.2.
- See Definition 2.3.
- See Definition 2.5.
- We have \(\mathcal{P}(M) = \{\emptyset, \{1\}, \{2\}, \{1,2\}\}\).
- We have \(M \cup N = \{1,2,4,5\}\), \(M \cap N = \{1\}\), \(M \setminus N = \{2\}\), and \(M \Delta N = \{2,4,5\}\).
- \(\mathbb{N}\) denotes the natural numbers \(1,2,...\). \(\mathbb{N}_n\) denotes the natural numbers up to and including \(n\), that is, \(1,2,...,n\). \(\mathbb{N}^0\) denotes the natural numbers and zero, that is, \(0,1,2,...\).
- \(\mathbb{Z}\) contains the negative natural numbers and zero, whereas \(\mathbb{N}\) does not. In addition to the rational numbers \(\mathbb{Q}\), \(\mathbb{R}\) contains numbers that cannot be represented as rational numbers, such as the circle constant \(\pi\).
- See Definition 2.11.
- See Definition 2.12.
- See Definition 2.13.