(a) So, is the set of all functions from into the integers ; I'm going to write .

These things can be pictured in different ways; sometimes looking at the same thing from different points of view can be helpful.

For instance, my first instinct would be to consider functions as collections of ordered pairs (basically their definition); so the example you gave would be .

But I think another way may be more enlightening: a function can be viewed as a sequence of two integers. For the example, we write . Using this way of thinking, we see that the number of such functions is exactly equal to the number of such two-term integer sequences.

Notice, however, that a "two-term sequence" is pretty much exactly the same as an ordered pair. Thus we see that . Have you discussed any results in your class about the countability of a finite Cartesian product of countable sets?

(b) So . First, let me visualize as being written (standard way to show the countability of ). I think of a function as a countable sequence

, where . Then is equal to the cardinality of the set of all such countable sequences of 0's and 1's (usually written ). We show is uncountable.

Suppose, for sake of contradiction, that is countable. Then we may list its elements as . Consider now the sequence , where

(k-th entry of ) . In words, the k-th entry of is the opposite of the k-th entry of .

Certainly, then, . But notice that, for any , because they differ (at least) in position k.

But the are supposed to make up all of ; this is clearly a contradiction. We conclude that must be uncountable.