Can we make witnesses for membership of $\Sigma_2$ sets unique?

Question

A $\Sigma_2$ set $A$ is one for which there is a computable relation $R(x, s, t)$ s.t. $x \in A \iff \exists s \forall t \colon R(x, s, t)$.

Can we use $R$ to produce another computable relation $Q$ determining membership of $A$ in the same fashion, but where $S_Q(x) = \{ s \ | \ \forall t \colon Q(x, s, t) \}$ (the set of witnesses for $x$ wrt $Q$) has a unique element?

The best I have so far is that if there is some computable $f$ s.t. $f(x) \in S_R(x)$ whenever $S_R(x)$ is non-empty, we can get the result by sabotaging the cases where $s \neq f(x)$. But I don't see how I can construct such $f$ or otherwise argue one exists.

Answer 1

You can compute such a "unique witness" $Q$ from $R$, using that pseudo-python code :

def Q(x,s,t) :
    r,u,a=0,0,False
    for i in range(s) : # repeat s times
        a=R(x,r,u)
        if a : u+=1
        else : r+=1
    if a : return False
    else : return R(x,r,t)

Answer 2

A strategy to compute such a $Q(x, s, t)$ is as follows. First check $R(x, 0, 0)$. If it holds, bump up the last entry by $1$, and check again. If it doesn't hold, set the last entry to $0$, and bump up the second entry by $1$. Repeat this $s$ times. The process we are undertaking is making a "best guess" at a witness (sitting in the second entry of our last $R(x, \cdot, \cdot)$ call). In short, we are guessing the least $s$ for which $R(x, s, t)$ has held for all $t$ checked so far. If there is a witness, we will eventually find the first one, and never change our guess.

So, we have our guess at the witness $s_0$. If when computing $Q(x, s-1, t)$ we arrive at the same guess, then $Q(x, s, t)$ does not hold. Otherwise, $Q(x, s, t) = R(x, s_0, t)$.

So if a witness does not exist for $x$ wrt $R$, then $Q$ does not find one either. If one does, then eventually at some $s_1$ we guess the right witness for the first time, and $s_1$ is then a witness for $x$ wrt $Q$. But our guess at the first witness never changes after this, so for $s>s_1$, computing $Q(x, s, t)$ finds that we used the same guess $s_0$ as when computing $Q(s, s-1, t)$, and as such, does not hold. Hence $s_1$ is a unique witness.