A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic
Notre Dame Journal of Formal Logic 51 (4):457-473 (2010)
| Abstract | We give a syntactic translation from first-order intuitionistic predicate logic into second-order intuitionistic propositional logic IPC2. The translation covers the full set of logical connectives ∧, ∨, →, ⊥, ∀, and ∃, extending our previous work, which studied the significantly simpler case of the universal-implicational fragment of predicate logic. As corollaries of our approach, we obtain simple proofs of nondefinability of ∃ from the propositional connectives and nondefinability of ∀ from ∃ in the second-order intuitionistic propositional logic. We also show that the ∀-free fragment of IPC2 is undecidable | |||||||||
| Keywords | No keywords specified (fix it) | |||||||||
| Categories | ||||||||||
| Options |
|
|||||||||
Download options| PhilPapers Archive |
Upload a copy of this paper Check publisher's policy on self-archival Papers currently archived: 5,679 |
| External links |
  Try with proxy. |
| Through your library | Configure |
Similar books and articlesA. S. Troelstra (1981). On a Second Order Propositional Operator in Intuitionistic Logic. Studia Logica 40 (2):113 - 139.
Philip Kremer (1997). On the Complexity of Propositional Quantification in Intuitionistic Logic. Journal of Symbolic Logic 62 (2):529-544.
Nobu-Yuki Suzuki (1995). Constructing a Continuum of Predicate Extensions of Each Intermediate Propositional Logic. Studia Logica 54 (2):173 - 198.
Ernst Zimmermann (2002). A Predicate Logical Extension of a Subintuitionistic Propositional Logic. Studia Logica 72 (3):401-410.
Peter W. O'Hearn & David J. Pym (1999). The Logic of Bunched Implications. Bulletin of Symbolic Logic 5 (2):215-244.
Greg Restall (2005). Logic: An Introduction. Routledge.
Tomasz Połacik (1998). Propositional Quantification in the Monadic Fragment of Intuitionistic Logic. Journal of Symbolic Logic 63 (1):269-300.
Mitsunori Kobayashi & Arata Ishimoto (1982). A Propositional Fragment of Leśniewski's Ontology and its Formulation by the Tableau Method. Studia Logica 41 (2-3):181 - 195.
D. C. McCarty (1996). Undecidability and Intuitionistic Incompleteness. Journal of Philosophical Logic 25 (5):559 - 565.
G. Aldo Antonelli & Richmond H. Thomason (2002). Representability in Second-Order Propositional Poly-Modal Logic. Journal of Symbolic Logic 67 (3):1039-1054.
Tomasz Połacik (1994). Second Order Propositional Operators Over Cantor Space. Studia Logica 53 (1):93 - 105.
Fernando Ferreira (2006). Comments on Predicative Logic. Journal of Philosophical Logic 35 (1):1 - 8.
M. H. Löb (1976). Embedding First Order Predicate Logic in Fragments of Intuitionistic Logic. Journal of Symbolic Logic 41 (4):705-718.
Aldo Ursini (1979). A Modal Calculus Analogous to K4w, Based on Intuitionistic Propositional Logic, Iℴ. Studia Logica 38 (3):297 - 311.
Balder ten Cate (2006). Expressivity of Second Order Propositional Modal Logic. Journal of Philosophical Logic 35 (2):209 - 223.
Analytics
Monthly downloads |
Added to index2010-09-30Total downloads12 ( #93,386 of 549,087 )Recent downloads (6 months)1 ( #63,317 of 549,087 )How can I increase my downloads? |
My notes
Discussion
