A note on hereditarily Pi(0)(1)- and Sigma(0)(1)-complete sets of sentences

作者：Speranski Stanislav O^*

来源：Journal of Logic and Computation, 2016, 26(5): 1729-1741.

DOI：10.1093/logcom/exu066

• Elementary definability
• hereditary Pi(0)(1)-completeness
• hereditary Sigma(0)(1)-completeness
• effective inseparability
• hereditary undecidability
• computable inseparability

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 Sigma(0)(1) and Pi(0)(1)-complete sets, in modern terminology. Changing the focus from modelling computations to measuring complexity of theories, the article describes how to obtain Sigma(0)(1)- and Pi(0)(1)- completeness results for a wide range of fragments of theories in a very uniform way, and the reasoning will employ the following concepts. Let s be a first-order signature and Vals the collection of all valid s- sentences. For C is an element of Gamma {Pi(0)(1), Pi(0)(1), call a set Delta of sigma-sentences hereditarily C- complete iff for any C- set Delta, whenever Vals n 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 Sigma(0)(1) and Pi(0)(1)-completeness, with a discussion of various applications.

• 出版日期2016-10