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}}} \)
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 [CantorSchr\(\ddot{0}\)derBernstein]. 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\).