Some new results in monadic second-order arithmetic
Stanislav Olegovich Speranski · Computability · 2015
Abstract Let σ be a signature and [Formula: see text] a σ-structure with domain [Formula: see text]. Say that a monadic second-order σ-formula is [Formula: see text] iff it has the form [Formula: see text] with [Formula: see text] set variables and ψ containing no set quantifiers. Consider the following properties: for each positive integer n, the set of [Formula: see text]- σ-sentences true in [Formula: see text] is [Formula: see text]-complete; for each positive integer n, if a set of natural numbers is [Formula: see text]-definable (i.e. by a [Formula: see text]-formula) in the standard model of arithmetic and closed under automorphisms of [Formula: see text], then it is [Formula: see text]-definable in [Formula: see text]. We use ∣ and ⊥ to denote the divisibility relation and the coprimeness relation respectively. Given a prime p, let [Formula: see text] be the function which maps every pair [Formula: see text] of natural numbers into [Formula: see text]. In this article we prove: [Formula: see text] and all [Formula: see text] have both [Formula: see text] and [Formula: see text]; in effect, even [Formula: see text] has [Formula: see text]. Notice – these results readily generalise to arbitrary arithmetical expansions of the corresponding structures, provided that the extended signature is finite.