March 9, 2015Stanislav 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.