No CrossRef data available.
Article contents
On a Propositional Calculus Whose Decision Problem is Recursively Unsolvable1)
Published online by Cambridge University Press: 22 January 2016
Extract
Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.
The purpose of this paper is to present a propositional calculus whose decision problem is recursively unsolvable. The paper is based on the following ideas:
(1) Using Löwenheim-Skolem’s Theorem and Surányi’s Reduction Theorem, we will construct an infinitely many-valued propositional calculus corresponding to the first-order predicate calculus.
(2) It is well known that the decision problem of the first-order predicate calculus is recursively unsolvable.
(3) Thus it will be shown that the decision problem of the infinitely many-valued propositional calculus is recursively unsolvable.
- Type
- Research Article
- Information
- Copyright
- Copyright © Editorial Board of Nagoya Mathematical Journal 1970
References
page 145 note 2) In the first-order predicate calculus, the semantical decision problem is equivalent to the syntactical one by the completeness theorem.
page 146 note 1)
Using those logical operations, we define 
page 147 note 1) Of course, h(F(y)) → ◊ Y F, h(F(z)) → ◊ZF, h(G(y, z)) → ◊(YG1 Λ ZG2), ….
You have
Access