Undecidability of the problem of recognizing axiomatizations for implicative propositional calculi
Autor: | Bokov, Grigoriy V. |
---|---|
Rok vydání: | 2014 |
Předmět: | |
Zdroj: | Logic Journal of the IGPL (2015) 23 (2): 341-353 |
Druh dokumentu: | Working Paper |
DOI: | 10.1093/jigpal/jzu047 |
Popis: | In this paper we consider propositional calculi, which are finitely axiomatizable extensions of intuitionistic implicational propositional calculus together with the rules of modus ponens and substitution. We give a proof of undecidability of the following problem for these calculi: whether a given finite set of propositional formulas constitutes an adequate axiom system for a fixed propositional calculus. Moreover, we prove the same for the following restriction of this problem: whether a given finite set of theorems of a fixed propositional calculus derives all theorems of this calculus. The proof of these results is based on a reduction of the undecidable halting problem for the tag systems introduced by Post. Comment: 13 pages |
Databáze: | arXiv |
Externí odkaz: |