1
$\begingroup$

In what follows, $\phi_n$ is the $n$th partial recursive function, and $\phi_n^g$ is the $n$th partial recursive function with oracle $g$.

We say $x\in\mathbb{N}$ is pre-total if the following two conditions hold:

  • For all distinct $y,z<_\mathcal{O} x$, we either have $y<_{\mathcal{O}} z$ or $z<_\mathcal{O} y$, where $<_\mathcal{O}$ is the ordering on Kleene's $\mathcal{O}$.
  • If $x=3\cdot 5^e$ then $\phi_e$ is total.

We say $x$ is total if it is pre-total and all $y<_\mathcal{O} x$ are pre-total.

Consider the following conditions on a binary function $f$:

  1. $f(x,y)=0$ or $f(x,y)=1$
  2. $f(1,y)=0$
  3. $f(2^x,y)=1\iff \phi_y^{f(x,\cdot)}(y)\downarrow$
  4. $f(3\cdot 5^x,\langle u,v\rangle)=1\iff$ there exists an $n$ such that $u<_\mathcal{O} \phi_x(n)$ and $f(u,v)=1$.

I'd like to show that no hyperarithmetical (that is, $\Delta_1^1$ and total) function $f$ can satisfy conditions (1)-(5) for all total $x$ and $y$.

I'm having trouble getting started, in part because I don't really see what these properties are encoding. Any help would be appreciated.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.