One Henkin Quantifier in the empty vocabulary suffices for undecidability

2016/12/21 by Konrad Zdanowski, Zdanowski, Konrad
Mathematics · #03B25 #FOS: Mathematics #Logic (math.LO) #math.LO #msc:03B25

paper · pdf · doi:10.48550/arxiv.1612.07154

arxiv created 2016/12/21 · arxiv updated 2016/12/22

Abstract

We prove that there are single Henkin quantifiers such that first order logic augmented by one of these quantifiers is undecidable in the empty vocabulary. Examples of such quantifiers are given.

Related

• Implicitly definable generalized quantifiers
• Monadic Second-Order Logic with Path-Measure Quantifier is Undecidable
• The Universal Fragment of Presburger Arithmetic with Unary Uninterpreted Predicates is Undecidable
• Undecidability in First-Order Theories of Term Algebras Extended with a Substitution Operator
• A Simplest Undecidable Modal Logic