Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-18T06:29:49.584Z Has data issue: false hasContentIssue false

Double-exponential inseparability of Robinson subsystem Q+

Published online by Cambridge University Press:  12 March 2014

Lavinia Egidi
Affiliation:
Dipartimento di Informatica, Università del Piemonte Orientale “A. Avogadro”, Viale T. Michel, 11, 15121 Alessandria, Italy, E-mail: lavinia.egidi@mfn.unipmn.it
Giovanni Faglia
Affiliation:
Dipartimento di Informatica, Università del Piemonte Orientale “A. Avogadro”, Viale T. Michel, 11, 15121 Alessandria, Italy, E-mail: giovanni.faglia@gmail.com

Abstract

In this work a double exponential time inseparability result is proven for a finitely axiomatizable first order theory Q+. The theory, subset of Presburger theory of addition S+, is the additive fragment of Robinson system Q. We prove that every set that separates Q+ from the logically false sentences of addition is not recognizable by any Turing machine working in double exponential time. The lower bound is given both in the non-deterministic and in the linear alternating time models.

The result implies also that any theory of addition that is consistent with Q+—in particular any theory contained in S+—is at least double exponential time difficult. Our inseparability result is an improvement on the known lower bounds for arithmetic theories.

Our proof uses a refinement and adaptation of the technique that Fischer and Rabin used to prove the difficulty of S+. Our version of the technique can be applied to any incomplete finitely axiomatizable system in which all of the necessary properties of addition are provable.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable