<p>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 <span class="math-container">$\Sigma_n^0$</span>-complete formula of the form <span class="math-container">$\exists y_1 \forall y_2 \cdots Q y_n Q^* y_{n+1} \phi(x, y_1, \ldots, y_{n+1})$</span> where <span class="math-container">$Q$</span> and <span class="math-container">$Q*$</span> are the appropriate ending quantifiers. This requires only <span class="math-container">$n+1$</span> variables.</p>

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

<p>Can we construct languages for which <span class="math-container">$f_\mathcal{L}(n) = n^2$</span>? <span class="math-container">$n^k$</span>? <span class="math-container">$2^n$</span>? An Ackermann function? Are any upper bounds known?</p>

<p><strong>Edit:</strong> 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.</p>

CC BY-SA 4.0
2019-09-17T17:13:20.013Z
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?
Joshua Grochow
CC BY-SA 4.0
2019-09-17T17:56:08.077Z
@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
Stella Biderman
CC BY-SA 4.0
2019-09-17T18:07:36.667Z
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.
Stella Biderman
CC BY-SA 4.0
2019-09-17T18:29:25.183Z
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$...)
Joshua Grochow
CC BY-SA 4.0
2019-09-17T18:31:50.863Z
@JoshuaGrochow Ah yes. I meant a formal language in first order logic that is interpretable as expressing statements of arithmetic.
Stella Biderman
<lo.logic><computability>
Are there languages require many variables to achieve $\Sigma_n^0$ completeness?
Stella Biderman
# Are there languages require many variables to achieve $\Sigma_n^0$ completeness?

(Asked by: username_0 on 2019-09-16)

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.

**Tags:** lo.logic, computability

> **Comments:**
> **username_1**: 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?  
> **username_0**: @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  
> **username_0**: 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.  
> **username_1**: 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$...)  
> **username_0**: @JoshuaGrochow Ah yes. I meant a formal language in first order logic that is interpretable as expressing statements of arithmetic.  

---

## 0 answers

