Degrees of logics with Henkin quantifiers in poor vocabularies (Q1882566): Difference between revisions

For \(\sigma\) a signature and \(A\) a set of ``additional'' quantifiers, the language \(L_\sigma(A)\) denotes the first-order language (with equality) in the signature \(\sigma\), extended by the quantifiers in \(A\). For \(\text{H}\) the simplest Henkin quantifier, it is known that if \(\sigma\) contains either a function symbol or a binary predicate, then the set of \(L_\sigma(\text{H})\) validities is not arithmetical. In this paper, in the case where \(\sigma=\emptyset\) and \(\mathcal H\) is the set of all Henkin quantifiers, it is proved that the set of all \(L_\emptyset(\mathcal H)\) validities has degree \({\mathbf0}^\prime\) and that the set of all \(L_\emptyset(\mathcal H)\) sentences true in all infinite structures also has this same degree. The \(\mathbf0^\prime\) degree result is shown to hold for the weaker logics \(L_\emptyset(\text{H}_\omega)\) and \(L_\emptyset(\text{E}_\omega)\). Here \(\text{H}_\omega=\{\text{H}_ n: n=2, 3, \ldots\}\), where \(\text{H}_ n\) is the Henkin quantifier whose constituents are \(\forall x_ i \exists y_ i, 1\leq i\leq n\), and \(\text{E}_\omega=\{\text{E}_ n: n=1, 2, 3, \ldots\}\), where \(\text{E}_ n\) is the quantifier whose two constituents are \(\forall x\exists y_ 1\ldots \exists y_ n\) and \(\forall z\exists w_ 1\ldots \exists w_ n\). The authors also consider logics with finitely many variables. For \(\text{Q}\) a Henkin quantifier, \(L_\emptyset^{(k)}(\text{Q})\) is \(L_\emptyset(\text{Q})\) with its variables restricted to \(\{x_ 0,\ldots, x_{k-1}\}\). For every \(\text{Q}\in\mathcal H\) and every \(k\in\omega\), it is shown that the set of all \(L_\emptyset^{(k)}(\text{Q})\) sentences true in infinite structures is decidable. However the authors also show that ``for each reasonable set theory no concrete algorithm can provably decide \(L_\emptyset^{(k)}(\text{Q})\) for some \(\text{Q}\).'' The paper also has results for other quantifiers and ends with a list of open problems.