How many variables do you need to be complete for $\Sigma^0_n$?

149 Views Asked by At

The arithmetic hierarchy is a structure on sentences in first order logic. It has a particular relationship with computability, due to Post’s Theorem.

In most discussions of the arithmetic hierarchy, it’s assumed that you have access to every formula $\phi$ in first order logic. But what if you don’t? Specifically, what if we define $\Sigma_{n,m}^0$ to be the usual set $\Sigma_n^0$ except you only have formulae with a total of $m$ variables ($n\leq m$).

What’s the computability theoretic power of this set? Is there a number of variables that is sufficient to get the full power of $\Sigma_n^0$? What if we set $m=n$?

1

There are 1 best solutions below

3
On BEST ANSWER

By Matiyasevich's Theorem, the universal $\Sigma_n$ formula is equivalent to one of the form

$\exists y_1 \forall y_2 \cdots Q y_n Q^* y_{n+1} \phi( x, \bar y)$,

where $Q$ and $Q^*$ are the appropriate quantifier and bounded quantifier, respectively, and $\phi$ is free of quantifiers. This means you only need $n+1$ variables to get the full power of $\Sigma_n$---with the caveat, as @James has brought up, that your language should be the same one used by Matiyasevich.

Removing one variable reduces your computational power to that of $\Sigma_{n-1}$. For example, if $\phi$ is quantifier-free, the set $\{x :\exists y \phi(x,y)\}$ is decidable by first using calculus to find upper and lower bounds on the possible $y$, and then checking each value by hand.