Undecidability of the Logic of Partial Quasiary Predicates

Logic Journal of the IGPL 30 (3):519-533 (2022)
  Copy   BIBTEX

Abstract

We obtain an effective embedding of the classical predicate logic into the logic of partial quasiary predicates. The embedding has the property that an image of a non-theorem of the classical logic is refutable in a model of the logic of partial quasiary predicates that has the same cardinality as the classical countermodel of the non-theorem. Therefore, we also obtain an embedding of the classical predicate logic of finite models into the logic of partial quasiary predicates over finite structures. As a consequence, we prove that the logic of partial quasiary predicates is undecidable—more precisely, $\varSigma ^0_1$-complete—over arbitrary structures and not recursively enumerable—more precisely, $\varPi ^0_1$-complete—over finite structures.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,873

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

About finite predicate logic.Herman Dishkant - 1986 - Studia Logica 45 (4):405 - 414.
The Axiom of Choice in Second‐Order Predicate Logic.Christine Gaßner - 1994 - Mathematical Logic Quarterly 40 (4):533-546.
Two variable first-order logic over ordered domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
Two Variable First-Order Logic Over Ordered Domains.Martin Otto - 2001 - Journal of Symbolic Logic 66 (2):685-702.
Probabilistic Canonical Models for Partial Logics.François Lepage & Charles Morgan - 2003 - Notre Dame Journal of Formal Logic 44 (3):125-138.
On Partial and Paraconsistent Logics.Reinhard Muskens - 1999 - Notre Dame Journal of Formal Logic 40 (3):352-374.
Nice Embedding in Classical Logic.Peter Verdée & Diderik Batens - 2016 - Studia Logica 104 (1):47-78.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.
A Kripkean Approach to Unknowability and Truth.Leon Horsten - 1998 - Notre Dame Journal of Formal Logic 39 (3):389-405.
Ranked partial structures.Timothy J. Carlson - 2003 - Journal of Symbolic Logic 68 (4):1109-1144.
Interpretability over peano arithmetic.Claes Strannegård - 1999 - Journal of Symbolic Logic 64 (4):1407-1425.

Analytics

Added to PP
2021-05-22

Downloads
15 (#971,048)

6 months
6 (#581,938)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

A note on the entscheidungsproblem.Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
Computability and Logic.George S. Boolos, John P. Burgess & Richard C. Jeffrey - 2003 - Bulletin of Symbolic Logic 9 (4):520-521.
Semantical Investigations in Heyting's Intuitionistic Logic.Dov M. Gabbay - 1986 - Journal of Symbolic Logic 51 (3):824-824.
``A Note on the Entcheidunsproblem".Alonzo Church - 1936 - Journal of Symbolic Logic 1 (1):40-41.
The Undecidability of Monadic Modal Quantification Theory.Saul A. Kripke - 1962 - Mathematical Logic Quarterly 8 (2):113-116.

View all 15 references / Add more references