TY - JOUR

T1 - A note on hereditarily $\Pi^0_1$- and $\Sigma^0_1$-complete sets of sentences

AU - Speranski, Stanislav O.

PY - 2016

Y1 - 2016

N2 - 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 paper 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 $\sigma$ be a first-order signature and ${Val}_{\sigma}$ the collection of all valid $\sigma$-sentences. For $\mathrm{C} \in \left\{ \Pi^0_1, \Sigma^0_1 \right\}$, call a set $\Gamma$ of $\sigma$-sentences hereditarily $\mathrm{C}$-complete iff for any $\mathrm{C}$-set $\Delta$, whenever ${Val}_{\sigma} \cap \Gamma \subseteq \Delta \subseteq \Gamma$, then $\Delta$ is $\mathrm{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 paper presents major tools and main examples in the study of hereditary $\Pi^0_1$- and $\Sigma^0_1$-completeness, with a discussion of various applications.

AB - 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 paper 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 $\sigma$ be a first-order signature and ${Val}_{\sigma}$ the collection of all valid $\sigma$-sentences. For $\mathrm{C} \in \left\{ \Pi^0_1, \Sigma^0_1 \right\}$, call a set $\Gamma$ of $\sigma$-sentences hereditarily $\mathrm{C}$-complete iff for any $\mathrm{C}$-set $\Delta$, whenever ${Val}_{\sigma} \cap \Gamma \subseteq \Delta \subseteq \Gamma$, then $\Delta$ is $\mathrm{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 paper presents major tools and main examples in the study of hereditary $\Pi^0_1$- and $\Sigma^0_1$-completeness, with a discussion of various applications.

KW - elementary definability

KW - hereditary $\Pi^0_1$-completeness

KW - hereditary $\Sigma^0_1$-completeness

KW - effective inseparability

KW - hereditary undecidability

KW - computable inseparability

KW - elementary definability

KW - hereditary $\Pi^0_1$-completeness

KW - hereditary $\Sigma^0_1$-completeness

KW - effective inseparability

KW - hereditary undecidability

KW - computable inseparability

U2 - 10.1093/logcom/exu066

DO - 10.1093/logcom/exu066

M3 - Article

VL - 26

SP - 1729

EP - 1741

JO - Journal of Logic and Computation

JF - Journal of Logic and Computation

SN - 0955-792X

IS - 5

ER -