Is this given set recursive, r.e. or none of them? Informal argument ok?

Question

I am working on an exercise for my computability course. The question is stated as:

Is the following set
$\{x|\text{ whenever } y<y', \text{ if } \phi_{x}(y)\downarrow \text{ and } \phi_{x}(y')\downarrow \text{, then } \phi_{x}(y) \lt \phi_{x}(y') \}$ recursive, r.e. or none of them? Motivate your answer.

So, i intuitively think that it is neither.

• To show this, I would first use Rice's theorem to show that the set (lets call it $A$) is not recursive, since it is extensional ($i \in A, \phi_{i} \simeq \phi_{j} \rightarrow j \in A$) and $A \neq \emptyset$ and $A \neq F_{comp}$ where $F_{comp}$ is the set of all computable functions.

• In a second step, I would then check if $\overline{A}$ is r.e. and argue that according to Post theorem, $A$ can't then be r.e. too. This check leads me to the conclusion that $\overline{A}$ is not r.e. (which I would like to show by a reduction to ALL-HALTING).

• So, in a third step (when $A$ is not recursive and $\overline{A}$ is not r.e.), I want to check if $A$ is r.e.: This, I would essentially do by showing that there can't be a computable function $$f(x) = \left\{ \begin{array}{ll}1 & f'(x,y,y') = 1 \text{ (this would check if } x \in A)\\ \uparrow & \text{otw.}\\ \end{array} \right.$$

that relies on $f'$ to be computable, since $f'$ is also reducable to ALL-HALTING (checking all pairs of $(y,y')$ for even one $x$ in the set would take infinite time).

Now, I am not entirely sure if this train of thought makes sense.. So I would be very thankful if you could point out if this is utter bullshit, somewhat ok for an informal argument or something inbetween.

Go easy on me, I am still learning the definitions commonly used in computability theory ;)

Answer 1

Your first two steps are basically correct, but I don't really understand what you're trying to say in your third step.

It is true that $A$ is not recursive and the argument you give in your first step is correct.

It is true that $A$ is not r.e. and the strategy you outline in your second step is basically correct (i.e. show that $\overline{A}$ is r.e. so $A$ cannot be r.e. since it is not recursive). But I don't think it is a good idea in this case to show that $\overline{A}$ is r.e. by reducing it to the halting problem (although it is of course possible to do that). In this case it is easier to just directly show it is r.e. using whatever definition of r.e. is most convenient. And I'm not sure why you conclude $\overline{A}$ is not r.e. It is. One way to see this is to write a definition for it which uses only existential quantifiers over a computable predicate. Namely: $$ x \in \overline{A} \iff \exists y\, \exists y'\, \exists t\, [(y < y') \land (\varphi_x(y) \text{ and } \varphi_x(y') \text{ both halt in at most } t \text{ steps}) \land (\varphi_x(y) \geq \varphi_x(y'))]. $$ The point is that the part in square brackets is computable.

I think in your third step you are suggesting that you believe $\overline{A}$ is not r.e. As I have just said, this is false. So this step seems unnecessary. But I also think you have written it in a confusing way. For instance, you mention $f$ and $f'$, but you never define $f'$ and only define $f$ in terms of $f'$. What are they supposed to be? If you don't define them, what you have written is hard to understand. Since I don't understand what your third step is supposed to mean, I can't really tell if it is correct or not.

As a final thought, if you are trying to calculate the complexity of a set a good first step is to write it a formal definition for it and then put that definition into prenex normal form (all unbounded quantifiers at the front of the formula). This immediately provides you with an upper bound on the complexity. This is all that I have done with $\overline{A}$ above to see that it is r.e.