The definition I am working with:

A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is said to be partial recursive iff the partial function $G:\omega^\omega\times\omega\rightarrow\omega$ s.t. $G(f,i)=F(f)(i)$ has a $\Sigma^0_1$ graph.

My definition does not mention anything about the domain of $G$, but I am assuming that $\text{dom}(G)=\text{dom}(F)\times\omega$

Under this assumption I seem to be getting that $f\in\text{dom}(F)\iff\exists i\exists j[G(f,i)=j]$, which means that $\text{dom}(F)$ is $\Sigma^0_1$.

However, later on in my notes there is a remark that says: "There is a partial recursive function $F:\omega^\omega\rightarrow\omega^\omega$ s.t. $\text{dom}(F)$ is not $\Sigma^0_2$".

So I'm making a mistake somewhere. Am I making the wrong assumption as to what the domain of $G$ should be?

Any help is appreciated, Thanks.

  • $\begingroup$ Just for clarification, I assume that $\omega^\omega$ the set of all total functions $\omega\to\omega$, but including for example ones that are not even arithmetical, right? And the statement that $\operatorname{dom} F$ is not $\Sigma^0_2$ asserts that there is no second-order $\Sigma^0_2$ formula with $f$ free that is true exactly when $f\in\operatorname{dom} F$? $\endgroup$ Apr 26 '15 at 2:18
  • $\begingroup$ Yes, that's exactly right, all the things you said are correct. $\endgroup$
    – user52534
    Apr 26 '15 at 3:41
  • $\begingroup$ It seems your reasoning is right, then. Perhaps if you reveal which book/notes you have these definitions from, someone would be able to check if you have missed something pertinent in them. $\endgroup$ Apr 26 '15 at 20:54
  • $\begingroup$ The definition is from class notes from a mathematical logic course I took a few years back. I may have copied something down incorrectly, or left something out, but the definition I have reads: "A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is partial recursive iff the function $G(f,i)=F(f)(i)$ is partial recursive". This definition translates into the definition I gave earlier. This definition also assumes uniqueness of such a function $G$, but more info for $G$ is required (like its domain for instance), otherwise a $G$ having the property stated won't necessarily be unique. $\endgroup$
    – user52534
    Apr 27 '15 at 1:25

I guess the definition should be like this:

A partial function $F: \omega^{\omega} \to \omega^{\omega}$ is said to be partial recursive iff there is a partial recursive function $G:\omega^{\omega}\times \omega\to \omega$ s.t. for any $f$, $f\in dom(F)\Leftrightarrow\forall i(G(f,i)\downarrow)$. Then $F(f)(i)$ is defined as $G(f,i)$.

Then $f\in dom(F)$ if and only if $\forall i\exists j (G(f,i)=j)$. So $dom(F)$ is $\Pi^0_2$. But this is a weird definition.

  • $\begingroup$ Don't you have a similar result as in descriptive set theory, that if a set is not $\Sigma^0_2$ then it is $\Pi^0_2$-hard? If this is so, this definition would be optimal. $\endgroup$ Apr 26 '15 at 11:53
  • $\begingroup$ Not sure what do you mean. It holds only for boldface classes. $\endgroup$
    – 喻 良
    Apr 26 '15 at 14:18
  • $\begingroup$ @喻良: The OP specifies that $\operatorname{dom}(G) = \operatorname{dom}(F)\times \omega$ (as it must logically be if $F(f)$ is always either total or undefined). Given that assumption, $\forall i\exists j \,G(f,i)=j$ is equivalent to $\exists i\exists j \,G(f,i)=j$, which is $\Sigma^0_1$. $\endgroup$ Apr 26 '15 at 20:52
  • $\begingroup$ i guess you must misunderstood something. Which book is it from? $\endgroup$
    – 喻 良
    Apr 26 '15 at 23:24
  • $\begingroup$ It is from class notes for a course I took a few years ago. I may have copied it down incorrectly. Thanks for your answer. To clarify, the correct definition should be: A partial function $F:\omega^\omega\rightarrow\omega^\omega$ is said to be partial recursive iff there is a partial function $G:\omega^\omega\times\omega\rightarrow\omega$ with a $\Sigma^0_1$ graph s.t. $\forall f[f\in\text{dom}(F)\iff \forall i[G(f,i)\downarrow]]$ and $\forall f\in\text{dom}(F)\forall i[F(f)(i)=G(f,i)]$. This makes much more sense now. $\endgroup$
    – user52534
    Apr 27 '15 at 2:14

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.