5
$\begingroup$

The proof of Post's Theorem that I am familiar with assumes you have access to as many variables as you wish in your language. Matiyasevich's Theorem by contrast gives a $\Sigma_n^0$-complete formula of the form $\exists y_1 \forall y_2 \cdots Q y_n Q^* y_{n+1} \phi(x, y_1, \ldots, y_{n+1})$ where $Q$ and $Q*$ are the appropriate ending quantifiers. This requires only $n+1$ variables.

The number of variables required to actually demonstrate $\Sigma_n^0$-completeness of particular language is a function of the particular language being used that we might denote $f_\mathcal{L}(n)$. Note that by "language" here I mean a formal language in first order logic that is interpretable as expressing statements of arithmetic.

Can we construct languages for which $f_\mathcal{L}(n) = n^2$? $n^k$? $2^n$? An Ackermann function? Are any upper bounds known?

Edit: Josh Grochow asked about distinguishing between variables and quantifiers. After some thought, I think that the number of variables can always be made to be one more than the number of unbounded quantifiers so the distinction isn't particularly important.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ This seems potentially very interesting, but in starting to think about it I realized I'm not quite sure what you mean "The num of vars required to demonstrate completeness in a particular lang." Does it just mean the number needed to define L? Do you only care about quantifier alternations, or really number of variables? If you have lots of variables under the same quantifier you can package them into a single variable at the cost of making your formula a bit longer... For number of alternations for $\Sigma^0_n$, I think you always need at least n and never more than n? $\endgroup$
    – Joshua Grochow
    Sep 17 '19 at 17:13
  • $\begingroup$ @JoshuaGrochow Thinking about your question has made me doubt some of what I believe about this, but I think there's still something interesting here. I'm going to tentatively concede that differentiating between variables and quantifiers isn't interesting. $\Sigma_0^0$ is what can be expressed with bounded quantifiers in the language of first-order arithmetic, so I assume you mean $n+1$ instead of $n$. If you can express an arbitrary arithmetical statement then you're right that you need exactly $n+1$. However, it seems that if you can only express some statements in a language, the language $\endgroup$
    – Stella Biderman
    Sep 17 '19 at 17:56
  • $\begingroup$ might require more quantifiers. You can write down a $\Sigma^0_7$ statement that is logically equivalent to a $\Sigma^0_5$ statement, and it seem plausible to me that a language might be able to express the former but not the later. An attempt at constructing such a language might involve making + a ternary operation instead of a binary one. The interpretation of +(a,b,c) is still the same as the arithmetical $a+b+c$, but $a+b$ is not a wff. This doesn't actually end up requiring more quantifiers as you can recover $a+b$ by writing $+(a, b, 0)$, but some other construct might not be like that. $\endgroup$
    – Stella Biderman
    Sep 17 '19 at 18:07
  • $\begingroup$ Ah, I think I see now. By "language" you didn't mean "decision problem," you literally meant the logical (first-order, I presume?) language in which the decision problem is expressed, right? (Also, though this is a minor point, I think I meant $n$, not $n+1$: $\Sigma^0_0$ is the computable problems, which are precisely those expressible with 0 unbounded quantifiers, $\Sigma^0_1$ is the degree of the halting problem, precisely those expressible with a single unbounded $\exists$...) $\endgroup$
    – Joshua Grochow
    Sep 17 '19 at 18:29
  • $\begingroup$ @JoshuaGrochow Ah yes. I meant a formal language in first order logic that is interpretable as expressing statements of arithmetic. $\endgroup$
    – Stella Biderman
    Sep 17 '19 at 18:31

Your Answer

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

Browse other questions tagged or ask your own question.