Prove or disprove that the set S is countable 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.
 A: 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.

A: This $\mid$ symbol you talk about translates to English as "such that", i.e. you want all boolean functions defined on the set $\mathbb{N}$ such that for all $x$ there exists $y$ greater than $x$ with $f(x) = f(y)$. This "such that" part and subsequent condition shrinks the initial set of all boolean functions defined on $\mathbb{N}$, potentially making it countable.
Namely, this condition says that your functions attain every value either zero or infinitely many times, meaning that some functions are excluded from the set, with one possible example being $$f(x) = \begin{cases} 1, & x = 1, \\ 0, & x > 1, \end{cases}$$ or the one suggested by @atticus-stonestrom
This is a partial answer not answering the title question, but I think that you'll be able to complete from here on. Hint: present all excluded functions as a countable union of countable sets, depending on how many times they attain the "wrong" value.
A: I think that a way to see this problem is that, with your condition, a sequence isn't in S if 0 or 1 appear a finite amount if time.
So I think you can caracterize $\{0,1\}^{\mathbb{N}}/S=\left(\{0,1\}^*\cup \{0\}^{\mathbb{N}} \right) \cup \left(\{0,1\}^*\cup\{1\}^{\mathbb{N}} \right)$
Where $ \{0,1\}^*$ reprsents all finite sequence of $\{0,1\}$ (which is countable), and $\{0\}^{\mathbb{N}} $ and $\{1\}^{\mathbb{N}} $ are countable (carinal $\aleph_0 $), So you get that $\{0,1\}^{\mathbb{N}}/S$ is countable.
However, $\{0,1\}^{\mathbb{N}}$ isn't countable, so you must have $S$ uncountable
A: $$S = \left\{ f \in \{0,1\}^{\mathbb{N}} \middle| (\forall x \in \mathbb{N})( \ \exists y \in \mathbb{N}): y > x \land f(y) = f(x) \right\}$$
The function gives as result any sequence of $0,1$ these are the binary representation of the real numbers, for instance in the interval $[0,1]$ therefore the set $S$ is more than countable.
