User:IssaRice/Computability and logic/First graph principle using a semirecursive relation

This is about proposition 7.17 (first graph principle) in Boolos, Burgess, Jeffrey's Computability and Logic.

The proof in the book defines two functions as follows:

$g(x)={\begin{cases}{\text{the least }}w{\text{ such that}}\\\quad \exists y<w\;\exists z<w\;Sxyz&{\text{if such a }}w{\text{ exists}}\\{\text{undefined}}&{\text{otherwise}}\end{cases}}$

$h(x,w)={\begin{cases}{\text{the least }}y<w{\text{ such that}}\\\quad \exists z<w\;Sxyz&{\text{if such a }}y{\text{ exists}}\\{\text{undefined}}&{\text{otherwise}}\end{cases}}$

How would one discover such functions? It seems like a first attempt would be:

$f(x)={\begin{cases}{\text{the least }}y{\text{ such that}}\\\quad \exists z\;Sxyz&{\text{if such a }}y{\text{ exists}}\\{\text{undefined}}&{\text{otherwise}}\end{cases}}$

Of course, the relation $\exists z\;Sxyz$ is semirecursive, not recursive, and this is the problem.

If the relation were recursive, then by proposition 7.9 we would know that $f$ is recursive. So the next question is, what is so special about the recursive relation in proposition 7.9? Can we replace it by a semirecursive relation and get a similar result?

If the characteristic function was recursive (and total) then it seems like we would be able to use the same proof. But in the case of a semirecursive relation, the characteristic function is not necessarily recursive.

What if we use the semicharacteristic function? The problem now is that a semicharacteristic function only takes on the value 1 (where it is defined), so the minimization will just be undefined everywhere.

Since the proof of proposition 7.9 uses the characteristic function of ${\sim }R$, we might use a "bit-flipped" semicharacteristic function $g$ defined by $g(x,y)={\overline {\operatorname {sg} }}(c(x,y))$, where $c$ is the semicharacteristic function of $\exists z\;Sxyz$. Now $g$ only takes on the value 0 (where it is defined). This means the minimization will return after the first step, returning 0, or else is undefined.

I guess the upshot here is that it's really nice to have a recursive characteristic function because the minimization works to define a useful function.