Set of functions that are eventually zero

[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,x₁),...,(N'-1,x_N'-1), (N',0),(N'+1,0)...}) = (x₁,...,x_N'-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.

 

[mfb]

The problem asks whether the set F of all functions from Z₊ into {0,1} 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.

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:

I took N' to be the largest of these N's.

"The largest N" does not have to exist in infinite subsets of the natural numbers.

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

 

[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.

 

[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.

 

[jmjlt88]

I knew that picking N' was wrong! It didn't sit right with me. What about this.

Let A_N be the set of all functions such that f(n)=0 for n≥N. For THIS set, I can construct a bijective correspondence between A_N and {0,1}^N-1 by defining g: A_N->{0,1}^N-1 by
g({(1,x₁),...,(N-1,x_N-1), (N,0),(N+1,0)...}) = (x₁,...,x_N-1).
Hence A_N is countable for each N.
Taking Z₊ as our index set. The union of all A_N for each NεZ₊ is the countable union of countable sets ...

 

[Dick]

I knew that picking N' was wrong! It didn't sit right with me. What about this.

Let A_N be the set of all functions such that f(n)=0 for n≥N. For THIS set, I can construct a bijective correspondence between A_N and {0,1}^N-1 by defining g: A_N->{0,1}^N-1 by
g({(1,x₁),...,(N-1,x_N-1), (N,0),(N+1,0)...}) = (x₁,...,x_N-1).
Hence A_N is countable for each N.
Taking Z₊ as our index set. The union of all A_N for each NεZ₊ is the countable union of countable sets ...

Yes, that would do it.