Chapter 7 Infinite sets
7.1 Countability
Definition 7.1 (Countable sets) A set \(X\) is said to be countably infinite (or just countable) iff it has equal cardinality with the natural numbers \(\mathbb{N}\). A set \(X\) is said to be at most countable iff it is either countable or finite. We say that a set is uncountable if it is infinite but not countable.
Proposition 7.1 (Well ordering principle) Let \(X\) be a non-empty subset of the natural numbers \(\mathbb{N}\). Then there exists exactly one element \(n\in X\) such that \(n\leq m\) for all \(m\in X\). In other words, every non-empty set of natural numbers has a minimum element.
Here is the proof.
Proof. Given any non-empty subset \(E\) of \(\mathbb{N}\), then there exists \(\inf(E)\). Then we just need to illustrate that \(\inf(E)\in E\).
Proposition 7.2 Let \(X\) be an infinite subset of the natural numbers \(\mathbb{N}\). Then there exists a unique bijection \(f:\mathbb{N} \to X\) which is increasing, in the sense that \(f(n+1)>f(n)\) for all \(n\in\mathbb{N}\).
Here is the proof.
Proof. \(f(n):=\min\{x\in X:x\ne a_m\text{ for all }m<n \}\)
Corollary 7.1 All subsets if the natural numbers are at most countable.
Corollary 7.2 If \(X\) is an at most countable set, and \(Y\) is a subset of \(X\), then \(Y\) is at most countable.
Proposition 7.3 Let \(Y\) be a set, and let \(f:\mathbb{N} \to Y\) be a function. Then \(f(\mathbb{N})\) is t most countable.