Section 7.1 Infinite Cardinality
Guiding Questions.
Today, we’ll seek to answer the questions:
In
Section 4.1, we briefly introduced the idea of cardinality. Recall
the definition: a (nonempty) finite set
\(S\) has cardinality
\(k\in \N\) if there is a one-to-one correspondence (i.e., a bijection) between
\(S\) and
\(\set{1,2,\ldots,k}\text{.}\) Nonempty sets which are not finite are infinite. But do all infinite sets have the same cardinality? Or are there different “sizes” of “infinity”? These were the questions that Georg Cantor explored, and to which we now turn.
We begin with a definition.
Definition 7.1.1.
Let
\(S\) be a set. We say
\(S\) is
countably infinite, or sometimes
countable , if there is a bijection
\(f : S\to\N\text{.}\)
Problem 7.1.2.
Prove that the following sets are countably infinite by exhibiting bijections between each of them and \(\N\text{.}\) You should be ready to give an informal proof that your function is, in fact, a bijection.
\(\displaystyle \N_0\)
\(\displaystyle 2\N = \set{2, 4, 6, 8, \ldots}\)
\(\displaystyle S = \set{1, 4, 9, 16, 25, 36, \ldots}\)
\(\displaystyle \N\times\N\)
Theorem 7.1.3.
The set of integers \(\Z\) is countable.
Activity 7.1.4.
Assume we can write an infinite set \(X\) as \(X = \set{x_1, x_2, x_3, \ldots}\text{;}\) that is, we can write the elements of \(X\) in some order, with a first element, and a second, and a third, and so on. Explain why such an \(X\) must be countable.
Theorem 7.1.5.
Let \(X\) be an infinite set. Then \(X\) contains a countably infinite subset.
Subsection 7.1.1 The Cantor-Schroeder-Bernstein Theorem
Definition 7.1.6.
Let \(A\) and \(B\) be sets. We say \(A\) and \(B\) have the same cardinality if there is a bijection \(f: A\to B\text{.}\) In this case, we write \(|A| = |B|\text{.}\)
If there is an injection \(A \hookrightarrow B\) we write \(|A| \le |B|\text{.}\)
The reason for the second part of
Definition 7.1.6 is hopefully clear: if such an injection exists, there is a set
\(A'\subseteq B\) for which
\(|A| = |A'|\text{,}\) and it is reasonable to take
\(|A'| \le |B|\text{.}\)
The following theorem (which you do not need to prove) answers the natural question: if \(|A| \le |B|\) and \(|B| \le |A|\text{,}\) must we have \(|A| = |B|\text{?}\) That is, if there are injections \(A\hookrightarrow B\) and \(B\hookrightarrow A\text{,}\) must there be a bijection \(A\to B\text{.}\)
Cantor-Schroeder-Bernstein.
Let \(A,B\) be sets. If there is a one-to-one function \(f: A\to B\) and a one-to-one function \(g : B\to A\text{,}\) then \(A\) and \(B\) have the same cardinality.
Theorem 7.1.7.
Let \(X_1, X_2\) be countable sets. Then \(X_1\times X_2\) is countable.
Corollary 7.1.8.
Let \(X_1, X_2, \ldots, X_k\) be countable sets, where \(k\ge 1\text{.}\) Then \(X_1\times X_2\times \cdots \times X_k\) is countable.
Theorem 7.1.9.
Let \(S_1, S_2\) be countable sets. Then \(S_1\cup S_2\) is countable.
Hint.
First assume \(S_1\cap S_2 = \emptyset\text{.}\) Then consider: what if \(S_1\cap S_2 \ne \emptyset\text{?}\)
Corollary 7.1.10.
Let \(S_1, S_2, S_3, \ldots\) be a countable collection of countable sets. Then \(\bigcup\limits_{k=1}^\infty S_k\) is countable.
We have seen thus far that many familiar sets are countable. One may rightly wonder: are all infinite sets countable? The answer turns out to be “no” —we explore this further in
Section 7.2.
