Chapter 10 Countability and infinite sets - non-examinable

10.1 Infinite sets

Let us begin by recalling some stuff from earlier in the course.

We say sets \(A\) and \(B\) have the same cardinality if there exists a bijection \(f: A \rightarrow B\). We write this \(|A|=|B|\).

We say \(A\) has cardinality \(n\) if there is a bijection \(f: A \rightarrow [[n]]\).

We say \(A\) is finite if \(|A|=n\) for some \(n \in \mathbb{N}\).

We think as cardinality as telling us about the size of a set. One of the peculiar properties of infinite sets is that we can have \(B \subset A\) and \(|A| = |B|\).

An example of this is \(S=\{m \in \mathbb{N} \,:\, \exists \, n \in \mathbb{N} \, m=n^2\}\) the square numbers. Then there is a bijection between \(\mathbb{N}\) and \(S\) given by \(f(n) = n^2\). So \(|S| = |\mathbb{N}|\).

This is a big contrast to final sets. If \(A \subset B\) and \(A \neq B\) and they are both finite then this implies that we must have \(|A| < |B|\).

In fact this difference characterises infinite sets

Proposition 10.1 A set \(A\) is infinite if and only if there exists a set \(B \subset A\) such that there is a bijection \(f: B \rightarrow A\).

Proof. We can see the only if part is fairly clear. If \(A\) is finite suppose it has \(n\) elements then \(B\) must have \(n-1\) elements or fewer. So we cannot form a bijection from \(B\) to \(A\).

Now if \(A\) is infinite we first show that there is a subset \(C\) which is in bijection with the natural numbers. So if first since \(A\) is infinite it must contain some element \(a_0\) then \(A \neq \{a_0\}\) as its infinite there must be another element \(a_1\). We continue like this to form the subset \(C = \{a_0, a_1, a_2, \dots \}\). Then set \(\tilde{C} = \{a_i \in C \,:\, \exists \, j \, i=j^2\}\) and set \(B = (A-C)\cup \tilde{C}\). We can then define \(f: B \rightarrow A\) by \(f(a) = a\) if \(a \in A-C\) and \(f(a_i) = a_{\sqrt{i}}\) for \(a_i \in \tilde{C}\).

Furthermore in this proof we can see that \(A-B\) is actually infinite.

10.2 Countability

Definition 10.1 (countability) We say a set \(A\) is countable if \(A\) is finie or has the same cardinality as \(\mathbb{N}\).

We say \(A\) is uncountable if it isn’t countable.

If \(A\) is countable and infinite it says its countably infinite.

Theorem 10.1 The following are equivalent

\(A\) is countable.
There is an injection from \(A\) to \(\mathbb{N}\).
\(A\) is \(\emptyset\) or there is a surjection from \(\mathbb{N}\) to \(A\).

Proof. We can see that \((i) \Rightarrow (iii)\) if \(A\) is finite then there is a bijection \(f: A \rightarrow [[n]]\) for some \(n\) then define \(g: \mathbb{N} \rightarrow A\) by \(g(m) = f^{-1}(m)\) for \(m \in [[n]]\) and \(g(m) = 0\) for \(m \geq n\). This is a surjection.

We can see \((iii) \Rightarrow (ii)\) as if \(g: \mathbb{N} \rightarrow A\) is a surjection then \(g\) has a right inverse \(h\) which must be an injection by previous results.

We can see that \((ii) \Rightarrow (i)\) as if \(h: A \rightarrow \mathbb{N}\) is an injection then we can define \(S\) to be the range of \(S\). Then as \(S\) is a subset of \(\mathbb{N}\) by itteratively using the well ordering principle we can list the elements of \(S\) in size order \(s_0 < s_1 < s_2\) etc. either there are finitely many elements \(n\) in which case \(S = \{s_0 , \dots, s_{n-1}\}\) or there are infinitely many elements in which case \(S = \{s_0, s_1, \dots\}\). In either case we can define a map \(i\) whose domain is \(S\) and codomain is either \([[n]]\) or \(\mathbb{N}\) by \(i(s_k)=k\). Then \(i\) will be a bijection. Then \(f = i \circ h\) is a bijection between \(A\) and \([[n]]\) or between \(A\) and \(\mathbb{N}\).

Example 10.1 \(\mathbb{Z}\) is countable as \(f(n) = 2n\) if \(n \geq 0\) and \(f(n) = 2(-n)-1\) if \(n < 0\) is a bijection from \(\mathbb{Z}\) to \(\mathbb{N}\).

Example 10.2 \(\mathbb{N} \times \mathbb{N}\) is countable since \(f(n.m) = 2^n 3^m\) gives an injection from \(\mathbb{N} \times \mathbb{N}\) to \(\mathbb{N}\). In a similar way \(\mathbb{N}^k\) is countable for any finite \(k\).

Example 10.3 \(\mathbb{Z}^k\) is countable. We can prove this because we know we have an injection \(g: \mathbb{Z} \rightarrow \mathbb{N}\). So given a finite set of distinct primes \(p_1, \dots, p_k\) then \(f(z_1, \dots, z_k) = p_1^{g(z_1)} \dots p_k^{g(z_k)}\) is an injection.

Theorem 10.2 A countable union of countable sets is countable. That is to say suppose \(I\) is a countable set and for each \(i \in I\) we have a countable set \(A_i\) then \(\bigcup_{i \in I} A_i\) is countable.

Proof. without loss of generality \(I\) is countably infinite (otherwise its fairly obvious). There is a bijection between \(I\) and \(\mathbb{N}\) so we can use this to relable. So we might as well be working with \[ \bigcup_n A_n. \] Then let us write \(B_n = A_n - \bigcup_{k=1}^{n-1}A_k\). So the \(B_n\) are all disjoint. Then for each \(A_n\) there is an injection \(f_n\) into \(\mathbb{N}\). Given \(a \in \bigcup_n A_n\) write \(g(a)\) to be the unique \(m \in \mathbb{N}\) such that \(a \in B_m\). Then define \(h(a) = (g(a), f_{g(a)}(a))\). This is an injection from \(\bigcup_n A_n\) to \(\mathbb{N} \times \mathbb{N}\). We can chain this with an injection from \(\mathbb{N} \times \mathbb{N}\) to \(\mathbb{N}\) to create an injection from \(\bigcup_n A_n\) to \(\mathbb{N}\).

We can use this to give a different proof of the fact that \(\mathbb{Q}\) is rational (one was on an exercise sheet). We can write \[ \mathbb{Q} = \bigcup_{n \geq 1} \{ \frac{m}{n} \, :\, m \in \mathbb{Z}\}.\]

Theorem 10.3 \(\mathbb{R}\) is uncountable.

Proof. This is the famous Cantor diagonal argument.

We prove by contradiction that \([0,1)\) is uncountable. Suppose that it is then we can list its elements \[\begin{align*} x_1 &= 0. d_{1,1} d_{1,2} d_{1,2} \dots \\ x_2 &= 0. d_{2,1} d_{2,2} d_{2,3} \dots \\ x_3 &= 0. d_{3,1} d_{3,2} d_{3,3} \dots \\ \end{align*}\] and so on. Now we define \(e_n\) by \(e_n = 0\) if \(d_{n,n} \neq 0\) and \(e_n = 1\) if \(d_{n, n} =0\). Then set \[ y = 0. e_1 e_2 e_3 \dots \] Now \(y \neq x_n\) because \(e_n \neq d_{n,n}\). So \(y\) cannot be in our list. But \(y \in [0,1)\) which is a contradiction.

Remark. If you remember Cantor’s theorem says that there can be no surjection \(f: A \rightarrow \mathcal{P}(A)\). This means that \(A\) and \(\mathcal{P}(A)\) cannot have the same cardinality.

This was obvious for finite sets but it has more interesting consequences for infinite sets. For example it implies that \(\mathbb{N}\) and \(\mathcal{P}(\mathbb{N})\) cannot have the same cardinality. So \(\mathbb{P}(N)\) must be uncountable.

10.3 Algebraic and Trancendental numbers

Definition 10.2 (Algebraic number) We call \(x \in \mathbb{R}\) algebraic if there exists \(n \in \mathbb{N}\) and \(a_0, \dots a_n \in \mathbb{Z}\) such that \[ a_n x^n + \dots + a_1 x + a_0 = 0. \] So that is to say \(x\) is algebraic if it is the root of some polynomial with integer coefficients.

Definition 10.3 (Trancendental number) We say \(x \in \mathbb{R}\) is trancendental if \(x\) is not algebraic.

Lemma 10.1 All rational numbers are algebraic.

Proof. If \(x = m/n\) where \(m \in \mathbb{Z}\) and \(n \in \mathbb{N} - \{0\}\) then \(x\) is a solution to \[nx-m=0.\]

Theorem 10.4 The set of all algebraic numbers \(\mathcal{Alg}\) is countable. (n.b. thtis is not standard notation)

Proof. Let \(\mathcal{P}_k\) be the set of all \(k^{th}\) order polynomials with integer coefficients. There is a bijection between \(\mathbb{Z}^{k+1}\) and \(\mathcal{P}_k\) given by \[ (a_0, \dots, a_k) \mapsto a_0 + a_1 X + \dots + a_k X^k. \]

We have already shown that \(\mathbb{Z}^{k+1}\) is countable so this shows that \(\mathcal{P}_k\) is countable.

Let \(\mathcal{P}\) be the set of all polynomials with integer coefficients then \(\mathcal{P} = \bigcup_k \mathcal{P}_k\) so is the countable union of countable sets so countable.

Then given \(P \in \mathcal{P}\) let \(r(P) = \{ x \in \mathbb{R} \,:\, P(x) =0\}\) i.e. the set of roots of \(P\). Then for each \(P\) we know that \(r(P)\) is a finite set and \[ \mathcal{Alg} = \bigcup_{P\in \mathcal{P}} r(P) \] so is the countable union of countable sets so countable.

Corollary 10.1 The set of all trancendental numbers in uncountable and therefore there exists at least one trancendental number.

Proof. The reals is the disjoint union of the algebraic numbers and the transcendental numbers. If both these sets were countable it would imply that the reals were countable so this shows the set of trancendental numbers must be uncountable. This means it can’t be the empty set.

10.4 Infinite cardinalities

It is very complicated to do a serious set theoretic construction of cardinal numbers but that doesn’t stop us from thinking a bit more about different kinds of infinities.

We can give a kind of order to cardinal numbers (this isn’t exactly an order relation as from before because we don’t know what set we are working in). We do this by saying \(|A| \leq |B|\) if there exists an injection from \(A\) to \(B\). We can also write \(|A| < |B|\) if there exists an injection from \(A\) to \(B\) but no bijection.

Cantor-Schroeder-Bernstein theorem from the first chapter allows us to make more sense of this “order” because it tells us if there is an injection from \(A\) to \(B\) and an injection from \(B\) to \(A\) then there is a bijection between them. So in the language of cardinality this says if \(|A| \leq |B|\) and \(|B| \leq |A|\) then \(|A| = |B|\).

These ideas were the motivation for proving theorems like Cantor’s theorem and Cantor-Schroeder-Bernstein.

We can have some sense of how cardinals can be added and multiplies. If \(A\) and \(B\) are finite disjoint sets then \[ |A| + |B| = |A \cup B| \] and \[|A| |B| = |A \times B|. \] If we extend this logic to cardinals we get some surprising results \[ |\mathbb{N}| + |\mathbb{N}| = |\mathbb{N}| \] and \[ |\mathbb{N}|^2 = |\mathbb{N}|. \] This is peculiar but nevertheless you can do arithmetic with cardinals. You’ll have to take a set theory course to find out more about it though.