Definition 6.1.
Let \(A\) and \(B\) be sets. The sets \(A\) and \(B\) are equinumerous, denoted \(A \# B\) (more commonly \(|A|=|B|\)), if there is a bijective function \(f : A \to B\text{.}\)
Section 6.1 Cardinality of Sets
Convention 6.2.
Don't like the \(\sim\) notation.
Theorem 6.3.
Warning 6.4. Almost Equivalent.
Lemma 6.5.2 might lead the reader to think of \(\#\) as an equivalence relation, but we need to proceed with caution here. If \(\#\) were a relation, on what set would it be a relation? We might want to think of \(\#\) as a relation on the set of all sets, because for any two sets \(A\) and \(B\text{,}\) it must be the case that either \(A \# B\) or \(A \not \# B\text{.}\) However, because of foundational problems such as Russell's Paradox, which was discussed in Section 3.5, we avoid things such as the set of all sets. Hence, although \(\#\) satisfies the three properties of an equivalence relation, it is not technically a relation on a set at all. If, however, all sets of interest are subsets of a given set \(X\text{,}\) then it is correct to say that \(\#\) is an equivalence relation on \(\cP(X)\text{.}\)
Definition 6.5.
Let \(A\) be a set.
- The set \(A\) is said to be finite if it is either the empty set or \(A \# \{1, \dots, n\}\) for some \(n\in\N\text{.}\)
- The set \(A\) is said to be infinite if it is not finite.
- The set \(A\) is said to be countably infinite if \(A \# \N\text{.}\)
- The set \(A\) is said to be countable (also called denumerable) if it is finite or countably infinite.
- The set \(A\) is said to be uncountable if it is not countable.
Theorem 6.6.
Let \(A\) and \(B\) be sets. Suppose that \(A \# B\text{.}\) If \(A\) is finite, infinite, countably infinite, countable or uncountable, then so is \(B\text{.}\)
Theorem 6.7.
- The set \(\N\) is infinite.
- A countably infinite set is infinite.
Proof.
- Suppose that \(\N\) is finite. Because \(\N \neq \es\text{,}\) then there is some \(n\in\N\) such that \(\N \# \{1, \dots, n\}\text{.}\) Let \(f : \{1, \dots, n\} \to\N\) be a bijective function. It then follows from Theorem 6.3.11 (1) that there is some \(k\in\{1, \dots, n\}\) such that \(f (k) ≥ f (i)\) for any \(i\in\{1, \dots, n\}\text{.}\) Therefore \(f (k) + 1 > f (i)\) for all \(i\in\{1, \dots, n\}\text{.}\) Hence \(f (k) + 1 \not\in f (\{1, \dots, n\})\text{.}\) Because \(f (k) + 1\in\N,\) we deduce that \(f\) is not surjective, which is a contradiction. Hence \(N\) is not finite, and so it is infinite.
- Let \(B\) be a set. Suppose that \(B\) is countably infinite. Then \(B \# N\text{.}\) Suppose further that \(B\) is finite. It would then follow from Exercise 6.5.5 that \(N\) is finite, which is a contradiction to Part (1) of this lemma. Hence \(B\) is infinite.
Theorem 6.8.
Let \(A\) be a set. Then \(A \not\# \cP (A)\text{.}\)
Proof.
There are two cases. First, suppose that \(A = \es\text{.}\) Observe that \(\cP (A) = \{ \es \}\text{,}\) and therefore there cannot be a bijective function \(\cP (A) \to A\text{,}\) because there cannot be a function from a non-empty set to the empty set. Hence \(\cP (A) \not\sim A\text{.}\)
Next, suppose that \(A \neq\es\text{.}\) Suppose further that \(A \sim\cP (A)\text{.}\) Then there is a bijective function \(f : A \to\cP (A)\text{.}\) Let \(D = \{a\in A | a /\in f(a)\}\text{.}\) Observe that \(D \subseteq A\text{,}\) and so \(D\in\cP (A)\text{.}\) Because \(f\) is surjective, there is some \(d\in A\) such that \(f (d) = D\text{.}\) Is \(d\in D\text{?}\) Suppose that \(d\in D\text{.}\) Then by the definition of \(D\) we see that \(d \not\in f (d) = D\text{.}\) Suppose that \(d \not\in D\text{.}\) Then \(d\in f (d) = D\text{.}\) We therefore have a contradiction, and so \(A \not\sim\cP (A)\text{.}\)
Corollary 6.9.
The set \(\cP (\N)\) is uncountable.
Proof.
By Theorem 6.5.7 we know that \(\cP (\N) \not\sim N\text{,}\) and so \(\cP (\N)\) is not countably infinite. If we could show that \(\cP (\N)\) were not finite, then it would follow that it is not countable. Suppose that \(\cP (\N)\) is finite. Let \(T = \{{n} | n\in N\} \subseteq\cP (\N)\text{.}\) It follows from Theorem 6.6.5 (1) that \(T\) is finite. However, it is evident that \(T \sim\N\text{,}\) and this would imply that \(\N\) is finite, which is a contradiction to Lemma 6.5.5 (1). We conclude that \(\cP (\N)\) is uncountable.
Definition 6.10.
Let \(A\) and \(B\) be sets. We say that \(A\into B \)if there is an injective function \(f : A \to B\text{.}\)
Convention 6.11.
Notation I like better
Theorem 6.12.
Let \(A\text{,}\) \(B\) and \(C\) be sets. Then the following hold:
- \(\es\into A\text{.}\)
- \(A\into A\text{.}\)
- If \(A\into B\) and \(B\into C\text{,}\) then \(A\into C\text{.}\)
Lemma 6.13.
Let \(A\text{,}\) \(B\) and \(C\) be sets. Suppose that \(C \subseteq B \subseteq A\text{,}\) and that \(A\into C\text{.}\) Then \(A \# B\text{.}\)
Theorem 6.14.
Let \(A\) and \(B\) be sets. Suppose that \(A\into B\) and \(B\into A\text{.}\) Then \(A \# B\text{.}\)
Proof.
By definition there are injective functions \(p : A \to B\) and \(q : B \to A\text{.}\) Then \(p(A) \subseteq B\text{,}\) and \(q(p(A)) \subseteq q(B) \subseteq A\text{.}\) By Exercise 6.5.4 we know that \(q(p(A)) \# A\) and \(q(B) \# B\text{.}\) From the former it follows that \(A\into q(p(A))\text{,}\) and we then use Lemma 6.5.11 to deduce that \(A \# q(B)\text{.}\) Hence \(A \# B\text{.}\)
Example 6.15.
Let \(a, b\in\R\text{.}\) Suppose that \(a < b\text{.}\) We will use the Schroeder-Bernstein Theorem (Theorem 6.5.10) to prove that \([a, b] \# (a, b)\text{.}\) By Example 6.5.3 (3) we know that \([a, b] \# [-1, 1]\) and \((a, b) \# (-1, 1)\text{.}\) Hence, it will suffice to prove that \((-1, 1) \# [-1, 1]\text{.}\) Let \(f : (-1, 1) \to [-1, 1]\) be defined by \(f (x) = x\) for all \(x\in (-1, 1)\text{,}\) and let \(g : [-1, 1] \to (-1, 1)\) be defined by \(g(x) = x^2\) for all \(x\in [-1, 1]\text{.}\) Then both \(f\) and \(g\) are injective, and hence \((-1, 1)\into [-1, 1]\) and \([-1, 1]\into (-1, 1)\text{.}\) The Schroeder-Bernstein Theorem now implies that \([-1, 1] \# (-1, 1)\text{,}\) and therefore \([a, b] \# (a, b)\text{.}\)
Theorem 6.16.
Let \(A\) and \(B\) be sets. Then \(A\into B\) or \(B\into A\text{.}\)
Proof.
We need to show that there is an injective function \(f : A \to B\) or an injective function \(g : B \to A\text{.}\) If \(A\) or \(B\) is empty these functions exist trivially, so we will assume that \(A\) and \(B\) are both non-empty.
A partial function from \(A\) to \(B\) is a function of the form \(f : J \to B\text{,}\) where \(J \subseteq A\text{.}\) We can think of a partial function from \(A\) to \(B\) as a subset \(F \subseteq A \times B\) such that for each \(a\in A\text{,}\) there is at most one pair in \(F\) of the form \((a, b)\text{.}\) Hence, we can apply the concepts of subset and union to partial functions from \(A\) to \(B\text{.}\)
Let \(P\) be the set of all injective partial functions from \(A\) to \(B\text{.}\) Observe that \(P \neq\es\text{,}\) because \(\es \in P\) . Let \(C\) be a chain in \(P\) . We claim that \(\bigcup _{F\in C} F\in P\) . Suppose that \((a, b)\text{,}\) \((a, c)\in \bigcup F\in C C\text{,}\) for some \(a\in A\) and \(b, c\in B\text{.}\) Then \((a, b)\in G\) and \((a, c)\in H\) for some partial functions \(G, H\in C\) . Because \(CC\) is a chain, we know that \(G \subseteq H\) or \(G ⊇ H\text{.}\) Without loss of generality assume that \(G \subseteq H\text{.}\) Then \((a, b)\) and \((a, c)\) are both in \(H\text{,}\) and because \(H\) is a partial function, then it must be the case that \(b = c\text{.}\) We conclude that \(\bigcup F\in C F\) is a partial function from \(A\) to \(B\text{.}\) Next, suppose that \((c, e), (d, e)\in \bigcup F\in C C\text{,}\) for some \(c, d\in A\) and \(e\in B\text{.}\) A similar argument shows that \((c, e) and (d, e)\) must both be in some \(K\in C\text{,}\) and because \(K\) is an injective partial function, then it must be the case that \(c = d\text{.}\) We conclude that \bigcup \(F\in C F\) is an injective partial function from \(A\) to \(B\text{,}\) and hence that \(\bigcup F\in C F\in P\) .
By Zorn's Lemma (Theorem 3.5.6) the family of sets \(P\) has a maximal element. Let \(M\in P\) be such a maximal element. Then \(M\) is an injective partial function from \(A\) to \(B\text{.}\) There are now three cases. First, suppose that for each \(a\in A\text{,}\) there is a pair of the form \((a, b) in M\text{.}\) Then \(M\) is an injective function \(A \to B\text{.}\) Second, suppose that for each \(d\in B\text{,}\) there is a pair of the form \((c, d)\in M\text{.}\) Then \(M\) is a bijective partial function from \(A to B\text{,}\) and using Exercise 4.4.13 (3) we see that the inverse function of \(M\) can be viewed as an injective function \(B \to A\text{.}\) Third, suppose that neither of the previous two cases holds. Then there is some \(x\in A\) such that there is no pair of the form \((x, b)\) in \(M\text{,}\) and there is some \(y\in B\) such that there is no pair of the form \((a, y)\in M\text{.}\) Let \(N = M \cup\{(x, y)\}\text{.}\) It is left to the reader to verify that \(N\) is an injective partial function from \(A\) to \(B\text{,}\) and hence that \(N\in P\) . Because \(M $ N\text{,}\) we have a contradiction to the fact that \(M\) is a maximal element of \(P\text{,}\) and so this third case cannot happen.
Exploration 6.17.
Let \(A\) and \(B\) be sets, let \(X \subseteq A\) be a subset and let \(f : A \to B\) be a function. Suppose that \(f\) is injective. Prove that \(X \# f (X)\text{.}\)
Exploration 6.18.
- Give an example of sets \(A\text{,}\) \(B\) and \(C\) such that \(A \# B\) and \(A \cup C \not\# B \cup C\text{.}\)
- Let \(A\text{,}\) \(B\) and \(C\) be sets. Suppose that \(A \# B\) and that \(A \cap C = \es\) and \(B \cap C = \es\) . Prove that \(A \cup C \# B \cup C\text{.}\)
- Let \(A\text{,}\) \(B\) and \(C\) be sets. Suppose that \(A \cup C \# B \cup C\) and that \(A \cap C = \es\) and \(B \cap C = \es\) . Is it necessarily the case that \(A \# B\text{?}\) Give a proof or a counterexample.
