The quantifier complexity of polynomial‐size iterated definitions in first‐order logic

We refine the constructions of Ferrante‐Rackoff and Solovay on iterated definitions in first‐order logic and their expressibility with polynomial size formulas. These constructions introduce additional quantifiers; however, we show that these extra quantifiers range over only finite sets and can be eliminated. We prove optimal upper and lower bounds on the quantifier complexity of polynomial size formulas obtained from the iterated definitions. In the quantifier‐free case and in the case of purely existential or universal quantifiers, we show that Ω(n /log n) quantifiers are necessary and sufficient. The last lower bounds are obtained with the aid of the Yao‐Håstad switching lemma (© 2010 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)