One Henkin Quantifier in the Empty Vocabulary Suffices for Undecidability

• Autorzy: Zdanowski Konrad

Identyfikatory

DOI

10.3233/FI-2019-1774

• Języki publikacji: EN

Abstrakty

EN

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 L_ø(H₁₂) and L_ø(E₁₀).

Słowa kluczowe

EN

Henkin quantifiers; undecidability; word problem

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2019
• Tom: Vol. 164, nr 4
• Strony: 375--386
• Opis fizyczny: Bibliogr. 16 poz.

Twórcy

autor

Zdanowski Konrad

• Cardinal Stefan Wyszynski University, Faculty of Mathematics and Natural Sciences, Warsaw, Poland

Bibliografia

• [1] Blass A, Gurevich Y. Henkin quantifiers and complete problems, Annals of Pure and Applied Logic, 1986;32:1-16. URL https://doi.org/10.1016/0168-0072(86)90040-0.
• [2] Ceitin G. Associative calculus with insoluble equivalence problem, Dokl. Akad. Nauk SSSR (N.S.), 1956;107:370-371, In Russian.
• [3] Enderton HB. Finite Partially-Ordered Quantifiers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1970;16:393-397. URL https://doi.org/10.1002/malq.19700160802.
• [4] Gierasimczuk N, Szymanik J. Branching Quantification v. Two-way Quantification, Journal of Semantics, 2009;26(4):367-392. URL https://doi.org/10.1093/jos/ffp008.
• [5] Gurevich Y. The word problem for certain classes of semigroups, Algebra and Logic, 1966;5(2):25-35.
• [6] Gurevich Y, Lewis HR. The word problem for cancellation semigroups with zero, Journal of Symbolic Logic, 1984;49(1):184-191. doi:10.2307/2274101.
• [7] Kołodziejczyk LA. The expressive power of Henkin quantifiers with dualization, Semantic Scholar 2002. https://pdfs.semanticscholar.org/4826/d35d0ca99beec09e5b2618312f00fc2b6a9a.pdf.
• [8] Krynicki M, Lachlan AH. On the semantics of the Henkin quantifier, Journal of Symbolic Logic, 1979;44(2):184-200. URL https://doi.org/10.2307/2273726.
• [9] Krynicki M, Mostowski M. Decidability problems in language with Henkin quantifiers, Annals of Pure and Applied Logic, 58, 1992, 149-172.
• [10] Matiyasevich Y. Simple examples of unsolvable associative calculi, Dokl. Akad. Nauk SSSR, 173, 1967, 1264-1266, In Russian.
• [11] Mikhalev AV, Pilz GF, Eds. The concise handbook of algebra, Springer, 2002.
• [12] Mostowski M. Pure logic with branched quantifiers, Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 35, 1989, 45-48.
• [13] Mostowski M. Arithmetic with the Henkin quantifier and its generalizations, 1991, 1-25.
• [14] Mostowski M, Zdanowski K. Henkin Quantifiers in Finite Models, In preparation.
• [15] Mostowski M, Zdanowski K. Degrees of Logics with Henkin Quantifiers in poor Vocabularies, Archive for Mathmetical Logic, 2004, 691-702.
• [16] Walkoe WJ. Finite partially-ordered quantification, Journal of Symbolic Logic, 35, 1970, 535-555.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).