9.S: Finite and Infinite Sets (Summary)
( \newcommand{\kernel}{\mathrm{null}\,}\)
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 N, page 466
- ℵ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 card(A)≤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 card(A)>card(B), then any function f:A→B is not an injection.
- Theorem 9.10. Let A and B be sets.
1. If A is infinite and A≈B, then B is infinite.
2. If A is infinite and A⊆B,then B is infinite. - Theorem 9.13. The set Z of integers is countably infinite, and so card(Z)=ℵ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∪B is a countably infinite set.
- Theorem 9.17. If A and B are disjoint countably infinite sets, then A∪B is a countably infinite set.
- Theorem 9.18. The set 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 R is uncountable and has cardinality c.
- Theorem 9.27 [Cantor’s Theorem]. For every set A, A and P(A) do not have the same cardinality.
- Corollary 9.28. P(N) is an infinite set that is not countably infinite.
- Theorem 9.29 [Cantor-Schr¨0der-Bernstein]. Let A and B be sets. If there exist injections f1:A→B and f2:B→A, then A≈B.