158 Computability Theory because either 17 S 17 and 17 A / or 17 S 17 and 17 A. / The set in part (c) has the same size as the set in part (b); simply pair up each subset of N with its characteristic function. Or to prove part (c) directly, consider any countable set {s 0 , s 1 , . . .} of infinite binary sequences. Then, we can make a new · binary sequence f by defining f (n) = 1 - s n (n) for each n. The set in part (d) is at least as big as the set in part (c). That is, the set in part (c) is a subset of the set in part (d). A particularly relevant example for our purposes is the set S of all register-machine programs. This set is countable. One way to see this fact is to represent S as a set of finite sequences over a certain finite alphabet. But a more direct proof uses the function P # P assigning to each program its G odel number. This function maps S one-to- ¨ one into N . Consequently, the set of all computable partial functions is countable. We can map each such function to the least G odel number of a program that computes it. ¨ The set of all partial functions (computable or not) is uncountable. By part (d) of the preceding theorem, even the set of total functions is uncountable. So the set of noncomputable total functions is uncountable. That is, there are uncountably many