Hostname: page-component-7b7567c8c-z4zkx Total loading time: 0 Render date: 2026-11-17T05:05:19.424Z Has data issue: false hasContentIssue false

END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS

Published online by Cambridge University Press:  19 July 2016

LESZEK ALEKSANDER KOŁODZIEJCZYK*
Affiliation:
INSTITUTE OF MATHEMATICS UNIVERSITY OF WARSAW BANACHA 2, 02-097 WARSZAWA POLAND E-mail: lak@mimuw.edu.pl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We prove that if the linear-time and polynomial-time hierarchies coincide, then every model of Π1(ℕ) + ¬Ω1 has a proper end-extension to a model of Π1(ℕ), and so Π1(ℕ) + ¬Ω ⊢ BΣ1. Under an even stronger complexity-theoretic assumption which nevertheless seems hard to disprove using present-day methods, Π1(ℕ) + ¬Exp ⊢ BΣ1. Both assumptions can be modified to versions which make it possible to replace Π1(ℕ) by IΔ0 as the base theory.

We also show that any proof that IΔ0 + ¬Exp does not prove a given finite fragment of BΣ1 has to be “nonrelativizing”, in the sense that it will not work in the presence of an arbitrary oracle.

Information

Type
Articles
Copyright
Copyright © The Association for Symbolic Logic 2016