The undecidability of propositional adaptive logic

Leon Horsten

Philip Welch

pp. 41-60

in: Synthese 158 (1), 2007.

Abstract

We investigate and classify the notion of final derivability of two basic inconsistency-adaptive logics. Specifically, the maximal complexity of the set of final consequences of decidable sets of premises formulated in the language of propositional logic is described. Our results show that taking the consequences of a decidable propositional theory is a complicated operation. The set of final consequences according to either the Reliability Calculus or the Minimal Abnormality Calculus of a decidable propositional premise set is in general undecidable, and can be (Sigma^0_3)-complete. These classifications are exact. For first order theories even finite sets of premises can generate such consequence sets in either calculus.