Define set $S$ as follows $$S = \left\{ f \in \{0,1\}^{\mathbb{N}} \middle| \forall x \in \mathbb{N} \ \exists y \in \mathbb{N}: x < y \land f(x) = f(y) \right\},$$ where $\{0,1\}^\mathbb{N}$ denotes the set of boolean functions defined on $\mathbb{N}$.
Prove or disprove that the set $S$ is countable.
I know that the first part before the |-symbol itself is uncountable, but I don't understand the whole $x$, $y$, $f(x)$, and $f(y)$ part, and how it would change the fact that it's already not countable. Could it not just be ignored? I'd be happy about any help.
Best Answer
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!)