Directly proof $S$ is countable, where $S$ is set of function from $\{0, 1\}$ to $\mathbb{N}$

Question

Suppose $S=\{f_1,f_2,f_3,f_4,f_5,........\}$ where $f_i$ is a function $f:\{0, 1\}\to\mathbb{N}.$ I have to prove $S$ is countable.Then need to prove direct one-to-one correspondence between $S$ and $\mathbb{N}.$ If I put $(\{0,f(0)\},\{1,f(1)\})=(\{0,1\},\{1,1\})$ for $f_1$ map to $1,$ Similarly,$(\{0,2\},\{1,2\})$ for $f_2$ map to $2..................$$(\{0,i\},\{1,i\})$ for $f_i$ map to $i...............$

Is it showing direct bijection between $S$ and $\mathbb{N}.$ But I already proven $S$ is countable by Countability Lemma. I need to understand why my direct proof concept is wrong.

Answer 1

Your list of functions is incomplete: $\{(0,i), (1,i)\}$ is a constant function, but there are also functions like $\{(0,564), (1, 876)\}$; where do you map those, i.e. what number do they get?

If you want to use the countability lemma you state in the comments, you can: just assign $\max(f(0), f(1))$ to $\{(0,f(0)), (1,f(1)\} \in S$ then there are at most finitely many functions with assigned value $n$ for each $n$ (why?)..

Answer 2

After understanding of @Henno Brandsma's answer I have created one Example for better understanding.

More precisely $2(n+1)−1=2n+1$ elements in $S$ for each $n.$ The max could be $f(0)$ in $n+1$ ways$, n+1$ ways for it to be $f(1)$ and $−1$ for the constant map that's counted doubly.

For example to get maximum value $n=3.$

Case:1 If max is $f(0)$, we know that $(0,3)$ is in the map and $f(1)$ can be $0,1,2,3.$Then the elements of $S$ are $\{(0,3),(1,0)\},$$\{(0,3),(1,1)\},$$\{(0,3),(1,2)\},$$\{(0,3),(1,3)\}.$ are map to same image $3$ in $\mathbb{N}$ because every element $max(f(0),f(1))$ is $3.$ Here number of elements $=4.$

Case:2 If max is $f(1)$, we know that $(1,3)$ is in the map and $f(0)$ can be $0,1,2,3.$Then the elements of $S$ are $\{(0,0),(1,3)\},$$\{(0,1),(1,3)\},$$\{(0,2),(1,3)\},$$\{(0,3),(1,3)\}.$ are map to same image $3$ in $\mathbb{N}$ because every element $max(f(0),f(1))$ is $3.$Here number of elements $=4.$

But we count $\{(0,3),(1,3)\}$ doubly, we should remove this. So $7 = 2n+1$ elements in $S$ maps to element $3$ in $\mathbb{N}.$