-1
$\begingroup$

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) $.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ @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. $\endgroup$ – UserA Oct 24 at 14:36
  • $\begingroup$ @mathematicalinutition It was never an assumption. See latest edit. $\endgroup$ – J.G. Oct 24 at 15:21
  • $\begingroup$ @mathematicalinutiton No, there are only countably many that do run out of $1$s. $\endgroup$ – J.G. Oct 24 at 18:32
  • $\begingroup$ @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. $\endgroup$ – J.G. Oct 24 at 18:52
  • $\begingroup$ @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. $\endgroup$ – J.G. Oct 25 at 13:43
0
$\begingroup$

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$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy