Are more classes of structures axiomatizable as you increase the order of the logic?

Question

This is similar to a question I asked before, but slightly different. Is it the case that $n+1$-th order logic can axiomatize more classes of structures than $n$-th order logic? So, for example, are there classes of structures that are second order axiomatizable but not first order axiomatizable, are there classes of structures that are third order axiomatizable but not second order axiomatizable, and so on?

Answer 1

Here's a sketch of a solution; I'll fill in the details later when I have time.

Let $\mathcal{N}=(\mathbb{N};+,\times)$ be the standard model of arithmetic. For $n>0$, let $(\varphi_i^n)_{i\in\mathbb{N}}$ be some "reasonable" enumeration of all order-$n$ formulas in the language of arithmetic, and let $$X_n=\{\langle i,j\rangle: i\in (\varphi^n_j)^\mathcal{N}\}$$ be the standard listing of the $n$th-order-definable subsets of $\mathcal{N}$. By diagonalization $X_n$ is not $n$th-order-definable over $\mathcal{N}$; a bit less obviously (but think about "Skolem functionals" of appropriate type), $X_n$ is always $(n+1)$th-order definable over $\mathcal{N}$. This implies that the expansion $\mathcal{N}_n$ of $\mathcal{N}$ by a unary predicate corresponding to $X_n$ is pinned down by an $(n+1)$th-order formula, and so its isomorphism type is an $(n+1)$th-order elementary class (note that since $n>0$ the "base structure" $\mathcal{N}$ is pinned down by an $(n+1)$th-order sentence, so we only have to think about the $X_n$ part).