Prove that the set of real numbers is uncountable. Use a proof similar to the proof in Section 17.3.1 that the set of integer functions is uncountable.

Transcribed Image Text:

17.3.1 Uncountability Before proving that the Halting Problem is unsolvable, we first prove that not all functions can be implemented as a computer program. This is so because the num- ber of programs is much smaller than the number of possible functions. A set is said to be countable (or countably infinite if it is a set with infinite members) if every member of the set can be uniquely assigned to a positive integer. A set is said to be uncountable (or uncountably infinite) if it is not possible to assign every member of the set to a positive integer. To understand what is meant when we say "assigned to a positive integer," imagine that there is an infinite row of bins, labeled 1, 2, 3, and so on. Take a set and start placing members of the set into bins, with at most one member per bin. If we can find a way to assign all of the members to bins, then the set is countable. For example, consider the set of positive even integers 2, 4, and so on. We can