Spectrum Problem for Higher-Order Logic

Question

Definitions. Given a sentence $\varphi$ of $n$th-order logic, we define the spectrum of $\varphi$ to be the set of cardinalities of finite structures that satisfy $\varphi$. A set $X\subseteq\mathbb N$ is said to be an $n$th-order spectrum if there is an $n$th-order sentence whose spectrum is $X$. Given any positive integer $n$, let $S_n$ be the set of all $n$th-order spectra. An $\omega$-order spectrum is an element of the set $S_{\omega}:=\bigcup_{n\in\mathbb Z_+}S_n$.

Questions.

1. Clearly, $S_n\subseteq S_{n+1}$ for each positive integer $n$. One knows that $S_1\subsetneq S_2$ (J. H. Bennett, On spectra, 1962).

   Do we have $S_n\subsetneq S_{n+1}$ for each positive integer $n$?

2. One does not know if the complement of a first-order spectrum is also a first-order spectrum. That is why I wonder:

   Is the complement of a second-order spectrum always a second-order spectrum? Is the complement of a third-order spectrum always a third-order spectrum? ...

3. For each positive integer $n$, every element of $S_n$ is decidable. But we can always construct a decidable set $D_n$ which is not in $S_n$: We simply construct the diagonal set $D_n$ such that $m \in D_n$ if and only if $m$ is not in the $m$th $n$th-order spectrum. (source, page 2)

   Is $D_n$ always an element of $S_{n+1}$? Is $D_n$ always an element of some $S_p$, where $p>n$?

4. Is the complement of an $\omega$-order spectrum always an $\omega$-order spectrum?

Answer 1

One can answer questions about higher-order spectra by characterizing $S_d$ as certain complexity classes, based on similar characterizations for classes of structures definable by fragments of higher-order logic.

Let me first recall how things work for the base case (first-order logic, i.e., $S_1$). Let $\phi$ be an FO sentence in a finite relational signature $\sigma=\{R_1,\dots,R_k\}$. If we reconsider each $R_i$ as a second-order variable, we can quantify them away in second-order logic to get the $\Sigma^1_1$ sentence $$\Phi=\exists R_1\dots\exists R_k\,\phi(R_1,\dots,R_k)$$ in the empty signature with the property $$\exists M\,(|M|=n\land M\vDash\phi)\iff M_n\vDash\Phi,$$ where $M_n$ denotes the $n$-element model with no extra structure. Conversely, every $\Sigma^1_1$ sentence in the empty language is of the form $\Phi$ for some first-order $\phi$. Thus, FO spectra are exactly sets of the form $$\{n\in\mathbb N:M_n\vDash\Phi\}$$ for $\Sigma^1_1$ sentences $\Phi$ in the empty signature.

Now, Fagin's theorem states

Theorem: Let $\sigma$ be a finite signature. A class of finite $\sigma$-structures is definable by a $\Sigma^1_1$ sentence iff it is recognizable in NP.

Applying this to empty $\sigma$, we see that FO spectra are sets of the form $$\{n\in\mathbb N:M_n\in L\},\qquad L\in\mathrm{NP}.$$ Observe that $M_n$ is more-or-less just the unary encoding of $n$ itself. Since conversion from the usual binary representation to unary blows up the input exponentially, it is easy to see that this implies $$S_1=\mathrm{NE}:=\mathrm{NTime}(2^{O(n)}).$$

We can generalize this to higher-order logic, but first we have to decide what exactly is higher-order logic. There are at least two important choices to be made:

1. What things can appear in the signature in $d$-th order logic? In FO, we have just predicates $R(x_1,\dots,x_k)$ where $x_i$ are first-order entities. Such predicates are effectively the same as free second-order variables. There are two obvious ways how to generalize this to $d$-th order logic:

   a) The signature can contain predicates $R(X_1,\dots,X_k)$, where $X_i$ are variables of any type allowed in the logic; that is, order $d$ or lower. This makes $R$ effectively a free variable of order at most $d+1$.

   I will denote spectra for this form of $d$-th order logic $S_d^+$.

   b) The signature can only contain predicates $R(x_1,\dots,x_k)$, where $x_i$ are first-order. That is, it is just an FO signature.

   I will denote spectra for this form of $n$th order logic $S_d^-$.

2. Do the higer-order variables have arbitrary arity, or only unary (monadic)? I will consider the former as default ($S_d^+$, $S_d^-$), and denote the spectra for the latter as $MS_d^+$, $MS_d^-$.

Second, we need an analogue of Fagin’s theorem. The following natural generalization is given in Kołodziejczyk [1]. Let me define the iterated exponential function $2_0^n=n$, $2_{d+1}^n=2^{2_d^n}$.

Theorem: Let $\sigma$ be a finite FO signature, $d\ge2$, and $m,k\ge1$. A set of finite $\sigma$-structures is definable by a $\Sigma^d_m$ sentence (that’s $(d+1)$-th order!) using only higher-order variables of arity $\le k$ if and only if it is recognizable in $\Sigma_m\text{-Time}(2_{d-1}^{O(n^k)})$.

Here, $\Sigma_m\text{-Time}(f(n))$ is the class of languages recognizable by an alternating Turing machine in time $f(n)$ with $m-1$ alternations, starting in an existential state.

The case of $\Sigma^1_m$ is more tricky, but as long as we do not restrict the arity, we still have that $\Sigma^1_m$-definable = recognizable in $\Sigma_m\text{-Time}(2_0^{n^{O(1)}})=\Sigma_m^P$.

By the same argument as when going from Fagin’s theorem to characterization of $S_1$, we obtain:

Theorem: Let $d\ge2$.

• $S_d^+=\mathrm{NTime}(2_d^{O(n)})$

• $S_d^-=\mathrm{AltTime}(O(1),2_{d-1}^{O(n)})$

• $\mathrm{NTime}(2_d^{n+O(1)})\subseteq MS_d^+\subseteq S_d^+=\mathrm{NTime}(2_d^{O(n)})$

• $MS_d^-=\mathrm{AltTime}(O(1),2_{d-1}^{n+O(1)})$ for $d\ge3$; $\mathrm{NE}\cup\mathrm{AltTime}(O(1),O(2^n))\subseteq MS_2^-\subseteq S_2^-=\mathrm{EH}$

• $S_\omega=\mathrm{ELEMENTARY}$, where $S_\omega:=\bigcup_dS_d^+=\bigcup_dS_d^-=\bigcup_dMS_d^+=\bigcup_dMS_d^-$.

Here, $\mathrm{AltTime}(f(n),g(n))$ denotes languages recognizable by an alternating TM with $f(n)$ alternations in time $g(n)$; in particular, $\mathrm{AltTime}(O(1),g(n))=\bigcup_m\Sigma_m\text{-Time}(g(n))$.

An exact characterization of the $MS$ classes gets messy because of the fact that the extra existential quantifiers we get by quantifying away the nonlogical symbols in the sentence do not have bounded arity unlike the rest. However, the above is sufficient for our purposes.

Now, we can answer the questions in turn.

Q1: Using standard variants of the nondeterministic time-hierarchy theorem, we have $$\begin{gather*} S_1\subsetneq S_2^+\subsetneq S_3^+\subsetneq S_4^+\subsetneq\cdots\\ S_1\subsetneq MS_2^+\subsetneq MS_3^+\subsetneq MS_4^+\subsetneq\cdots\\ S_1\subseteq S_2^-\subsetneq S_3^-\subsetneq S_4^-\subsetneq\cdots\\ S_1\subseteq MS_2^-\subsetneq MS_3^-\subsetneq MS_4^-\subsetneq\cdots \end{gather*}$$

The inclusions $S_1\subseteq MS_2^-$ and $S_1\subseteq S_2^-$ are also conjecturally strict. Despite the imprecision in our characterization of $MS_2^-$, the closure properties of $\mathrm{NE}$ ensure $$S_1=MS_2^-\iff S_1=S_2^-\iff \mathrm{NE=EH}.$$ It is generally assumed that $\mathrm{NE\ne EH}$, but as this implies $\mathrm{NP\ne coNP}$, it remains a difficult open problem.

Q2: The classes $S_d^-$ for $d\ge2$, and $MS_d^-$ for $d\ge 3$ are closed under complement. Under unproven complexity-theoretic assumptions, $S_1$, $S_d^+$, and $MS_d^+$ are not closed under complement, but this is at least as hard to prove as $\mathrm{NP\ne coNP}$. The remaining case is $MS_2^-$; based on the asymmetry in its characterization, I’d think this might also not be closed under complement, but I don’t have a generally accepted complexity assumption to support it.

Q3: This depends wildly on how you define $D_n$, however, diagonalization using a natural and reasonably efficient enumeration of sentences should indeed give $D_n\subseteq S_{n+1}$, with appropriate superscripts and modifiers.

Q4: Yes.

Reference:

[1] Leszek A. Kołodziejczyk, Truth definitions in finite models, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200. jstor, preprint