# Pointclass of $\text{dom}(F)$ where $F:\omega^\omega\rightarrow\omega^\omega$ is partial recursive.

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.

• 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$? Apr 26 '15 at 2:18
• Yes, that's exactly right, all the things you said are correct. Apr 26 '15 at 3:41
• 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. Apr 26 '15 at 20:54
• 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. 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.

• 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. Apr 26 '15 at 11:53
• Not sure what do you mean. It holds only for boldface classes.
– 喻 良
Apr 26 '15 at 14:18
• @喻良: 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$. Apr 26 '15 at 20:52
• i guess you must misunderstood something. Which book is it from?
– 喻 良
Apr 26 '15 at 23:24
• 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. Apr 27 '15 at 2:14