9.S: Finite and Infinite Sets (Summary)

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$.