<p>As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it works pretty much the same as in the second-order case.</p>

<p>More precisely, define the iterated exponential function <span class="math-container">$2_d^x$</span> by
<span class="math-container">$$\begin{align*}2_0^x&amp;=x,\\2_{d+1}^x&amp;=2^{2_d^x}.\end{align*}$$</span>
Let <span class="math-container">$\Sigma^d_m$</span> denote in the usual fashion the class of <span class="math-container">$(d+1)$</span>th order sentences that consist of <span class="math-container">$m$</span> alternating blocks of <span class="math-container">$(d+1)$</span>th order quantifiers starting from existential, followed by a <span class="math-container">$d$</span>th order formula. (Note that the superscript is off by one from the order. Don’t blame me for this historical peculiarity.)</p>

<p>Then:</p>

<ul>
<li><p>For any <span class="math-container">$d,m\ge1$</span>, the class of all <span class="math-container">$\Sigma^d_m$</span>-expressible languages is exactly <span class="math-container">$\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$</span>.</p></li>
<li><p>Thus, for any <span class="math-container">$d\ge1$</span>, the languages expressible in <span class="math-container">$(d+1)$</span>th order logic are exactly those from the <span class="math-container">$2_{d-1}^x$</span>-time hierarchy: <span class="math-container">$\bigcup_m\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$</span>. For example, second-order logic corresponds to <span class="math-container">$\mathrm{PH}$</span>, and third-order logic to <span class="math-container">$\mathrm{EXPH}$</span>.</p></li>
<li><p>Thus, the class of languages expressible in all of finite-order logic is <span class="math-container">$\mathrm{ELEMENTARY}$</span>.</p></li>
</ul>

<p><strong>Reference:</strong></p>

<p>[1] Leszek Kołodziejczyk: <em>Truth definitions in finite models</em>, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200, doi: <a href="https://doi.org/10.2178/jsl/1080938836" rel="noreferrer">10.2178/jsl/1080938836</a>.</p>

CC BY-SA 4.0
2019-11-11T17:29:27.153Z
2019-11-11T17:29:27.153Z
Emil Jeřábek
<p>In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to? </p>

CC BY-SA 4.0
2019-11-11T06:11:30.710Z
@EmilJeřábek Please make that an answer! Maybe to you it's obvious, but that's pretty cool.
Huck Bennett
<descriptive-complexity>
Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?
DeeDee
# Second order logic = PH. Do even higher order logics correspond to anything on complexity side of things?

(Asked by: username_0 on 2019-11-10)

In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?

**Tags:** descriptive-complexity

> **Comments:**
> **username_1**: @EmilJeřábek Please make that an answer! Maybe to you it's obvious, but that's pretty cool.  

---

## 1 answers

### Answer by username_2 on 2019-11-11. Score: 11

As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it works pretty much the same as in the second-order case.

More precisely, define the iterated exponential function $2\_d^x$ by
$$\begin{align\*}2\_0^x&=x,\\2\_{d+1}^x&=2^{2\_d^x}.\end{align\*}$$
Let $\Sigma^d\_m$ denote in the usual fashion the class of $(d+1)$th order sentences that consist of $m$ alternating blocks of $(d+1)$th order quantifiers starting from existential, followed by a $d$th order formula. (Note that the superscript is off by one from the order. Don’t blame me for this historical peculiarity.)

Then:

* For any $d,m\ge1$, the class of all $\Sigma^d\_m$-expressible languages is exactly $\Sigma\_m\text-\mathrm{TIME}\bigl(2\_{d-1}^{\mathrm{poly}(n)}\bigr)$.
* Thus, for any $d\ge1$, the languages expressible in $(d+1)$th order logic are exactly those from the $2\_{d-1}^x$-time hierarchy: $\bigcup\_m\Sigma\_m\text-\mathrm{TIME}\bigl(2\_{d-1}^{\mathrm{poly}(n)}\bigr)$. For example, second-order logic corresponds to $\mathrm{PH}$, and third-order logic to $\mathrm{EXPH}$.
* Thus, the class of languages expressible in all of finite-order logic is $\mathrm{ELEMENTARY}$.

**Reference:**

[1] Leszek Kołodziejczyk: *Truth definitions in finite models*, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200, doi: [10.2178/jsl/1080938836](https://doi.org/10.2178/jsl/1080938836).


---

