Some new results in monadic second-order arithmetic

Article type: Research Article

Authors: Speranski, Stanislav O.

Affiliations: Sobolev Institute of Mathematics, Novosibirsk, Russia. katze.tail@gmail.com. http://math.nsc.ru/~speranski/

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 ∀X1∃X2∀X3…Xnψ 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.

Keywords: Monadic second-order arithmetic, complexity, definability

DOI: 10.3233/COM-150036

Journal: Computability, vol. 4, no. 2, pp. 159-174, 2015