Automorphisms of models of bounded arithmetic

Ali Enayat

Fundamenta Mathematicae, Tome 189 (2006), p. 37-65 / Harvested from The Polish Digital Mathematics Library

Résumé

We establish the following model-theoretic characterization of the fragment IΔ₀ + Exp + BΣ₁ of Peano arithmetic in terms of fixed points of automorphisms of models of bounded arithmetic (the fragment IΔ₀ of Peano arithmetic with induction limited to Δ₀-formulae). Theorem A. The following two conditions are equivalent for a countable model of the language of arithmetic: (a) satisfies IΔ₀ + BΣ₁ + Exp; (b) $ = I_{fix}(j)$ for some nontrivial automorphism j of an end extension of that satisfies IΔ₀. Here $I_{fix}(j)$ is the largest initial segment of the domain of j that is pointwise fixed by j, Exp is the axiom asserting the totality of the exponential function, and BΣ₁ is the Σ₁-collection scheme consisting of the universal closure of formulae of the form [∀x < a ∃y φ(x,y)] → [∃z ∀x < a ∃y < z φ (x,y)], where φ is a Δ₀-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 is a countable recursively saturated model of PA and I is a proper initial segment of that is closed under exponentiation. There is a group embedding j ↦ ĵ from Aut(ℚ) into Aut( ) such that $I = I_{fix}(ĵ)$ for every nontrivial j ∈ Aut(ℚ). Moreover, if j is fixed point free, then the fixed point set of ĵ is isomorphic to . Here Aut(X) is the group of automorphisms of the structure X, and ℚ is the ordered set of rationals.

Détail

Publié le : 2006-01-01

Zbl 1115.03036

EUDML-ID : urn:eudml:doc:282846