Undecidable iterative propositional calculus

DOI10.1007/S10469-016-9396-3MaRDI QIDQ2364331zbMATH OpenOpenAlexFDO

Authors G. V. Bokov

Publication date 18 July 2017

Published in Algebra and Logic (Search for Journal in Brave)

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

zbMATH Keywords

derivability problemPost's correspondence problemexpressibility problemiterative propositional calculus

Mathematics Subject Classification ID

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

Abstract: In this paper, we consider iterative propositional calculi, which are finite sets of propositional formulas together with the rules of modus ponens and weak substitution (when formula being substituted must be already inferred). We construct an undecidable iterative propositional calculus using axioms in 3 variables. Particulary, we show that the general problem of derivability for these calculi is undecidable.

Recommendations

• Undecidable problems for propositional calculi with implication
• Undecidability of propositional separation logic and its neighbours
• Undecidability and intuitionistic incompleteness
• Undecidability of compass logic
• Undecidable properties of extensions of the logic of provability
• Undecidability of the problem of recognizing axiomatizations for propositional calculi with implication
• Recursive unsolvability of a problem of expressibility in the logic of provability
• Undecidable properties of extensions of provability logic. II
• Undecidability of multiplicative subexponential logic
• A forward unprovability calculus for intuitionistic propositional logic

Cites work

• scientific article; zbMATH DE number 3771592 (Why is no real title available?)
• scientific article; zbMATH DE number 3432342 (Why is no real title available?)
• scientific article; zbMATH DE number 3237823 (Why is no real title available?)
• scientific article; zbMATH DE number 3266622 (Why is no real title available?)
• scientific article; zbMATH DE number 3378895 (Why is no real title available?)
• A mind of a non-countable set of ideas
• A variant of a recursively unsolvable problem
• Address at the Princeton University Bicentennial Conference on Problems of Mathematics (December 17–19, 1946), By Alfred Tarski
• Formal Reductions of the General Combinatorial Decision Problem
• Undecidability of the problem of recognizing axiomatizations for propositional calculi with implication
• Undecidable problems for propositional calculi with implication

Cited in

(9)

• Undecidable goals for completed acyclic programs
• Undecidable problems for propositional calculi with implication
• Undecidability of the problem of recognizing axiomatizations for propositional calculi with implication
• Nondecidable intermediate calculus
• Implication of clauses is undecidable
• Recursive unsolvability of a problem of expressibility in the logic of provability
• Undecidability of the problem of recognizing axiomatizations of superintuitionistic propositional calculi
• Computer Science Logic
• On the number of variables in undecidable superintuitionistic propositional calculi

This page was built for publication: Undecidable iterative propositional calculus

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