- New
-
Topics
- All Categories
- Metaphysics and Epistemology
- Value Theory
- Science, Logic, and Mathematics
- Science, Logic, and Mathematics
- Logic and Philosophy of Logic
- Philosophy of Biology
- Philosophy of Cognitive Science
- Philosophy of Computing and Information
- Philosophy of Mathematics
- Philosophy of Physical Science
- Philosophy of Social Science
- Philosophy of Probability
- General Philosophy of Science
- Philosophy of Science, Misc
- History of Western Philosophy
- Philosophical Traditions
- Philosophy, Misc
- Other Academic Areas
- Journals
- Submit material
- More
The existential fragment of second-order propositional intuitionistic logic is undecidable
Journal of Applied Non-Classical Logics 34 (1):55-74 (2024)
Abstract
The provability problem in intuitionistic propositional second-order logic with existential quantifier and implication (∃,→) is proved to be undecidable in presence of free type variables (constants). This contrasts with the result that inutitionistic propositional second-order logic with existential quantifier, conjunction and negation is decidable.My notes
Similar books and articles
A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic.Morten H. Sørensen & Paweł Urzyczyn - 2010 - Notre Dame Journal of Formal Logic 51 (4):457-473.
Propositional Quantification in the Monadic Fragment of Intuitionistic Logic.Tomasz Połacik - 1998 - Journal of Symbolic Logic 63 (1):269-300.
The first-order logic of CZF is intuitionistic first-order logic.Robert Passmann - 2024 - Journal of Symbolic Logic 89 (1):308-330.
A secondary semantics for Second Order Intuitionistic Propositional Logic.Mauro Ferrari, Camillo Fiorentini & Guido Fiorino - 2004 - Mathematical Logic Quarterly 50 (2):202-210.
On the complexity of propositional quantification in intuitionistic logic.Philip Kremer - 1997 - Journal of Symbolic Logic 62 (2):529-544.
On the computational content of intuitionistic propositional proofs.Samuel R. Buss & Pavel Pudlák - 2001 - Annals of Pure and Applied Logic 109 (1-2):49-64.
The undecidability of second order linear logic without exponentials.Yves Lafont - 1996 - Journal of Symbolic Logic 61 (2):541-548.
Logics for propositional contingentism.Peter Fritz - 2017 - Review of Symbolic Logic 10 (2):203-236.
Representability in second-order propositional poly-modal logic.G. Aldo Antonelli & Richmond H. Thomason - 2002 - Journal of Symbolic Logic 67 (3):1039-1054.
Undecidability of the Problem of Recognizing Axiomatizations of Superintuitionistic Propositional Calculi.Evgeny Zolin - 2014 - Studia Logica 102 (5):1021-1039.
Another Neighbourhood Semantics for Intuitionistic Logic.Morteza Moniri & Fatemeh Shirmohammadzadeh Maleki - forthcoming - Logic Journal of the IGPL.
Expressivity of second order propositional modal logic.Balder ten Cate - 2006 - Journal of Philosophical Logic 35 (2):209-223.
Analytics
Added to PP
2024-03-08
Downloads
11 (#1,142,538)
6 months
11 (#244,932)
2024-03-08
Downloads
11 (#1,142,538)
6 months
11 (#244,932)
Historical graph of downloads
References found in this work
On 2nd order intuitionistic propositional calculus with full comprehension.Dov M. Gabbay - 1974 - Archive for Mathematical Logic 16 (3-4):177-186.
On second order intuitionistic propositional logic without a universal quantifier.Konrad Zdanowski - 2009 - Journal of Symbolic Logic 74 (1):157-167.
Embedding first order predicate logic in fragments of intuitionistic logic.M. H. Löb - 1976 - Journal of Symbolic Logic 41 (4):705-718.
A simple proof of second-order strong normalization with permutative conversions.Makoto Tatsuta & Grigori Mints - 2005 - Annals of Pure and Applied Logic 136 (1-2):134-155.
PhilPapers logo by Andrea Andrews and Meghan Driscoll.
This site uses cookies and Google Analytics (see our terms & conditions for details regarding the privacy implications). Use of this site is subject to terms & conditions.
All rights reserved by The PhilPapers Foundation
Server: philpapers-web-5ff6c685cb-dmxst uwo