arnold beckmann's pages

Preservation theorems and restricted consistency statements in bounded arithmetic

File: PDF-File

Author: Arnold Beckmann
Title: Preservation theorems and restricted consistency statements in bounded arithmetic
Journal: Ann.Pure.Appl.Logic 2004, 126: 255-280
Proceedings of the Tarski Conference in Warsaw, May 28 - June 1, 2001
DOI: 10.1016/j.apal.2003.11.003

Abstract: In this article we prove preservation theorems for theories of bounded arithmetic. The following one is well-known: The ∀Π b 1 - separation of bounded arithmetic theories S i 2 from T j 2 (1 ≤ i ≤ j) is equivalent to the existence of a model of S i 2 which does not have a Δ b 0 - elementary extension to a model of T j 2 .
Let
Ω1nst denote that there is a nonstandard element c such that the function n→2log(n)c is a total function.
Let
BLΣ b 1 be the bounded collection schema ∀x≤|t| ∃y φ(x,y) → ∃z ∀x≤|t| ∃y≤z φ(x,y) for φ ∈ Σ b 1 .

Main Theorem. The
∀Π b 1 - separation of S i 2 from T j 2 (1 ≤ i ≤ j) is equivalent to the existence of
  1. a model of S i 2 + Ω1nst which is 1b - closed w.r.t. T j 2 ,
  2. a countable model of S i 2 + BLΣ b 1 without weak end extensions to models of T j 2 .
These results still hold when the theories are extended by finitely many ∃ ∀ (Σ b i ∪ Π b i ) - sentences.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!