The diversity of quantifier prefixes

Abstract

The Arithmetical Hierarchy Theorem of Kleene [1] states that in the complete theory of the standard model of arithmetic there is for each positive integer r a Σ r 0 formula which is not equivalent to any Π r 0 formula, and a Π r 0 formula which is not equivalent to any Π r 0 formula. A Π r 0 formula is a formula of the form where φ has only bounded quantifiers; Π r 0 formulas are defined dually. The Linear Prefix Theorem in [3] is an analogous result for predicate logic. Consider the first order predicate logic L with identity symbol, countably many n -placed relation symbols for each n , and no constant or function symbols. A prefix is a finite sequence of quantifier symbols ∃ and ∀, for example ∀∃∀∀∀∃. By a Q formula we mean a formula of L of the form where v 1 , …, v r are distinct variables and φ has no quantifiers. A sentence is a formula with no free variables. The Linear Prefix Theorem is as follows. Linear Prefix Theorem. Let Q and q be two different prefixes of the same length r. Then there is a Q sentence which is not logically equivalent to any q sentence . Moreover, for each s there is a Q formula with s free variables which is not logically equivalent to any q formula with s free variables . For example, there is an ∀∃∀∀∀∃ sentence which is not logically equivalent to any ∀∃∃∀∀∃ sentence, and vice versa. Recall that in arithmetic two consecutive ∃'s or ∀'s can be collapsed; for instance all ∀∃∀∀∀∃ and ∀∃∃∀∀∃ formulas are logically equivalent to Π 4 0 formulas. But the Linear Prefix Theorem shows that in predicate logic the number of quantifiers in each block, as well as the number of blocks, counts.