Page 196 - Discrete Mathematics and Its Applications

2.5 Cardinality of Sets 175

Because Theorem 2 seems to be quite straightforward, we might expect that it has an easy
proof. However, even though it can be proved without using advanced mathematics, no known
proof is easy to explain. Consequently, we omit a proof here. We refer the interested reader to
[AiZiHo09] and [Ve06] for a proof. This result is called the Schröder-Bernstein theorem after
Ernst Schröder who published a flawed proof of it in 1898 and Felix Bernstein, a student of
Georg Cantor, who presented a proof in 1897. However, a proof of this theorem was found
in notes of Richard Dedekind dated 1887. Dedekind was a German mathematician who made
important contributions to the foundations of mathematics, abstract algebra, and number theory.
We illustrate the use of Theorem 2 with an example.

EXAMPLE 6 Show that the |(0, 1)|=|(0, 1]|.

Solution: It is not at all obvious how to find a one-to-one correspondence between (0, 1) and
(0, 1] to show that |(0, 1)|=|(0, 1]|. Fortunately, we can use the Schröder-Bernstein theorem
instead. Finding a one-to-one function from (0, 1) to (0, 1] is simple. Because (0, 1) ⊂ (0, 1],
f(x) = x is a one-to-one function from (0, 1) to (0, 1]. Finding a one-to-one function from
(0, 1] to (0, 1) is also not difficult. The function g(x) = x/2 is clearly one-to-one and maps
(0, 1] to (0, 1/2]⊂ (0, 1). As we have found one-to-one functions from (0, 1) to (0, 1] and
from (0, 1] to (0, 1), the Schröder-Bernstein theorem tells us that |(0, 1)|=|(0, 1]|. ▲

UNCOMPUTABLE FUNCTIONS We will now describe an important application of the
concepts of this section to computer science. In particular, we will show that there are functions
whose values cannot be computed by any computer program.

DEFINITION 4 We say that a function is computable if there is a computer program in some programming
language that finds the values of this function. If a function is not computable we say it is
uncomputable.

To show that there are uncomputable functions, we need to establish two results. First, we
need to show that the set of all computer programs in any particular programming language is
countable. This can be proved by noting that a computer programs in a particular language can
be thought of as a string of characters from a finite alphabet (see Exercise 37). Next, we show
that there are uncountably many different functions from a particular countably infinite set to
itself. In particular, Exercise 38 shows that the set of functions from the set of positive integers
to itself is uncountable. This is a consequence of the uncountability of the real numbers between
0 and 1 (see Example 5). Putting these two results together (Exercise 39) shows that there are
uncomputable functions.

THE CONTINUUM HYPOTHESIS We conclude this section with a brief discussion of a
+
famous open question about cardinality. It can be shown that the power set of Z and the set
of real numbers R have the same cardinality (see Exercise 38). In other words, we know that
+
|P(Z )|=|R|= c, where c denotes the cardinality of the set of real numbers.
An important theorem of Cantor (Exercise 40) states that the cardinality of a set is always less
+
+
than the cardinality of its power set. Hence, |Z | < |P(Z )|. We can rewrite this as ℵ 0 < 2 ,
ℵ 0
using the notation 2 |S| to denote the cardinality of the power set of the set S. Also, note that the
+
relationship |P(Z )|=|R| can be expressed as 2 ℵ 0 = c.
This leads us to the famous continuum hypothesis, which asserts that there is no cardinal
number X between ℵ 0 and c. In other words, the continuum hypothesis states that there is no set
c is the lowercase
A such that ℵ 0 , the cardinality of the set of positive integers, is less than |A| and |A| is less than
Fraktur c.
c, the cardinality of the set of real numbers. It can be shown that the smallest infinite cardinal
numbers form an infinite sequence ℵ 0 < ℵ 1 < ℵ 2 < ··· . If we assume that the continuum
hypothesis is true, it would follow that c =ℵ 1 , so that 2 ℵ 0 =ℵ 1 .