Degrees of logics with Henkin quantifiers in poor vocabularies

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(H₄) and L(F₂) of Krynicki and M. Mostowski from [KM92].Mathematics Subject Classification (2000): 03C80, 03D35, 03B25Revised version: 28 August 2003