# Is the set of all functions $\Bbb N \to \{0,1\}$ (with the following restriction) countable?

There are many solutions to the question without the restriction, so this one is a bit different: $$S = \bigl\{{f \in \{0,1\}^{\Bbb N} \mid \forall x\, \exists y\, (x < y \land f(x) = f(y)}\bigr\}$$

Is $$S$$ countable or not? The restriction is, that for all $$x_1$$ there somewhere must be a $$x_2 > x_1$$ s.t. $$f(x_1) = f(x_2)$$.

• Changing the question after receiving answers is extremely disrespectful of people who have already answered. Don't do it (-1). I rolled back. – Gae. S. Oct 26 at 21:06

In other words, we never run out of $$0$$s or $$1$$s. There are only countably many functions where we do, so there must be uncountably many where we don't. To see the finitely-many-$$1$$s are countable, define$$\Phi(f)=\prod_{f(k)=1}p_k,$$where $$p_k$$ is the $$k$$th prime number. This product is finite since $$f$$ has only finitely many ones. On the other hand, this function is injective since if $$\prod_{f(k)=1}p_k=\Phi(f)=\Phi(g)=\prod_{g(k)=1}p_k,$$ then by the fundamental theorem of arithmetic the products have the same prime decomposition.
• @GyroGearloose instead of looking at $S$, hes looking at $S^c$. Just negating the condition for $S$, we get $\exists x\forall y(y<x\vee f(x)\neq f(y))$. This means that $S^c$ is the set of functions that are eventually constantly 1 or constantly 0. As binariny strings, those are clearly countable. – UserA Oct 24 at 14:36
• @mathematicalinutiton No, there are only countably many that do run out of $1$s. – J.G. Oct 24 at 18:32
• @mathematicalinutition The ones that run our of $1$s are countable; the ones that run out of $0$s object with those, so are also countable; if the last kind of function were countable too, there would only be countably many functions to $\{0,\,1\}$, contradicting Cantor's theorem. – J.G. Oct 24 at 18:52
• @mathematicalinutition I haven't a clue what you're talking about, especially since "unfinitely" isn't a word, but I said exactly what I meant. There are countably many functions that achieve (only) finitely many $1$s, due to the aforementioned association with positive integers' prime factorizations. – J.G. Oct 25 at 13:43
I presume it's supposed to be $$f(x)=f(y)$$ instead of $$f(x)=f(x)$$? If so, an injection $$\Phi:\{0,1\}^{\Bbb N}\hookrightarrow S$$ can be devised, for instance, by setting $$\Phi(f)(n)=\begin{cases}f(n/3)&\text{if }n\equiv 0\pmod 3\\ 1&\text{if }n\equiv 1\pmod 3\\ 0&\text{if }n\equiv 2\pmod 3\end{cases}$$
Therefore $$\lvert S\rvert=\left\lvert\{0,1\}^{\Bbb N}\right\rvert=\beth_1$$.