Some new results in monadic second-order arithmetic

Abstract

Abstract

Let σ be a signature and $\mathfrak{A}$ a σ-structure with domain $\mathbb{N}$ . Say that a monadic second-order σ-formula is ${\mathrm{\Pi }}_{\mathit{n}}^1$ iff it has the form $$\forall {\mathit{X}}_1\exists {\mathit{X}}_2\forall {\mathit{X}}_3\dots {\mathit{X}}_{\mathit{n}}\mathit{\psi }$$ with ${\mathit{X}}_1\mathrm{,}\dots \mathrm{,}{\mathit{X}}_{\mathit{n}}$ set variables and ψ containing no set quantifiers. Consider the following properties:

for each positive integer n, the set of ${\mathrm{\Pi }}_{\mathit{n}}^1$ -σ-sentences true in $\mathfrak{A}$ is ${\mathrm{\Pi }}_{\mathit{n}}^1$ -complete;

for each positive integer n, if a set of natural numbers is ${\mathrm{\Pi }}_{\mathit{n}}^1$ -definable (i.e. by a ${\mathrm{\Pi }}_{\mathit{n}}^1$ -formula) in the standard model of arithmetic and closed under automorphisms of $\mathfrak{A}$ , then it is ${\mathrm{\Pi }}_{\mathit{n}}^1$ -definable in $\mathfrak{A}$ .

We use ∣ and ⊥ to denote the divisibility relation and the coprimeness relation respectively. Given a prime p, let ${\mathsf{bc}}_{\mathit{p}}$ be the function which maps every pair $\mathrm{(}\mathit{x}\mathrm{,}\mathit{y}\mathrm{)}$ of natural numbers into $\left(\genfrac{}{}{0.0pt}{}{\mathit{x}+\mathit{y}}{\mathit{x}}\right)\mathsf{mod}\mathit{p}$ . In this article we prove: $⟨\mathbb{N}\mathrm{,}\mid ⟩$ and all $⟨\mathbb{N}\mathrm{,}{\mathsf{bc}}_{\mathit{p}}\mathrm{,}=⟩$ have both $\mathtt{ACP}$ and $\mathtt{ADP}$ ; in effect, even $⟨\mathbb{N}\mathrm{,}\perp ⟩$ has $\mathtt{ACP}$ . Notice – these results readily generalise to arbitrary arithmetical expansions of the corresponding structures, provided that the extended signature is finite.