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

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

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

Intuitively, they mimic two well-known descriptions of the analytical hierarchy, one in terms of many-one reducibility and one in terms of second-order definability. I develop an approach to proving that certain structures (which are much weaker than the standard model of Peano arithmetic from the viewpoint of first-order logic) have one or both of these properties. E.g. any $A$ in which the divisibility relation is first-order definable has both properties. The same holds for some other interesting structures, including the standard model of Presburger arithmetic, the natural... more