A+ CATEGORY SCIENTIFIC UNIT

Automorphisms of models of bounded arithmetic

Volume 192 / 2006

Ali Enayat Fundamenta Mathematicae 192 (2006), 37-65 MSC: Primary 03F30, 03C62, 03H15; Secondary 03C15, 20B27. DOI: 10.4064/fm192-1-3

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}$;

(b) $\mathfrak{M}=I_{{\rm fix}}(j)$ for some nontrivial automorphism $j$ of an end extension $\mathfrak{N}$ of $\mathfrak{M}$ that satisfies $I\Delta_{0}.$

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}$.

Here $\mathop{\rm Aut}\nolimits(X)$ is the group of automorphisms of the structure $X$, and $\mathbb{Q}$ is the ordered set of rationals.

Authors

  • Ali EnayatDepartment of Mathematics and Statistics
    American University
    4400 Mass. Ave. N.W.
    Washington, DC 20016-8050, U.S.A.
    e-mail

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image