Is $n+1$-th order logic always more expressive than $n$-th order logic?

Question

Is $n+1$-th order logic always more expressive than $n$-th order logic? That is to say, it means that third-order logic is more expressive than second-order, $11$-th order logic is more expressive than $10$-th order logic, etc. Is this true? And if so, what is the proof?

Answer 1

Yes, we do strictly gain expressive power in general. Working over $(\mathbb{N};+,\cdot)$ for example, $(n+1)$th-order logic can express a truth predicate for $n$th-order logic for each $n$. At this point we can diagonalize: "The set of $k$ such that the $k$th $n$-th-order formula fails on $k$" is $(n+1)$th-order definable but not $n$th-order definable.

EDIT: We can also think in terms of complexity theory. For each $n$ let $O_n$ be the set of sets of finite graphs definable by an $n$th-order sentence (that is, $\mathcal{A}\in O_n$ iff $\mathcal{A}$ is the set of finite models of $\varphi$ for some $n$th-order $\varphi$ in the language of graphs). Complexity-theoretic considerations then show that $O_n\subsetneq O_{n+1}$ for each $n$, the point being roughly that we can talk about the behavior of a machine running in time $\approx 2\uparrow\uparrow n$ using an $n$th-order sentence.

---

That said, there is a kind of "complexity collapse" here when we look more broadly:

The set of $2$nd-order validities is Turing-equivalent to the set of $n$th-order validities for each $n$.

Here's a sketch of the proof in the case $n=3$ and restricting to monadic higher-order quantifiers (that is, looking only at quantification over sets and sets of sets); it's not hard to turn this into a complete argument. Suppose I have a third-order monadic sentence $\varphi$. Consider the second-order sentence $\theta$ given by:

$\theta$: "If the universe has three sorts $A,B,C$ with $B$ being the powerset of $A$ and $C$ being the powerset of $B$, then the version of $\varphi$ with first-order variables coming from $A$, second-order variabes coming from $B$, and third-order variables coming from $C$ is true."

Then $\theta$ is a validity iff $\varphi$ is a validity. A counterexample $\mathcal{A}$ to $\varphi$ yields a counterexample to $\theta$ namely $(\mathcal{A},\mathcal{P}(\mathcal{A}),\mathcal{P}(\mathcal{P}(\mathcal{A}))$. Conversely, if $(\mathcal{A},\mathcal{B},\mathcal{C})$ is a counterexample to $\theta$ then it must satisfy the hypothesis of $\theta$, which is to say we must have $\mathcal{B}=\mathcal{P}(\mathcal{A})$ and $\mathcal{C}=\mathcal{P}(\mathcal{P}(\mathcal{A}))$. But then since the conclusion of $\theta$ must fail of this structure we get $\mathcal{A}\models\neg\varphi$.