# Set of functions that are eventually zero

1. Oct 14, 2012

### jmjlt88

The problem asks whether the set F of all functions from Z+ into {0,1} that are "eventually zero" is countable or uncountable.

In my proof, I claimed countable. By definition, associated with each function f in F, there is a positive integer N such that f(n)=0 for n≥N. I took N' to be the largest of these N's. Hence, for each f in F, f(n)=0 for all n≥N'. Then, I defined a function g: F -> {0,1}N'-1 by

g({(1,x1),....,(N'-1,xN'-1), (N',0),(N'+1,0)....}) = (x1,......,xN'-1)​

[Note: I know there is a simplier way to denote elements in F]

I then proved that this is a bijection. Since the range is a finite product of countable sets, it is countable. It follows that F is indeed countable.

Looking back at my proof, I feel that I may have made an error in picking N'. Cannot I not just construct a function that sends 1 through, say, N'+1 to 1 and the rest to zero? In other words, what (if anything) allows me to pick such an N'?

My proof may be correct. That is, I may be second guessing myself.

Last edited: Oct 14, 2012
2. Oct 14, 2012

### Staff: Mentor

What about f(n)=1 for all n in Z+?
Or g(n)=1 for odd n, g(n)=0 for even n?

If that N(f) would exist for all f in F, F would be countable. However, you would need a different proof:
"The largest N" does not have to exist in infinite subsets of the natural numbers.

If that N' would exist, F would be finite.

3. Oct 14, 2012

### jmjlt88

Sorry. I posted the question wrong. The problem asks whether the set F of all functions from Z+ into {0,1} that are eventually zero is countable or uncountable.

4. Oct 14, 2012

### Dick

You can't choose a largest N' at all. Each function has a different N, no reason they should be bounded. Take the set of all functions such that f(n)=0 for n≥N. That's countable (in fact, it's finite). Now think about forming a union of sets.

5. Oct 14, 2012