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.


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.