Is Presburger arithmetic in stronger logics still complete?

Question

Originally asked at MSE:

Let $\Sigma=\{+,<,0,1\}$ be the usual language of Presburger arithmetic. Given a "reasonable" logic $\mathcal{L}$, let $\mathbb{Pres}(\mathcal{L})$ be the $\mathcal{L}$-theory consisting of

• Axioms 1-4 of the usual presentation of Presburger arithmetic, and

• for each $\mathcal{L}[\Sigma]$-formula $\varphi(x,\overline{y})$, the $\mathcal{L}[\Sigma]$-sentence $$\forall \overline{y}[\varphi(0,\overline{y})\wedge\forall x(\varphi(x,\overline{y})\rightarrow\varphi(x+1,\overline{y}))\implies \forall x\varphi(x,\overline{y})].$$

For example, $\mathbb{Pres}(\mathsf{SOL})$ is fully categorical. $\mathbb{Pres}(\mathsf{FOL})$ (= usual Presburger arithmetic) is not fully categorical of course, but it is complete as an $\mathsf{FOL}$-theory: for each first-order sentence $\theta$ in the language $\Sigma$, either $\mathbb{Pres}(\mathsf{FOL})\models\theta$ or $\mathbb{Pres}(\mathsf{FOL})\models\neg\theta$.

I'm curious about whether there is a "natural" logic $\mathcal{L}$ such that $\mathbb{Pres}(\mathcal{L})$ is incomplete as an $\mathcal{L}$-theory. There are a couple natural candidates coming from a similarly-flavored analogue of this question for PA, and I think the simplest is "Ramsey logic," that is, first-order logic equipped with the Ramsey/Magidor-Malitz quantifiers (see e.g. this answer of Enayat):

Let $\mathcal{R}$ be first-order logic augmented by each Ramsey quantifier $Q^n$. Is $\mathbb{Pres}(\mathcal{R})$ complete as an $\mathcal{R}$-theory? That is, is it the case that, for every $\mathcal{R}[\Sigma]$-sentence $\theta$, either $\mathbb{Pres}(\mathcal{R})\models\theta$ or $\mathbb{Pres}(\mathcal{R})\models\neg\theta$?

Answer 1

The following theorem of Schmerl and Simpson gives a positive answer to the question; i.e., it shows that $\mathbb{Pres}(\mathcal{R})$ is complete as an $\mathcal{R}$-theory.

In what follows $\mathsf{PrA}$ denotes Presburger Arithmetic (formulated in first order logic).

Theorem. (Schmerl and Simpson) Given a formula $\theta$ in the language of $\mathsf{PrA}$ with Ramsey quantifiers, we can effectively find a first order formula $\psi$ in the language of $\mathsf{PrA}$, such that $\theta$ and $\psi$ are equivalent in all models of $\mathsf{PrA}$.

The above appears as Theorem 4.1 of the following paper:

J. Schmerl and S. Simpson, On the role of Ramsey quantifiers in first order arithmetic, Journal of Symbolic Logic, Vol.47, 1982.

The interaction of Ramsey quantifiers and Presburger Arithmetic also has "practical applications", as indicated by this recent paper. Note that the paper refers to Presburger Arithmetic as "Linear Integer Arithmetic", the latter refers to the first order theory of $(\mathbb{Z}, +, \leq, 0, 1)$.