-
Views
-
Cite
Cite
Stanislav O. Speranski, A note on hereditarily - and -complete sets of sentences , Journal of Logic and Computation, Volume 26, Issue 5, October 2016, Pages 1729–1741, https://doi.org/10.1093/logcom/exu066
- Share Icon Share
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 - and -complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the article describes how to obtain - and -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 the collection of all valid -sentences. For , call a set of -sentences hereditarily-complete iff for any -set , whenever , then is -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 - and -completeness, with a discussion of various applications.