Countability Question (Theory)

Question

I'm taking the GRE tomorrow, and had a question. Based on the answer key, this practice test states that the set of all functions from N to {0, 1} is not countable.

Can't you map the natural numbers to these functions, as follows?

 i   1 2 3 4 5 6 7 8 ...
f0 = 0 0 0 0 0 0 0 0 ...
f1 = 1 0 0 0 0 0 0 0 ...
f2 = 0 1 0 0 0 0 0 0 ...
f3 = 1 1 0 0 0 0 0 0 ...
f4 = 0 0 1 0 0 0 0 0 ...

That is, f4(1)=0, f4(2)=0, f4(3)=1, and f4(anything else)=0. Won't this eventually cover all possible kinds of these functions? And we can definitely map the natural numbers to this set.

Answer 1

This is part of Cantor's Theorem. See this paper (near the end.)

Answer 2

If this were countable then irrationals would have to be countable too. Just think of each of those functions you have listed as binary decimals and you can put them 1:1 with reals [0, 1)

Answer 3

All entries in your list will contain a finite number of ones. Where in your list would the function that returns 0 for all evens but 1 for all odds appear or the function which always returns 1? A diagonalization argument can show that no other numbering scheme can work either. To do this, consider a function which returns 1-(fi(i)) at position i. Then this function differs from each entry in the list in at least one place, so it's not in the list.

Answer 4

Any function f_k that is constructed by this algorithm have a finite number of values n such that f_k(n)=1, but you have the function f(odd)=1, f(even)=0, which is a valid function and is not in the list of functions that can be generated by this algorithm.

In general you can apply the Cantor's diagonal argument, as stated by Dan. If such set were numerable then you have a numerable family of functions g_1, g_2, ..., which cover the whole set. But then you can construct a new function h such that h(n) != g_n(n), by construction h can't be equal to any of the g_k, absurd!