One Henkin Quantifier in the Empty Vocabulary Suffices for Undecidability

Issue title: Bridging Logic, Philosophy, Computer and Cognitive Science: in the Memory of Marcin Mostowski (1955-2017)

Guest editors: Nina Gierasimczuka and Jakub Szymanikb

Article type: Research Article

Authors: Zdanowski, Konrad^{; *}

Correspondence: [*] Address for correspondence: Cardinal Stefan Wyszynski University, Faculty of Mathematics and Natural Sciences, Warsaw, Poland

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. We estimate the size of such quantifiers proving undecidability of L0(H12) and L0(E10).

Keywords: Henkin quantifiers, undecidability, word problem

DOI: 10.3233/FI-2019-1774

Journal: Fundamenta Informaticae, vol. 164, no. 4, pp. 375-386, 2019