9.S: Finite and Infinite Sets (Summary)
- Page ID
- 7089
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)
Important Definitions
- Equivalent sets, page 452
- Sets with the same cardinality, page 452
- Finite set, page 455
- Infinite set, page 455
- Cardinality of a finite set, page 455
- Cardinality of \(\mathbb{N}\), page 466
- \(\aleph_0\), page 466
- Countably infinite set, page 466
- Denumerable set, page 466
- Uncountable set, page 466
Important Theorems and Results about Finite and Infinite Sets
- Theorem 9.3. Any set equivalent to a finite nonempty set \(A\) is a finite set and has the same cardinality as \(A\).
- Theorem 9.6. If \(S\) is a finite set and \(A\) is a subset of \(S\), then \(A\) is finite and \(\text{card}(A) \le \text{card}(S)\).
- Corollary 9.8. A finite set is not equivalent to any of its proper subsets.
- Theorem 9.9 [The Pigeonhole Principle]. Let \(A\) and \(B\) be finite sets. If \(\text{card}(A) > \text{card}(B)\), then any function \(f: A \to B\) is not an injection.
- Theorem 9.10. Let \(A\) and \(B\) be sets.
1. If \(A\) is infinite and \(A \thickapprox B\), then \(B\) is infinite.
2. If \(A\) is infinite and \(A \subseteq B\),then \(B\) is infinite. - Theorem 9.13. The set \(\mathbb{Z}\) of integers is countably infinite, and so card\((\mathbb{Z}) = \aleph_0\).
- Theorem 9.14. The set of positive rational numbers is countably infinite.
- Theorem 9.16. If \(A\) is a countably infinite set and \(B\) is a finite set, then \(A \cup B\) is a countably infinite set.
- Theorem 9.17. If \(A\) and \(B\) are disjoint countably infinite sets, then \(A \cup B\) is a countably infinite set.
- Theorem 9.18. The set \(\mathbb{Q}\) of all rational numbers is countably infinite.
- Theorem 9.19. Every subset of the natural numbers is countable.
- Corollary 9.20. Every subset of a countable set is countable.
- Theorem 9.22. The open interval (0, 1) is an uncountable set.
- Theorem 9.24. Let \(a\) and \(b\) be real numbers with \(a < b\). The open interval \((a, b)\) is uncountable and has cardinality \(c\).
- Theorem 9.26. The set of real numbers \(\mathbb{R}\) is uncountable and has cardinality \(c\).
- Theorem 9.27 [Cantor’s Theorem]. For every set \(A\), \(A\) and \(\mathcal{P}(A)\) do not have the same cardinality.
- Corollary 9.28. \(\mathcal{P}(\mathbb{N})\) is an infinite set that is not countably infinite.
- Theorem 9.29 [Cantor-Schr\(\ddot{0}\)der-Bernstein]. Let \(A\) and \(B\) be sets. If there exist injections \(f_1: A \to B\) and \(f_2: B \to A\), then \(A \thickapprox B\).