# Proving or disproving a set of total functions is countable

Let S be the set of total functions from $N \rightarrow M$, such that for each $f \in S$, there is $i > 1$ such that for all $j < i$, $f(i)$ and $f(j)$ are not equivalent Turing machines. Prove or disprove that S is countable

I don't think this is actually countable, but I'm having a hard tie proving this using diagonilzation. Can anyone give me pointers / hint? Preferably explained at a lower level.

Hint: Let $M_1,M_2$ be an arbitrary pair of inequivalent Turing machines. Your set $S$ contains all functions satisfying $f(1) = M_1$ and $f(2) = M_2$.
• Okay. Here's my attempt. Wondering if I've done anything glaringly wrong. Let $M_1$ and $M_2$ be an arbitrary pair of inequivalent Turing achines. Note that by definiton of S we have that $S$ contains all functions satisfying $f(1) = M_1$ and $f(2) = M_2$. Suppose $S$ is countable. Then there exists an exhaustive list of these functions: $f_0, f_1, ....$. Consider $g: N \rightarrow M$ defined by $g(x)=f_x((x+1)mod 2 + 1)$. (I made f(1) -> f(2) and f(2) -> f(1)). By definition we have that $g(x) \ne f_x(x)$ for all $x$ and so $S$ cannot be countable. – Overflow2341313 Dec 14 '17 at 21:08