Publishing house / Journals and Serials / Fundamenta Mathematicae / All issues

Abstract

We establish the following model-theoretic characterization of the fragment $I\Delta_{0}+\mathop{\rm Exp}+B\Sigma_{1}$ of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment $I\Delta_{0}$ of Peano arithmetic with induction limited to $\Delta_{0}$-formulae).

Theorem A. The following two conditions are equivalent for a countable model $\mathfrak{M}$ of the language of arithmetic:

(a) $\mathfrak{M}$ satisfies $I\Delta_{0}+B\Sigma _{1}+\mathop{\rm Exp}$;

Here $I_{{\rm fix}}(j)$ is the largest initial segment of the domain of $j$ that is pointwise fixed by $j$, $\mathop{\rm Exp}$ is the axiom asserting the totality of the exponential function, and $B\Sigma_{1}$ is the $\Sigma_{1}$-collection scheme consisting of the universal closure of formulae of the form $$ [\forall x< a\ \exists y\ \varphi (x,y)]\rightarrow [\exists z\ \forall x< a\ \exists y< z\ \varphi (x,y)], $$ where $\varphi $ is a $\Delta_{0}$-formula. Theorem A was inspired by a theorem of Smoryński, but the method of proof of Theorem A is quite different and yields the following strengthening of Smoryński's result:

Theorem B. Suppose $\mathfrak{M}$ is a countable recursively saturated model of\/ {\rm PA} and $I$ is a proper initial segment of $\mathfrak{M}$ that is closed under exponentiation. There is a group embedding $j\mapsto \widehat{j}$ from $\mathop{\rm Aut}\nolimits(\mathbb{Q})$ into $\mathop{\rm Aut}\nolimits(\mathfrak{M})$ such that $I=I_{{\rm fix}}(\widehat{j})$ for every nontrivial $j\in \mathop{\rm Aut}\nolimits(\mathbb{Q}).$ Moreover, if $j$ is fixed point free, then the fixed point set of $\widehat{j}$ is isomorphic to $\mathfrak{M}$.