We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
A note on hereditarily Π<sup>0</sup><sub>1</sub>- and Σ<sup>0</sup><sub>1</sub>-complete sets of sentences.
- Authors
SPERANSKI, STANISLAV O.
- 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 Σ01Σ01- and Π01Π01-complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the article describes how to obtain Σ01Σ01- and Π01Π01-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σValσ the collection of all valid σσ-sentences. For C∈{Π01,Σ01}C∈{Π01,Σ01}, call a set ΓΓ of σσ-sentences hereditarily CC-complete iff for any CC-set ΔΔ, whenever Valσ∩Γ⊆Δ⊆ΓValσ∩Γ⊆Δ⊆Γ, then ΔΔ is CC-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 Π01Π01- and Σ01Σ01-completeness, with a discussion of various applications.
- Subjects
COMPUTATIONAL complexity; ARITHMETIC; COMPLETENESS theorem; MODEL theory; DEFINABILITY theory (Mathematical logic); MATHEMATICAL logic
- Publication
Journal of Logic & Computation, 2016, Vol 26, Issue 5, p1729
- ISSN
0955-792X
- Publication type
Article
- DOI
10.1093/logcom/exu066