Let $f$: $\mathbb{N} \rightarrow \mathbb{Z}$ be a function that is eventually zero. i.e: There exists some $N \in \mathbb{N}$ s.t $f(n)=0$ for all $n \geq \mathbb{N}$. Prove that the set of such functions is countable.


Define $g$: $\mathbb{N} \rightarrow \mathbb{Z}$ s.t $$ g(i) = \left\{ \begin{array}{ll} f(i) & \quad i \in \{0,1…N-1\} \\ 0 & \quad , otherwise \end{array} \right. $$

Let $B_n=\{h|h: \{0,1…N-1\}\rightarrow \mathbb{Z}$}. Clearly, $B_n$ is equal to $N$ copies of $\mathbb{Z}$. Hence, it's countable.

Let $G=\{f|f: \mathbb{N}\rightarrow \mathbb{Z}\}$ is eventually zero}. So, $G = \cup_{N=1}^{\infty} B_n$. Countable union of countable sets is countable. So is $G$.

Is my approach correct?


The basic idea is good, but you rather want to take the union of $G_N$'s where $$G_N:=\{f:\Bbb N\to\Bbb Z:f(n)=0\text{ if } n>N\}$$


Your proof is correct. Here are some points of feedback.

  • Your definition of $g$ depends on a specific $f$ and is actually just the same as that $f$. It does not really do anything in your proof, so just leave it out.
  • It is not quite true that $G = \bigcup_{N=1}^\infty B_n$, because the maps in $B_n$ do not have domain $\mathbb{N}$. They can however easily be made into maps with domain $\mathbb{N}$ (which is clearly what you mean), you should say this (and how).
  • A few small issues with notation, it is a bit sloppy. There is a $\}$ too many in the definition of $G$. The set $B_n$ depends on $n$ not on $N$ in its notation. That kind of thing. Not really a problem here, but in bigger proofs it will get confusing.
  • $\begingroup$ For the first point, Think I should've used some other function, say $f'(i)$ instead of $f(i)$. Second, I think I should've defined a set $T_N$={$g: f' \in B_N$}? Then, take unions of all such $T_N$'s , which is equal to $G$? $\endgroup$ – SL_MathGuy Jan 1 at 14:39
  • 2
    $\begingroup$ @SL_MathGuy That sounds about right. It would be good to make explicit that $g$ depends on $f'$ (e.g. denote $g_{f'}$). Because what you are saying is that $g$ is the extension of $f'$ to $\mathbb{N}$ by setting it to $0$ everywhere $f'$ is not defined. $\endgroup$ – Mark Kamsma Jan 1 at 14:46

I think there is a problem defining the map $g$...What you call $f$ is actually a set of functions....And also you do not use $g$ after you define it...

Some hint, How many maps from $\Bbb{N}$ to $\Bbb{Z}$ can you construct that they are zero after $n=0$ or after $n=1$,.....?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.