Some new definability and complexity results in monadic second-order arithmetic

March 9, 2015

Stanislav Speranski (Laboratory of Logical Systems, Sobolev Institute of Mathematics)

Let $ A $ be a structure with domain the natural numbers. Consider the following properties:

— for every positive natural number $ n $, the set of $Pi^1_n$-sentences true in $ A $ is $Pi^1_n$-complete;

— for every positive natural number $ n $, if a set $ X $ of natural numbers is $Pi^1_n$-definable in the standard model of arithmetic and closed under automorphisms of $ A $, then it is $Pi^1_n$-definable in $ A $.

I prove that the natural numbers with the coprimeness relation and all Pascal’s triangles modulo a prime have both properties. In effect, the proofs provide a method which can be used in other situations. E.g. the same holds for the natural numbers with the divisibility relation.