Finite partially-ordered quantification

Abstract

In [3] Henkin made the observation that certain second-order existential formulas may be thought of as the Skolem normal forms of formulas of a language which is first-order in every respect except its incorporation of a form of partially-ordered quantification. One formulation of this sort of language is the closure of a first-order language under the formation rule that Qφ is a formula whenever φ is a formula and Q , which is to be thought of as a quantifier-prefix, is a system of partial order whose universe is a set of quantifiers. Although he introduced this idea in a discussion of infinitary logic, Henkin went on to discuss its application to finitary languages, and he concluded his discussion with a theorem of Ehrenfeucht that the incorporation of an extremely simple partially-ordered quantifier-prefix (the quantifiers ∀ x , ∀ y , ∃ v , and ∃ w , with the ordering {〈 ∀ x , ∃ v 〉, 〈 ∀ y , ∃ w 〉}) into any first-order language with identity gives a language capable of expressing the infinitary quantifier ∃ zκ 0 x .