Skip to main content

Foundations of Advanced Mathematics

Sam Macdonald

Section 6.2 Finite and Countable Sets

Definition 6.19.

Let \(A\) be a set. Suppose that \(A\) is finite. The cardinality of \(A\text{,}\) denoted \(|A|\text{,}\) is defined as follows. If \(A = \es\text{,}\) let \(|A| = 0\text{.}\) If \(A \neq\es\text{,}\) let \(|A| = n\text{,}\) where \(A \#\{1, \dots, n\}\text{.}\)
Let \(X \subseteq A\text{.}\)
If \(A\) is finite, then by Theorem 6.6.5 (1) we know that \(X\) is finite, and hence it is countable. Now assume that \(A\) is countably infinite. We will prove the theorem for the special case that \(A = \N\text{.}\) For the general case, we observe that if \(A\) is countably infinite, then there is a bijective function \(f : A \to\N\text{,}\) and the desired result follows from the fact that \(X \# f (X)\text{,}\) which holds by Exercise 6.5.4, and that \(f (X)\) is a subset of \(\N\text{.}\)
Suppose that \(A = \N\text{.}\) If \(X\) is finite, then it is countable by definition, and there is nothing to prove. Now suppose that \(X\) is infinite.
By the Well-Ordering Principle (Theorem 6.2.5), there is a unique element \(b\in X\) such that \(b \leq x\) for all \(x\in X\text{.}\) Let \(k : G(X) \to X\) be defined as follows. Let \(g\in G(X)\text{.}\) Then \(g\in F (\{1, \dots, n\}, X)\) for some \(n\in\N\text{,}\) which means that \(g\) is a function \(\{1, \dots, n\} \to X\text{.}\) It follows from Exercise 6.6.3 that \(g\) cannot be surjective, and hence \(X \sm g(\{1, \dots, n\}) \neq\es\) . Using the Well-Ordering Principle again we see that there is a unique element \(z_g\in X \sm g(\{1, \dots, n\})\) such that \(z_g \leq x\) for all \(x\in X \sm g(\{1, \dots, n\})\text{.}\) We then let \(k(g) = z_g\text{.}\)
We can apply Theorem 6.4.8 to \(b\) and \(k\) as above, and we deduce that there is a unique function \(f : \N \to A\) such that \(f (1) = b\text{,}\) and that \(f (n + 1) = k( f_|\{1,...,n\})\) for all \(n\in\N\text{.}\) Hence \(f (1) \leq x\) for all \(x\in X\text{,}\) and if \(n\in\N\text{,}\) then \(f (n + 1)\in X \sm [ f |_{1,...,n}](\{1, \dots, n\}) = X \sm f (\{1, \dots, n\})\text{,}\) and so \(f (n + 1) \leq y\) for all \(y\in X \sm f (\{1, \dots, n\})\text{.}\)
Let \(r\in\N\text{.}\) Then \(f (r) \leq y\) for all \(y\in X \sm f (\{1, \dots, r - 1\})\text{,}\) where we think of \(\{1, \dots, 0\}\) as the empty set when \(r = 1\text{.}\) Because \(f (r + 1)\in X \sm f (\{1, \dots, \}) \subseteq X - f (\{1, \dots, r - 1\})\text{,}\) it follows that \(f (r) < f (r + 1)\text{.}\) By Exercise 6.3.4 we see that \(f (n) ≥ n\) for all \(n\in\N\text{.}\)
We now show that \(f\) is bijective. Let \(i, j\in\N\text{.}\) Suppose that \(i \neq j\text{.}\) Without loss of generality assume that \(i < j\text{.}\) Then \(i \leq j - 1\text{,}\) and also \(j > 1\text{,}\) so that \(j - 1\in\N\text{.}\) It follows that \(f (i)\in f (\{1, \dots, j - 1\})\text{,}\) and as observed above we know that \(f ( j)\in X \sm f (\{1, \dots, j - 1\})\text{.}\) Therefore \(f (i) \neq f ( j)\text{,}\) and we deduce that f is injective.
Let \(m\in X\text{.}\) Suppose that \(m \neq f (p)\) for any \(p\in\N\text{.}\) Using a previous observation we know that \(m \leq f(m)\text{,}\) and hence \(m < f(m)\text{.}\) On the other hand, we saw above that \(f(m) \leq y\) for all\(y\in X \sm f (\{1, \dots, m - 1\})\text{.}\) By hypothesis on \(m\) we know that \(m \not\in f (\{1, \dots, m - 1\})\text{,}\) and it follows that \(f(m) \leq m\text{,}\) which is a contradiction. Therefore \(f\) is surjective.
We conclude that \(f\) is bijective, which implies that \(X \#\N\text{.}\) Hence \(X\) is countably infinite, and therefore countable.
  • \((a) ⇒ (b)\text{.}\) Suppose that \(A\) is countable. There are two cases, depending upon whether \(A\) is finite or countably infinite. If \(A\) is finite, there is a bijective function \(k : A \to\{1, \dots, n\}\) for some \(n\in\N\text{,}\) and hence there is an injective function \(ˆk : A \to N\text{,}\) because \(\{1, \dots, n\} \subseteq\N\text{.}\) If \(A\) is countably infinite, there is a bijective function \(h : X \to N\text{,}\) which is injective.
  • \((b) ⇒ (a)\text{.}\) Suppose that there is an injective function \(f : A \to\N\text{.}\) Because \(f\) is injective, it follows from Exercise 6.5.4 that \(A \# f(a)\text{.}\) By Theorem 6.6.7 we know that \(f(a)\) is countable, and therefore \(A\) is countable.
  • \((b) ⇔ (c)\text{.}\) Suppose that there is an injective function \(f : A \to N\text{.}\) By Theorem 4.4.5 (2) the function \(f\) has a left inverse, say \(g : N \to A\text{.}\) By Exercise 4.4.13 (1) we see that \(g\) is surjective. The other implication is proved similarly, and we omit the details.
  1. Choose some \(k\in I\text{.}\) Then \(⋂i\in I Ai \subseteq Ak\text{,}\) and hence \(⋂i\in I Ai\) is countable by Theorem 6.6.7.
  2. If \(A_i = \es\) for all \(i\in I\text{,}\) then \(\bigcup_{i\in I} A_i = \es\text{,}\) which implies that \(\bigcup_{i\in I} A_i\) is finite, and hence countable. Now assume that \(Ak \neq\es\) for some \(k\in I\text{.}\) Because the empty set contributes nothing to a union of sets, the set \(\bigcup i\in I Ai\) will not be changed if we delete from \(I\) those elements \(s\in I\) such that \(A_s = \es\) . Let us assume that that has been done, and therefore that \(A_i \neq\es\) for all \(i\in I\text{.}\)
    There are two cases, depending upon whether \(I\) is countably infinite or is finite. We prove the former case, leaving the other case to the reader in Exercise 6.6.12. Because we are assuming that \(I\) is countably infinite, without loss of generality we may assume that \(I = \N\text{.}\)
    Because \(A_i\) is countable for all \(i\in I\text{,}\) then by Theorem 6.6.8 there is a surjective function \(f_i : N \to A_i\) for each \(i\in I\text{.}\) Let \(g : \N \to \bigcup_{i\in I} A_i\) be defined as follows. Let \(r\in \N\text{.}\) We can apply Exercise 6.3.14 to the function \(f : \N \to \N\) defined by \(f (n) = (n-1)n^2\) for all \(n\in \ N\text{,}\) and we deduce that there are unique \(n, p\in \N\) such that \((n-1)n^2 < r \leq n(n+1)^2\) and \(r = (n-1)n^2 + p\text{.}\) Let \(g(r) = f n-p+1(p)\text{.}\)
    Let \(x\in \bigcup_{i\in I} A_i\text{.}\) Then \(x\in A_k\) for some \(k\in I\text{.}\) Because \(f_k\) is surjective, there is some \(w\in \N\) such that \(x = f_k(w)\text{.}\) Let \(t = k + w - 1\text{.}\) The reader can then verify that \(g( (t-1)t 2 + w) = f t-w+1(w) = f k(w) = x\text{.}\) Therefore \(g\) is surjective, and it follows from Theorem 6.6.8 that \(\bigcup_{i\in I} A_i\) is countable.

Remark 6.27.

Observe that in the proof of Theorem 6.6.9 (2), we simultaneously had to choose a surjective function \(f_i : \N \to A_i\) for each \(i\in I\text{;}\) there really is a choice to be made, because there is more than one such function for each \(i\in I\) (except when \(A_i\) has only one element in it). Hence, we are making use of the Axiom of Choice (Theorem 4.1.5). To use that axiom formally in this proof, we would let \(S_i\) denote the set of all surjective functions \(N \to A_i\) for each \(i\in I\text{,}\) and we would apply the Axiom of Choice to the family of sets \(\{Si\}_{i\in I}\text{;}\) we omit the details. It is pointed out in [Vau95, p. 56] that any proof of Theorem 6.6.9 (2) requires the Axiom of Choice.
Suppose that \(A\) is infinite. By the Trichotomy Law for Sets (Theorem 6.5.13) we know that \(\N\into A or A\into \N\text{.}\)
First, suppose that \(\N\into A\text{.}\) Then there is an injective function \(f : \N \to A\text{.}\) By Exercise 6.5.4 we know that \(\N \# f (N)\text{.}\) Hence \(f (\N)\) is a countably infinite subset of \(A\text{.}\)
Second, suppose that \(A\into \N\text{.}\) Then there is an injective function \(g : A \to \N\text{.}\) By Exercise 6.5.4 again we know that \(A \# g(A)\text{.}\) Because \(g(A) \subseteq \N\text{,}\) it follows from Theorem 6.6.7 that \(g(A)\) is countable. Hence \(A\) is countable. Because \(A\) is infinite, then it must be countably infinite, and hence A has a countably infinite subset, namely, itself.
Let \(A\) and \(B\) be sets. Suppose that \(A\) and \(B\) are finite. Prove that \(A \cup B\) is finite.
Let \(A \subseteq \N\) be a subset. Suppose that there is some \(M\in N\) such that \(a \leq M\) for all \(a\in A\text{.}\) Prove that \(A\) is finite.
Let \(A\) be a set. Prove that \(A\) is finite if and only if there is an injective function \(f : A \to \{1, \dots, n\}\) for some \(n\in \N\) if and only if there is a surjective function \(f : \{1, \dots, n\} \to A\) for some \(n\in \N\text{.}\)
Let \(A\) and \(B\) be sets, and let \(f : A \to B\) be a function. Suppose that \(A\) and \(B\) are finite sets, and that \(|A| = |B|\text{.}\) Prove that \(f\) is bijective if and only if \(f\) is injective if and only if \(f\) is surjective.
Let \(F \subseteq \N\) be a set. Suppose that \(F\) is finite and non-empty. Use Theorem 6.3.11 (1) to prove that there is some \(k\in F\) such that \(p \leq k\) for all \(p\in F\text{.}\)
Let \(X\) be a set. Suppose that \(X\) is countably infinite. Prove that there is a function \(f : X \to X\) that is injective but not surjective.
Let \(A\) be a set. Prove that \(A\) is uncountable if and only if it contains an uncountable subset.
Let \(A\) and \(B\) be sets. Suppose that \(A\) and \(B\) are countable. Prove that \(A \times B\) is countable.
<Prev^TopNext>