Abstract: Let σ be a signature and A a σ-structure with domain N. Say that a monadic second-order σ-formula is Πn1 iff it has the form
with X1,…,Xn set variables and ψ containing no set quantifiers. Consider the following properties:
ACPfor each positive integer n, the set of Πn1-σ-sentences true in A is Πn1-complete;ADPfor each positive integer n, if a set of natural numbers is Πn1-definable (i.e. by a Πn1-formula) in the standard model of arithmetic and closed under automorphisms of A, then it is Πn1-definable in A.
We use ∣ and ⊥ to denote the divisibility relation and the coprimeness relation respectively. Given a prime p, let bcp be the function which maps every pair (x,y) of natural numbers into x+yxmodp. In this article we prove: ⟨N,∣⟩ and all ⟨N,bcp,=⟩ have both ACP and ADP; in effect, even ⟨N,⊥⟩ has ACP. Notice – these results readily generalise to arbitrary arithmetical expansions of the corresponding structures, provided that the extended signature is finite.