Everything here is in the L-structure $\mathbb N = (\mathbf N;0,S,+,\cdot,<)$. I was following these notes and got stuck with the lemma 5.1.11 page 84 of paper (88 pdf):
In this context we assume that +,$\cdot$,$R$,$I^n_i$ are computable where $R$ are relations and $I^n_i$ is the coordinate function (just indexes). We assume composition of computable functions are computable and that search s.t. some property holds is computable i.e. $\mu x( G(a,x) = 0 ) = arg \min_{x \in N}\{ G(a,x) = 0 \}$ if $\exists x$ s.t. $G(a,x) = 0$ is computable. Also, $F_R(a,y) := \mu x( R(a,x) \lor x = y )$ has already been shown to be computable.
So the goal is to show that the indicator/characteristic function of the relations $P$ and $Q$ are computable. Let's consider the relation $P$ first. We want to show the following is computable (in the formal sense defined here and the notes):
$$ X_P(a,y) = \begin{cases} 1 & \text{ if } \exists x \in \mathbf N (x < y \to R(a,x) ) \\ 0 & \text{ if } \forall x \in \mathbf N (x \geq y \land \neg R(a,x) ) \end{cases} $$
the solution seems to be $X_P(a,y) := X_<(F_R(a,y),y)$ which doesn't make sense to me.
The reason is that we want the indicator function that returns true if there does exist a real number s.t. the implication $x<y \to R(a,x)$ is true. My claim is (if I understand things correctly) that this indicator function is really boring because it always returns 1. This is because it requires the implication $x<y \to R(a,x)$ to be true for some $x$. But such an $x$ always exists because we are only allowed to use natural numbers (i.e. we are in the L-structure $\mathbb N$), so we can trivially find such an $x$ by setting $x=y$ (then it doesn't matter if $R(a,x)$ is false or not because the antecedent is false). Thus since $\mu x (x = y)$ and that always exists then we have $X_p(a,y) := X_=(\mu x (x = y),y)$. Which seems extremely silly. So I must have some very weird misconception or something.
In fact I just noticed that it is possible for some $R$ for this function to want to return both 1 and 0 at the same time. By my previous argument $x=y$ makes the antecedent false so it returns 1. Now consider when it returns 0. For it to return zero we must not have a natural number x s.t. $(x<y \to R(a,x)$. Equivalently we must have that $\forall x \in \mathbf N, (x<y \land \neg R(a,x))$. If we just choose an $R$ such that its always false for $x<y$ (say x is not zero), then we have that the condition for false is satisfied simultaneously to the condition to true. Which obviously doesn't make sense and something must be wrong in my reasoning of course (since the conditions for the function seem quite sensible to me, intuitively, I don't see why they encode the halting problem in any funky way, so I assume I wrong somewhere).
Do I have a misunderstanding or misinterpret something?
Natural number bounded quantifiers are computable if their formula arguments are computable. In the simplest case you can see that in that you provide a primitive recursive def.
$P(a,0) \leftarrow \bot$
$P(a,y+1) \leftarrow P(a,y) \vee R(a,y)$
$Q(a,0) \leftarrow \top$
$Q(a,y+1) \leftarrow Q(a,y) \wedge R(a,y)$
Computable predicates are closed over primitive recursion. The $μ_{x<y}$ operator from the script in Lemma 5.1.10 is a form of primitive recursion.
Disclaimer: I am assuming that computable means here nothing more primitive than primitive recursive, rather something above. I didn't read the full script.