Prove or disprove the set $F$ of all functions $f:\Bbb{N}\to \{0,1\}$ that are ''eventually zero'' is countable.
For each $n\in \Bbb{N}$, let $F_n = \{f: \Bbb{N}\to\{0, 1\}:f(i) = 0 \forall i > n\}$. Then it is easy to see that $F_n$ is finite.
How to prove rigorously?
function $f$ is eventually zero means $f(n)=0$ $\forall$ $n\geq N$, $N\in \Bbb{N}$.
Define a map $\psi: \Bbb{N} \to \{0,1\}^\Bbb{N}$ such that
$\psi(i)=\{f(i):i\in\{0,2,…,n-1\}$
$\psi(i)=\{0:i\notin\{0,2,…,n-1\}$.
Does this map work?
Any help will be appreciated.
Best Answer
Just writing numbers from $\mathbb{N}$ in binary effectively identifies every number in $\mathbb{N}$ with a function of the form you describe. Conversely every such function is basically telling you how to write down a binary number, from right to left.
For example, suppose $$\begin{align}f:{}&1\to0\\&2\to1\\&3\to0\\&4\to0\\&5\to1\end{align}$$ and all else to $0$. This identifies with the binary integer $$\stackrel{5}{1}\stackrel{4}{0}\stackrel{3}{0}\stackrel{2}{1}\stackrel{1}{0}$$ which is $18$ in binary. So this $f\leftrightarrow 18$.
And for example, start with the number $23$, which is $10111$. This defines $$\begin{align}g:{}&1\to1\\&2\to1\\&3\to1\\&4\to0\\&5\to1\end{align}$$ So $g\leftrightarrow23$.
More formally, there is a map $\varphi:\mathbb{N}\to F$, such that if $n$ is $b_kb_{k-1}\cdots b_1$ in binary, then $\left(\varphi(n)\right)(m)=b_m$, where $b_m=0$ for $m>k$.
And there is $\varphi^{-1}:F\to \mathbb{N}$ where $\varphi^{-1}(f)=f(k)\cdots f(2)f(1)$ (read as a binary concatenation) where $k$ is the largest number for which $f$ returns $1$.
So there is a very direct enumeration of these functions, which makes them countable.