Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm having trouble with the notation in Sacks' Higher Recursion Theory. I've asked specific questions from page 4. Instead of reading my question in detail and trying to understand my confusion (which would be appreciated), one could probably just read the blockquotes below and tell me exactly what they're supposed to mean in "everyday" mathematical language.

Sacks writes

A predicate $R(f,x)$ is recursive if there is an $e$ such that:
(i) $(f)(x)[\{e\}^{f}(x) \text{ is defined}]$
(ii) $(f)(x)[R(f,x) \leftrightarrow \{e\}^{f}(x)=0]$

What is the purpose/function of the $(f)(x)$ at the beginning of each of items (i) and (ii)? It seems that the purpose is to denote that those are free variables, but then he says

$$ \begin{equation} (Ex)(f)(Eg)R(x,y,f,g,h) \text{ and } (Ef)(h)S(f,h,z) \tag{1} \end{equation} $$ are analytical if $R$ and $S$ are recursive.

If my hypothesis about free variables is correct, then I wonder why there is no $(h)(y)$ before $(Ex)(f)(Eg)R(x,y,f,g,h)$ (and similarly for the second conjunct). (I bolded what is intended to be an implicit question; if someone'd like me to make it explicit, I will.)

Finally, Theorem 1.3 reads

If $P(f,x)$ is analytical, then it can be put in one of the following forms: $$ (Eg)(y)R(f,x,g,y), \quad (Eg)(h)(Ey)R(f,x,g,h,y)\ldots $$ $A(f,x)$ $$ (g)(Ey)R(f,x,g,y), \quad (g)(Eh)(y)R(f,x,g,h,y)\ldots $$ where $A$ is arithmetic and $R$ is recursive.

Why is the $A(f,x)$ left justified and on its own line?

share|cite|improve this question
up vote 3 down vote accepted

$(f)$ means "for all $f$", $(Ex)$ means "there exists an $x$". That should clear up the first question. We are saying: Call an index $e$ total iff no matter what $f,x$ are, $\{e\}^f(x)$ is defined. Then $R$ is recursive iff there is a total $e$ such that, for any $f,x$, $R(f,x)$ holds iff $\{e\}^f(x)=0$.

In (1), you want $y,h,...$ to be free variables, so you are not quantifying over them. In Theorem 1.3, Sacks is saying: If $P(f,x)$ is analytical, then either there is an arithmetic $A$ such that $P(f,x)$ iff $A(f,x)$, or else there is a recursive $R$ such that $P$ can be put in one of the following forms... and then he describes the two infinite lists of possible forms. In the ones on top, the statements are existential quantifier, in the others, the statements are universal.

share|cite|improve this answer
Thanks, that certainly clears things up. Any idea why the $A(f,x)$ in Theorem 1.3 is left-justified? – Quinn Culver May 2 '12 at 23:16
A purely stylistic choice. – Andrés E. Caicedo May 3 '12 at 2:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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