A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic
Sørensen, Morten H. ; Urzyczyn, Paweł
Notre Dame J. Formal Logic, Tome 51 (2010) no. 1, p. 457-473 / Harvested from Project Euclid
Text on Project Euclid
PDF
Alt PDF
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.
Publié le : 2010-10-15
Classification:  propositional quantification,  IPC2,  03B20,  03F03 
@article{1285765799,
     author = {S\o rensen, Morten H. and Urzyczyn, Pawe\l },
     title = {A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic},
     journal = {Notre Dame J. Formal Logic},
     volume = {51},
     number = {1},
     year = {2010},
     pages = { 457-473},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1285765799}
}

Sørensen, Morten H.; Urzyczyn, Paweł. A Syntactic Embedding of Predicate Logic into Second-Order Propositional Logic. Notre Dame J. Formal Logic, Tome 51 (2010) no. 1, pp.  457-473. http://gdmltest.u-ga.fr/item/1285765799/