Undecidable problems for propositional calculi with implication

DOI10.1093/JIGPAL/JZW013zbMATH Open1405.03031arXiv1502.00978OpenAlexW3106203864MaRDI QIDQ4644571FDOQ4644571

G. V. Bokov

Publication date: 8 January 2019

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

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.

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

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

zbMATH Keywords

decision problemspropositional calculusimplicational calculustag system

Mathematics Subject Classification ID

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

Cited In (11)

• Recursive unsolvability of a problem of expressibility in the logic of provability
• Title not available (Why is that?)
• The metatheory of the classical propositional calculus is not axiomatizable
• Implication of clauses is undecidable
• Title not available (Why is that?)
• The undecidability of propositional adaptive logic
• Undecidable properties of extensions of the logic of provability
• Title not available (Why is that?)
• Undecidable iterative propositional calculus
• Nondecidable intermediate calculus
• The undecidability of entailment and relevant 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)