We say that a first-order formula A ( x 1 x n ) over R defines a Boolean function f : 0 1 n 0 1 , if for every x 1 x n 0 1 , A ( x 1 x n ) is true iff f ( x 1 x n ) = 1 . We show that:

(i) every f can be defined by a formula of size O ( n ) , (ii) if A is required to have at most k 1 quantifier alternations, there exists an f which requires a formula of size 2 ( n k ) . The latter result implies several previously known as well as some new lower bounds in computational complexity. We note that (i) holds over any field of characteristic zero, and (ii) holds for any real closed or algebraically closed field.