Prove or disprove that the set S is countable

We will define an injection $\varphi:\{0, 1\}^\mathbb{N}\rightarrow S$. Because $\{0, 1\}^\mathbb{N}$ is uncountable, as you have noted, this will be enough to show that $S$ is uncountable. So, define $\varphi(f)$ by $\varphi(f)(n)=f(n/3)$ if $n\equiv 0\text{ (mod 3)}$, $\varphi(f)(n)=0$ if $n\equiv 1\text{ (mod 3)}$, and $\varphi(f)(n)=1$ if $n\equiv 2\text{ (mod 3)}$. Can you show that $\varphi(f)\in S$ and that $\varphi$ is injective? (Answer given below, but try to do it yourself first!)

---

To show $\varphi(f)\in S$, let $x\in \mathbb{N}$. We wish to show there is $y>x$ such that $\varphi(f)(x)=\varphi(f)(y)$. If $\varphi(f)(x)=0$, let $y=3x+1$, and if $\varphi(f)(x)=1$, let $y=3x+2$.

To show injectivity, suppose that $f\neq g\in\{0, 1\}^\mathbb{N}$. Then there is some $n\in\mathbb{N}$ such that $f(n)\neq g(n)$, we have $\varphi(f)(3n)=f(n)\neq g(n)=\varphi(g)(3n)$, so $\varphi(f)\neq\varphi(g)$ as desired.