Abstract

We investigate some logics with Henkin quantifiers. For a given logic L, we consider questions of the form: what is the degree of the set of L–tautologies in a poor vocabulary (monadic or empty)? We prove that the set of tautologies of the logic with all Henkin quantifiers in empty vocabulary L*∅ is of degree 0’. We show that the same holds also for some weaker logics like L ∅(Hω) and L ∅(Eω). We show that each logic of the form L ∅ (k)(Q), with the number of variables restricted to k, is decidable. Nevertheless – following the argument of M. Mostowski from [Mos89] – for each reasonable set theory no concrete algorithm can provably decide L (k) (Q), for some (Q). We improve also some results related to undecidability and expressibility for logics L(H4) and L(F2) of Krynicki and M. Mostowski from [KM92]