Cardinality
Definition 1. Sets \(A\) and \(B\) have the same cardinality, denoted \(|A|=|B|\), if there exists a bijective function \(f:A\to B\). If \(A\) and \(B\) do not have the same cardinality, we write \(|A|\neq|B|\).
Theorem 1. If there exist injective functions \(f:A\to B\) and \(g:B\to A\), then \(|A|=|B|\).
Theorem 2. For any sets \(A\) and \(B\), there is an injection from \(A\) into \(B\) or there is an injection from \(B\) into \(A\).
Proof. Uses axiom of choice. ◻
Example 1. \(|\mathbb{Q}|=|\mathbb{Z}|=|\mathbb{N}|\)
Definition 2. A set \(A\) is infinite if there exists an injective function \(f:\mathbb{N}\to A\). A set is finite if it is not infinite.
Theorem 3. A set \(A\) is finite if and only if there exists \(n\in\mathbb{N}\) such that \(|A|=|\{k\in\mathbb{N}: 1\leq k\leq n\}|\). This value of \(n\) is unique.
Definition 3. If \(A\) is a finite set, we say that the cardinality of \(A\) is the value \(n\in\mathbb{N}\) from the previous theorem and write \(|A|=n\).
Example 2. \(|\emptyset|=0\), \(|\{1\}|=1\), \(|\{1,2\}|=2\), etc.
Theorem 4. If \(A\) is a finite set and \(B\subset A\) is a proper subset, then \(|B|<|A|\).
Definition 4. A set \(A\) is countable if there exists an injective function \(f:A\to\mathbb{N}\). A set is uncountable if it is not countable. If \(A\) is countable, it may be enumerated by denoting each \(a\in A\) by \(a_{f(a)}\) \[A = \{a_1, a_2, \dots \}\]
Theorem 5. A finite product of countable sets is countable.
Theorem 6. A countable union of countable sets is countable.
Example 3. The countable product \(\prod_{n\in\mathbb{N}} \{0,1\}\) is uncountable.
Lemma 7. If \(A\) is an infinite set and \(B\) is a finite set, then \[|A\cup B| = |A\setminus B| = |A|\]
Proof. Let \(A\) be infinite and \(B\) be finite. Let \(n=|B|\) and suppose \(B=\{b_1,\dots,b_n\}\). Let \(\{a_k\}_{k=1}^\infty \subseteq A\). Define \(f:A\to A\cup B\) by \[f(a) = \begin{cases} b_k & a = a_k, 1\leq k\leq n \\ a_{k-n} & a = a_k, k > n \\ a & \text{otherwise}. \end{cases}\] ◻
Lemma 8. If \(A\) is an uncountable set and \(E\) is a countable set, then \[|A\cup E| = |A\setminus E| = |A|\]
Proof. Let \(A\) be uncountable and \(E\) be countable. Let \(G = E\setminus A\). Then \(G\) is countable. Assume \(G\) is infinite with \(G=\{g_n\}_{n=1}^\infty\). Let \(\{a_n\}_{n=1}^\infty \subseteq A\). Define \(f: A\to A\cup G\) by \[f(a) = \begin{cases} g_n & a = a_{2k} \\ a_n & a = a_{2n-1} \\ a & \text{otherwise}. \end{cases}\] Then \(f\) is bijective and \(A\cup G = A\cup E\setminus A = A\cup E\), hence \[|A| = |A\cup E|.\] ◻
Example 4. As subsets of \(\mathbb{R}\) \[|[0,1]| = |[0,1)| = |(0,1]| = |(0,1)|\]
Theorem 9. If a set \(S\) is nonempty, then \(|S|\neq |\mathcal{P}(S)|\).
Proof. Let \(f: S\to\mathcal{P}(S)\) be a function. Let \[B = \{s\in S : s\notin f(s)\}.\] Suppose towards a contradiction that there is \(x\in S\) with \(f(x)=B\).
Case 1: Suppose \(x\in B\). Then \(x\notin f(x)\) and \(f(x)=B\) so that \(x\notin B\), contradiction.
Case 2: Suppose \(x\notin B\). Then \(x\in f(x)\) and \(f(x)=B\) so that \(x\in B\), contradiction.
Then \(B\) is not in the range of \(f\), and \(f\) is not surjective. ◻
Example 5. The set of real numbers \(\mathbb{R}\) is uncountable. \[|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\{0,1\}^\mathbb{N}| = |[0,1)| = |(0,1)| = |\mathbb{R}|\]
Source File: jakemath.com/latex/sets/cardinality.tex