Countable and Uncountable Sets
Solved Problems
Example 1.
Is the set \(\left\{ {\mathbb{N},\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}} \right\}\) countable or uncountable?
Solution.
Here we have a finite set consisting of \(5\) elements. Therefore, it is countable despite the fact that some of its elements are uncountable sets.
Example 2.
Prove that the set \({\mathbb{N}^3}\) is countably infinite.
Solution.
We know that the Cartesian product \(\mathbb{N}^2 = \mathbb{N} \times \mathbb{N}\) is countably infinite. The Cartesian product of three sets \(\mathbb{N}^3 = \mathbb{N} \times \mathbb{N} \times \mathbb{N}\) can be represented as
We obtain the product of two countably infinite sets, which is also countably infinite.
In list form, the set \({\mathbb{N}^3}\) is given by
Example 3.
Prove or disprove: If \(A\) is an uncountable set and \(B \subset A\) is a countably infinite set, then the set difference \(A \backslash B\) is uncountable.
Solution.
This is a true statement. It can be proved by contradiction. Suppose that \(A \backslash B\) is countably infinite. Then the union of two countably infinite sets must also be countable:
This contradicts the fact that the set \(A\) is uncountable.
Example 4.
Show that the set \(\mathbb{Q}^n\) is countable for any \(n \in \mathbb{N}.\)
Solution.
When \(n = 1,\) we have the set of rational numbers \(\mathbb{Q}\) which is countable. Suppose, by induction, that \(\mathbb{Q}^n\) is countable for \(n \in \mathbb{N}.\) Note that
It is known that the Cartesian product of two countable sets is countable. Therefore \({\mathbb{Q}^{n + 1}}\) is a countable set.
It follows that the set \({\mathbb{Q}^{n}}\) is countable for any \(n \in \mathbb{N}.\)
Example 5.
Prove that the set \(\left\{ {0,1} \right\} \times \mathbb{N}\) is countably infinite.
Solution.
The set \(\left\{ {0,1} \right\}\) is finite and hence countable. The set of natural numbers \(\mathbb{N}\) is also countable. As it is known, the Cartesian product of two countable sets is countable. Therefore, the set \(\left\{ {0,1} \right\} \times \mathbb{N}\) is countable.
We can arrange the elements of the set in list form as follows:
This shows that the set \(\left\{ {0,1} \right\} \times \mathbb{N}\) is countably infinite.)
Example 6.
Determine whether the set of all finite strings over Latin alphabet is countable or uncountable?
Solution.
We assume that the Latin alphabet includes \(52\) letters (both upper and lower case). Then there are \(52\) one letter strings, \(52^2\) two letter strings, etc. Let \(M\) be the maximum string size. Then the total number of possible strings is \(52^M.\) We can arrange all these strings as follows:
- We sort the strings by size starting from \(1\) to \(M.\)
- To arrange the elements within each size, we use the lexicographic order.
The resulting list can be numbered with natural numbers, so this set is countable.