Article contents
The decidability of dependency in intuitionistic propositional logic
Published online by Cambridge University Press: 12 March 2014
Abstract
A definition is given for formulae A1, …, An in some theory T which is formalized in a propositional calculus S to be (in)dependent with respect to S. It is shown that, for intuitionistic propositional logic IPC, dependency (with respect to IPC itself) is decidable. This is an almost immediate consequence of Pitts’ uniform interpolation theorem for IPC. A reasonably simple infinite sequence of IPC-formulae Fn (p, q) is given such that IPC-formulae A and B are dependent if and only if at least on of the Fn (A, B) is provable.
- Type
- Research Article
- Information
- Copyright
- Copyright © Association for Symbolic Logic 1995
References
REFERENCES
- 9
- Cited by