Section 7.2 Uncountable Sets
Guiding Questions.
Today, we’ll seek to answer the questions:
What does it mean for a set to be uncountable?
What are some examples of uncountable sets?
What does Cantor’s Theorem say, and what does it imply about infinite cardinalities?
We begin with a definition.
Definition 7.2.1.
A set which is neither finite nor countably infinite is said to be uncountable.
Before proving any theorems about uncountable sets, we should exhibit an example of the phenomenon.
Problem 7.2.2.
Consider the set \(\mathcal{S}\) of all infinite sequences of 0’s and 1’s. We will prove that this set is uncountable by showing that no bijection can exist between \(\mathcal{S}\) and \(\N\).
List three examples of elements of \(\mathcal{S}\text{.}\)
Reasoning toward a contradiction, assume that
\(\mathcal{S}\) is countable. Use
Activity 7.1.4 to write the elements of
\(\mathcal{S}\) in order.
Construct a sequence \(b\in \mathcal{S}\) which nonetheless differs from every sequence you listed in the previous part.
Describe the contradiction you’ve reached.
One can use the ideas of
Problem 7.2.2 to prove that
\(\R\) is uncountable (in fact, the closed interval
\([0,1]\) is uncountable!).
Let us explore some consequences of this definition.
Theorem 7.2.3.
Let \(X\) be an infinite set. Then \(X\) has a countably infinite subset.
Theorem 7.2.4.
Suppose \(X\) is uncountable and \(Y\subseteq X\) is countable. Then \(X\setminus Y\) is uncountable.
Corollary 7.2.5.
There are more irrational numbers than rational numbers.
We conclude this section by exploring one of the milestones in early set theory.
Problem 7.2.6.
Let
\(S\) be any set, and recall that
\(\mathcal{P}(S)\) is the
power set of
\(S\text{.}\)
Exhibit an injection \(S\hookrightarrow \mathcal{P}(S)\) to conclude that \(|S| \le |\mathcal{P}(S)|\text{.}\)
Now, let \(f : S \to \mathcal{P}(S)\) be any function. Define \(T = \setof{s\in S}{s\notin f(s)}\text{.}\) Suppose there is some \(x\in S\) for which \(f(x) = T\text{,}\) and reach a contradiction.
Conclude that \(|S| \lt |\mathcal{P}(S)|\text{.}\)
Briefly describe the cardinalities of \(\mathcal{P}(\N), \mathcal{P}(\mathcal{P}(\N)), \mathcal{P}(\mathcal{P}(\mathcal{P}(\N))),\ldots,\) etc.
