1

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.

G. H. Faust
  • 1,766
  • You will not be able to build such an $f$ in the general case. (A would only be $\Pi_1$ if you can) – Xoff Nov 04 '15 at 17:43

2 Answers2

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)
Xoff
  • 10,310
  • While trying to understand the strategy of your answer, I arrived at a similar solution myself (I'm writing up my own answer), so thanks—but I don't think this is quite right. The for-statement looks through values of $s$ (I.e. $r$) for a current best guess at the first witness, and if its guess is wrong then no harm is done. If one exists then it eventually finds the first witness $s$, and $r$ never exceeds this value, so from then on the for-loop exits with $a$ true. Then it always returns False from this point on, so there can be no witness at all. – G. H. Faust Nov 07 '15 at 04:50
  • @G.H.Faust I'm not sure what's wrong with my answer. Once you find a potential witness 's', yes, all subsequent witnesses are False, to make 's' unique. It doesn't prevent Q to have that witness. So I don't understand your comment. For example if $R(x,0,n)$ only fails for $n=10$ but $R(x,1,n)$ is always true for all $n$, then $Q(0,x,y)=R(0,x,y)$ $Q(x,n,z)$ fails for all $0<n<11$ (and for all $z$) and $Q(11,x,y)=R(1,x,y)$ and then $Q$ has a unique witness $11$. – Xoff Nov 08 '15 at 23:11
  • Ah, I see now—the value of $a$ is always assigned before $r$ is incremented, so it lags one behind, and consequently the for-loop does not exit with $a$ true the very first time it finds a new witness. – G. H. Faust Nov 09 '15 at 01:06
0

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.

G. H. Faust
  • 1,766