Undecidable problems for propositional calculi with implication

DOI10.1093/JIGPAL/JZW013MaRDI QIDQ4644571zbMATH OpenOpenAlexFDO

Authors G. V. Bokov

Publication date 8 January 2019

Published in Logic Journal of the IGPL (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1502.00978

zbMATH Keywords

decision problemspropositional calculusimplicational calculustag system

Mathematics Subject Classification ID

Classical propositional logic (03B05) Decidability of theories and sets of sentences (03B25)

Abstract: In this article, we deal with propositional calculi over a signature containing the classical implication $o$ with the rules of modus ponens and substitution. For these calculi we consider few recognizing problems such as recognizing derivations, extensions, completeness, and axiomatizations. The main result of this paper is to prove that the problem of recognizing extensions is undecidable for every propositional calculus, and the problems of recognizing axiomatizations and completeness are undecidable for propositional calculi containing the formula $xo(yox)$. As a corollary, the problem of derivability of a fixed formula $A$ is also undecidable for all $A$. Moreover, we give a historical survey of related results.

Recommendations

• Undecidability of the problem of recognizing axiomatizations for propositional calculi with implication
• Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
• Undecidable iterative propositional calculus
• The undecidability of the disjunction property of propositional logics and other related problems
• On the number of variables in undecidable superintuitionistic propositional calculi

Cited in

(14)

• Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
• Recursive unsolvability of a problem of expressibility in the logic of provability
• scientific article; zbMATH DE number 1180151 (Why is no real title available?)
• Implication of clauses is undecidable
• The metatheory of the classical propositional calculus is not axiomatizable
• Undecidable properties of extensions of the logic of provability
• The undecidability of propositional adaptive logic
• scientific article; zbMATH DE number 3849196 (Why is no real title available?)
• Undecidable iterative propositional calculus
• On the number of variables in undecidable superintuitionistic propositional calculi
• Lower end of the linial-post spectrum
• Nondecidable intermediate calculus
• The undecidability of entailment and relevant implication
• Undecidability of the problem of recognizing axiomatizations for propositional calculi with implication

This page was built for publication: Undecidable problems for propositional calculi with implication

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4644571)