The factorial function is primitive recursive, and therefore definable by a $\Sigma\_1$ formula. 
Is it also definable by a $\Delta\_0$ formula (i.e. bounded quantifiers)?
If not, why?



Is factorial definable using a $\Delta_0$ formula?
(Sorry for the earlier confusion.)


Yes, the graph of factorial is $\Delta\_0$.


First, the problem can be restated in terms of computational complexity. By a characterization going back to Bennett, $\Delta\_0$-definable predicates are exactly those computable in the linear-time hierarchy. A convenient sufficient condition is provided by Nepomnjaščiĭ’s theorem [4]: a predicate is in $\Delta\_0$ whenever it is decidable by an algorithm working simultaneously in polynomial time, and space $n^\epsilon$ for some $\epsilon<1$. In particular, all predicates computable in logarithmic space are $\Delta\_0$.


Chiu, Davida, and Litow [2], building on earlier work by Beame, Cook, and Hoover [1], proved that logarithmic space (in fact, log-space uniform $\mathrm{TC}^0$, subsequently improved to fully uniform $\mathrm{TC}^0$ by Hesse, Allender, and Barrington [3]) contains the *iterated multiplication* problem: given a sequence $x\_1,\dots,x\_n$ of integers in binary, compute their product.


By applying their algorithm to the sequence $1,\dots,n$, we can compute in logarithmic space (and in $\mathrm{TC}^0$) the factorial $n!$ when $n$ is given in unary. Consequently, we can decide in logarithmic space the graph $\{(x,y):y=x!\}$, where both $x,y$ are binary: we test whether $x$ is logarithmically smaller than $y$, and if so, compute its factorial and compare it to $y$. (Note that testing the equality of two log-space computable functions can be done in log space: we do not need to write down the intermediate results, we recompute their individual bits on the fly as needed.)


**References:**


[1] P. W. Beame, S. A. Cook, H. J. Hoover, [*Log depth circuits for division and related problems*](http://homes.cs.washington.edu/~beame/papers/division.pdf), SIAM Journal on Computing 15 (1986), no. 4, pp. 994–1003.


[2] A. Chiu, G. Davida, B. Litow, [*Division in logspace-uniform $\mathit{NC}^1$*](http://dx.doi.org/10.1051/ita:2001119), RAIRO – Theoretical Informatics and Applications 35 (2001), no. 3, pp. 259–275.


[3] W. Hesse, E. Allender, D. A. M. Barrington, [*Uniform constant-depth threshold circuits for division and iterated multiplication*](http://dx.doi.org/10.1016/S0022-0000(02)00025-9), Journal of Computer and System Sciences 65 (2002), no. 4, pp. 695–716.


[4] V. A. Nepomnjaščiĭ, *Rudimentary predicates and Turing computations [calculations]*, Doklady Akademii Nauk SSSR 195 (1970), pp. 282–284. [MR0281611](http://www.ams.org/mathscinet-getitem?mr=281611), [Zbl 0223.02031](https://zbmath.org/?q=an:0223.02031).


