 with \(F(y_1,\ldots,y_m)\) being of complexity \(\Pi^0_k\) (\(\Sigma^0_k\)). Thus the complexity of a formula is measured in terms of quantifier alternations. For instance \(\Pi^0_2\)-formulae have two alternations starting with a block of universal quantifiers or more explicitly they are of the shape 