MATH 1800
When we started looking at sets, we defined the cardinality of a finite set \(A\), denoted by \(\lvert A \rvert\), to be the number of elements of \(A\). We now formalize the notion and extend the notion of cardinality to sets that do not have a finite number of elements.
Let \(A\) and \(B\) be sets. \(A\) and \(B\) are said to be equipotent (or equinumerous), denoted by \(\lvert A \rvert = \lvert B \rvert\), if there exists \(f:A \rightarrow B\) that is bijective. We write \(\lvert A \rvert \neq \lvert B \rvert\) if \(A\) and \(B\) are not equipotent.
We write \(\lvert A \rvert \leq \lvert B \rvert\), or \(\lvert B \rvert \geq \lvert A \rvert\), if there exists \(f:A\rightarrow B\) that is injective.
We write \(\lvert A \rvert < \lvert B \rvert\), or \(\lvert B \rvert > \lvert A \rvert\), if \(|A| \leq |B|\) and \(|A| \neq |B|\).
\(|\mathbb{Z}| \leq |\mathbb{Q}|\).
\(A = \{ x \in \mathbb{N} \mid x \text{ is even}\}\) is equipotent to \(\mathbb{N}\) since the function \(f\) given by \(f(n) = \frac{n}{2}\) is a bijection between \(A\) and \(\mathbb{N}\).
Georg Cantor proved that \(|\mathbb{N}| = |\mathbb{Q}| < |\mathbb{R}|\).
The cardinality of the empty set is defined to be \(0\).
For a positive integer \(n\), define \([n]\) to be the set \(\{1,\ldots,n\}\). A set \(A\) is finite if it is empty or if it is equipotent to \([n]\) for some positive integer \(n\). In the latter case, \(|A|\) is defined to be \(n\).
Remark. When defining the cardinality of a finite set, we implicitly assumed that it is a unique positive integer. This seemingly “obvious” fact actually requires proof which is usually discussed in a course in set theory. In this course, we will take for granted that the cardinality of a finite set is a unique positive integer.
For example, \(A = \{2,4,\sqrt{7}\}\) is equipotent to \([3]\) since the function \(f\) given by \(f(2) = 1\), \(f(4) = 2\), and \(f(\sqrt{7}) = 3\) is a bijection. Thus, \(|A| = 3\).
There are many counting problems that have simple solutions once we have proved the inclusion-exclusion principle. The questions below can all be answered using the theorem.
How many natural numbers at most \(100\) are divisible by \(2\) or \(3\)?
How many three-digit numbers begin with a 1 or end with a 5?
We first prove an intermediate result that seems “obvious”.
Lemma. If \(A\) and \(B\) are disjoint finite sets, then \(|A\cup B| = |A| + |B|\).
Proof.
The statement clearly holds if either \(A\) or \(B\) is the empty set.
We assume that neither \(A\) nor \(B\) is empty.
Let \(m\) and \(n\) be positive integers such that \(|A| = m\) and \(|B| = n\). Let \(f\) be a bijection between \(A\) and \([m]\) and let \(g\) be a bijection between \(B\) and \([n]\). Define \(h:[m+n]\rightarrow A\cup B\) by \[h(i) = \left\{\begin{array}{ll} f(i) & \text{if } 1 \leq i \leq m \\ g(i-m) & \text{if } m+1 \leq i \leq m+n \end{array} \right.\] Thus, \(\{h(1),\dots,h(m)\} = \{f(1),\ldots,f(m)\} = A\) and \(\{h(m+1),\dots,h(m+n)\} = \{g(1),\ldots,g(n)\} = B\). It follows that \(h\) is surjective.
We now prove that \(h\) is injective as well. Since \(A \cap B = \emptyset\), \(h(i) \neq h(j)\) for all \(i \in \{1,\ldots,m\}\) and \(j \in \{m+1,\ldots, m+n\}\). As well, \(h(1),\dots,h(m)\) are distinct and \(h(m+1),\ldots,h(m+n)\) are disjinct since \(f\) and \(g\) are bijective. It follows that \(h(1),\ldots,h(m+n)\) are distinct, implying that \(h\) is injective.
As \(h\) is a bijection between \([m+n]\) and \(A\cup B\), we have \(|A \cup B| = m+n = |A| + |B|\) as desired.
Theorem. (Inclusion-exclusion principle for two sets)
Let \(A\) and \(B\) be finite sets. Then \(|A\cup B| + |A\cap B| = |A| + |B|\).
Proof. Let \(U\) be the universe of discourse. One can easily show the following:
\(A = (A \cap B) \cup (A\cap \overline{B});\)
\(A \cap B\) and \(A\cap \overline{B}\) are disjoint;
\(A\cap \overline{B}\) and \(B\) are disjoint.
Then by the lemma above, \(|A| = |A \cap B|+|A\cap \overline{B}|\) and \(|(A\cap\overline{B})\cup B| = |A\cap \overline{B}| + |B|\). Hence, \[\begin{align} & |A| + |B| = |A \cap B|+|A\cap \overline{B}|+|B| \\ = & |A \cap B|+|(A\cap \overline{B})\cup B| \\ = & |A \cap B|+|(A\cup B)\cap (\overline{B}\cup B)| \\ = & |A \cap B|+|(A\cup B)\cap U| \\ = & |A \cap B|+|A\cup B|. \end{align}\]
A set that is not finite is said to be infinite.
An infinite set equipotent to \(\mathbb{N}\) is said to be countably infinite (or denumerable). Otherwise, it is said to be uncountable.
A set that is either finite or countably infinite is said to be countable. (Note that some resources use “countable” to mean “countably infinite”.)
To see where these descriptive words came from, note that if there exists \(f:\mathbb{N} \rightarrow A\) that is bijective. then the elements of \(A\) are simply \(f(0), f(1), f(2),\ldots\), implying that the elements of \(A\) can be counted out or listed one by one.
It is perhaps a bit surprising that \(\mathbb{Q}\) is countable whereas \(\mathbb{R}\) is not even though both sets look “dense” on the number line. Also, \(\mathbb{N}\) looks much sparser than \(\mathbb{Q}\) on the number line yet they have the same cardinality.
Schröder-Bernstein Theorem.
Let \(A\) and \(B\) be sets. If \(|A| \leq |B|\) and \(|B| \leq |A|\), then \(|A| = |B|\).
Despite the simple appearance of this theorem, the proof is quite involved and will not be discussed in this course. The challenge is in constructing a bijection between \(A\) and \(B\) from an injection from \(A\) to \(B\) and an injection from \(B\) to \(A\).
We show that \(|\mathbb{R}_{\geq 0}| = |\mathbb{R}|\) in two ways:
Using Schröder-Bernstein Theorem:
Note that \(g:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}\) given by \(g(x) = x\) is injective. Thus, \(|\mathbb{R}_{\geq 0}| \leq |\mathbb{R}|\).
Now, note that \(h:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}\) given by \(h(x) = 2^x\) is injective. Thus, \(|\mathbb{R}| \leq |\mathbb{R}_{\geq 0}|\). By the Schröder-Bernstein Theorem, we have \(|\mathbb{R}| = |\mathbb{R}_{\geq 0}|\).
Constructing a bijection \(f:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}\):
Looking at the function \(h\) above, the function \(\log_2 x\) is nearly what we want because it is a bijection between \(\mathbb{R}_{>0}\) and \(\mathbb{R}\). However, \(\log_2 x\) is undefined at \(x = 0\). We need to find a way to map 0 to somewhere in \(\mathbb{R}\). What we will do is to map \(n\) to \(\log_2 (n+1)\) for each \(n \in \mathbb{N}\) and \(x\) to \(\log_2 x\) for each \(x \notin \mathbb{N}\) as usual. Namely, let \(f:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}\) be given by \[f(x) = \left \{ \begin{array}{ll} \log_2 (x + 1) & \text{if } x \in \mathbb{N} \\ \log_2 x & \text{otherwise}. \end{array} \right.\] We prove that \(f\) is bijective.
First, we show that \(f\) is injective. Let \(u,v \in \mathbb{R}_{\geq 0}\) be such that \(u \neq v\).
Suppose that \(u,v \in \mathbb{N}\). Then \(f(u) = \log_2 (u+1)\) and \(f(v) = \log_2 (v+1)\). If \(f(u) = f(v),\) then \(\log_2 (u+1)= \log_2 (v+1),\) implying that \(2^{\log_2 (u+1)}= 2^{\log_2 (v+1)},\) giving \(u+1 = v+1\), which is impossible since \(u \neq v\).
Suppose that \(u \in \mathbb{N}\) but \(v \notin \mathbb{N}\). Then \(f(u) = \log_2 (u+1)\) and \(f(v) = \log_2 v\). If \(f(u) = f(v),\) then \(\log_2 (u+1)= \log_2 v,\) implying that \(u+1 = v.\) Since \(u + 1 \in \mathbb{N}\), this contradicts that \(v \notin \mathbb{N}\). The case when \(v \in \mathbb{N}\) but \(u \notin \mathbb{N}\) is similar.
Finally, suppose that \(u, v \notin \mathbb{N}\). Then \(f(u) = \log_2 u\) and \(f(v) = \log_2 v\). If \(f(u) = f(v),\) then \(\log_2 u= \log_2 v,\) implying that \(u = v\), a contradiction.
Thus, \(f\) is injective.
To complete the proof, we show that \(f\) is surjective.
Let \(y \in \mathbb{R}\). If \(y = \log_2 k\) for some positive integer \(k\), then \(k-1 \in \mathbb{N}\) and so \(f(k-1) = \log_2 (k-1+1) = \log_2 k = y\).
Suppose that there is no positive integer \(k\) such that \(y = \log_2 k\). Let \(x = 2^y\). Then \(x > 0\) and \(x \notin \mathbb{N}\). Thus, \(f(x) = \log_2 (2^y) = y\).
Hence, \(f\) is surjective.
Determine the number of natural numbers at most \(100\) divisible by \(3\) or \(5\) or both.
Let \(k\) and \(n\) be positive integers with \(k \leq n\). Let \(A\) denote the set of all \(k\)-element subsets of \(\{1,\ldots,n\}\). Let \(B = \{ (x_1,\ldots,x_n) \in \{0,1\}^n \mid \sum_{i=1}^n x_i = k \}\). Prove that \(|A| = |B|\) by constructing a bijection between \(A\) and \(B\).
Let \(A_1,\ldots,A_n\) be finite sets where \(n\) is a positive integer. Use the method of mathematical induction to prove that \[\left \lvert \bigcup_{i=1}^n A_i \right \rvert = \sum_{k=1}^n (-1)^{k+1} \left ( \sum_{1\leq i_1 < \cdots < i_k \leq n} \lvert A_{i_1} \cap \cdots \cap A_{i_k} \rvert \right ).\]
Let \(A\) and \(B\) be finite sets such that \(|A| = m\) and \(|B| = n\) where \(m\) and \(n\) are positive integers satisfying \(m > n\). Prove that there is no bijection between \(A\) and \(B\). (Hint: Use induction on \(n\).)
Let \(A\) be a set. Prove that \(\lvert A \rvert < \lvert {\cal P}(A) \rvert.\) (Hint: Suppose that there were a surjection \(f: A \rightarrow {\cal P}(A)\). What can you say about the set \(S = \{ a \in A \mid a \notin f(a) \}\)?)
Let \(R = \{ x \in \mathbb{R} \mid 0 \leq x < 1\}\). Let \(S = \{ x\in \mathbb{R} \mid 0 \leq x \leq 1\}\).
Show that \(|R| = |S|\) using the Schröder-Bernstein Theorem.
Give an explicit description of a bijection between \(R\) and \(S\).