Abstract

Many important achievements of formal logic have been concerned with the discovery of incomputability—and thus firmly rooted in the undecidability of the halting problem and its complement. Also, the latter produce influental examples of Σ10 - and Π10 -complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the article describes how to obtain Σ10 - and Π10 -completeness results for a wide range of fragments of theories in a very uniform way, and the reasoning will employ the following concepts. Let σ be a first-order signature and Valσ the collection of all valid σ -sentences. For C{Π10,Σ10} , call a set Γ of σ -sentences hereditarilyC-complete iff for any C -set Δ , whenever ValσΓΔΓ , then Δ is C -complete. Both notions are closely connected with that of being hereditarily undecidable, but unlike their common predecessor, serve the purpose of getting computational complexity results, via employing the two most fundamental levels of the arithmetical hierarchy. This article presents major tools and main examples in the study of hereditary Π10 - and Σ10 -completeness, with a discussion of various applications.

This content is only available as a PDF.
You do not currently have access to this article.