Enumerating relations that are true infinitely often

Question

Let us concentrate on relations on natural numbers. Is it possible to enumerate all computable unary relations that are true infinitely often? I would guess no but I can't see a direct way to prove it.

Answer 1

Note that unary relations on the natural numbers are just sets. So computable unary relations are just computable sets. Each computable enumerable set has an index which is a natural number. Let $W_e$ denote the $e^\text{th}$ computable enumerable set.

Let $A = \{e : W_e \text{ is computable and } W_e \text{ is infinite }\}$. Now let us suppose that $A$ is computably enumerable.

Let $\Phi_e$ denote the $e^\text{th}$ Turing machine. $\bar{H} = \{e : \Phi_e(e) \text{ does not halt }\}$. It is well known that the halting problem is a computable enumerable incomputable set. Hence the complement $\bar{H}$ is not computably enumerable.

Now for each $e$. Let $S_e = \{s : \Phi_e(e) \text{ has not halted in $s$ steps }\}$. Note that $S_e$ is always computable since $S_e$ is either finite or all of the natural numbers. Because the process defined above is computable uniformly, there is a computable function $f$ such that $S_e = W_{f(e)}$. Hence if $\Phi_e(e)$ does not converges, then $S_e = W_{f(e)} = \omega$ is infinite. If $\Phi_e(e)$ does converge then, $S_e$ is finite.

So the $f$ above is a computable reduction of $\bar{H}$ to $A$. Since we assumed that $A$ is computable enumerable, this means that $\bar{H}$ is also computably enumerable. But this contradicts the well-known fact that $\bar{H}$ is not computably enumerable.