Some Properties of Logics with Henkin Quantifiers in Poor Vocabularies

Marcin Mostowski & Konrad Zdanowski

We consider the logic with the Henkin quantifiers L^{∗}, for the main ideas and concepts see survey [Krynicki–Mostowski 1995]. We continue investigations of the logic L^{∗} in empty vocabulary, see [Mostowski 1989] and [Mostowski 1991]. We prove that the set of all tautologies in infinite models of L^{∗} in empty vocabulary is of degree 0′. It answers the problem from [Mostowski 1991]. Moreover the same set restricted to quantifiers H_{n} has the same degree, what essentially follows from the result from [Krynicki–Mostowski 1992]. As a corolary we obtain that the set of all tautologies (in arbitrary models) of L^{∗} as well as L_{H_{ω}} in empty vocabulary is of degree 0′.

Additionaly, as a result, we obtain decidability of each logic L^{k}(Q) – the logic with Henkin quantifier Q, and k variables. On the other hand – by easy generalization of [Mostowski 1989] – for each algorithm A, the statement ”A decides L^{k}(Q)” cannot be proved e. g. in GB, for sufficiently large Henkin quantifier Q.

We consider also L^{∗} in σ_{n} – monadic vocabulary (with n unary predicates). We prove that, assuming some natural generalization of ”Chang Conjencture”, for each n and each class of Henkin quantifiers A, containing at least one nonlinear Henkin quantifier, the logic L_{σ_{n}}(A) either is decidable or it is not axiomatizable. This solves positively the following conjecture from [Krynicki–Mostowski 1992].

For each vocabulary σ and each class of Henkin quantifiers A, containing at least one nonlinear Henkin quantifier, the logic L_{σ}(A) either is decidable or it is not axiomatizable.

Additionally we improve some undecidability results from [Krynicki–Mostowski 1992] by showing that L_{σ_{n}}(H_{4}) and L_{σ_{n}}(H_{2}^{2}) are undecidable for some n.

Let E_{n} be \begin{matrix}∀x∃y_{1} … ∃y_{n} \\ ∀z∃w_{1} … ∃w_{n} \end{matrix} . Then we prove that pure logic with all quantifiers E_{n} is not decidable. It

improves the results of [Krynicki–Mostowski 1992] by proving the same for the logic appearingly weaker.

[Krynicki–Mostowski 1992] M. Krynicki and M. Mostowski, Decidability problems in language with Henkin quantifiers, in Annals of Pure and Applied Logic 58 (1992), pp. 149–172.

[Krynicki–Mostowski 1995] M. Krynicki and M. Mostowski Henkin Quantifiers in M. Krynicki, M. Mostowski, and L.W. Szczerba (eds.) Quantifiers: Logics, Models and Computation Volume I, Kluwer Academic Publishers, 1995, pp. 193–262.

[Mostowski 1989] M. Mostowski, Pure logic with branched quantifiers, in Zeitschrift für Mathematische Logik und Grundlagen der Mathematik 35 (1989), pp. 45–48.

[Mostowski 1991] M. Mostowski, Branched Quantifiers, Rozprawy Uniwersytetu Warszawskiego, Dział Wydawnictw Filii UW w Białymstoku, 1991.

Addresses Marcin Mostowski: Institute of Mathematics, WSP Słupsk, (Institute of Philosophy, Warsaw University), Poland

E-mail: marcinmo@plearn.edu.pl

Konrad Zdanowski: Institute of Philosophy, Warsaw University, Sokołowska 70 m. 95, 08–119 Siedlce, Poland