The page on descriptive complexity theory in Wikipedia states the following:
"First-order logic defines the class FO, corresponding to AC0, the languages recognized by polynomial-size circuits of bounded depth, which equals the languages recognized by a concurrent random access machine in constant time."
How can we show that first order logic is equivalent to AC0?
In Clote and Kranakis' book Boolean Functions and Models of Computation (Springer, p. 34), it is states that symmetric boolean functions are in AC0.
Could we the state that symmetric functions are equivalent to AC0 and first order logic? I am guessing that no, but still...