  We introduce a new framework for a descriptive complexity approach to
arithmetic computations. We define a hierarchy of classes based on the idea of
counting assignments to free function variables in first-order formulae. We
completely determine the inclusion structure and show that #P and #AC^0 appear
as classes of this hierarchy. In this way, we unconditionally place #AC^0
properly in a strict hierarchy of arithmetic classes within #P. We compare our
classes with a hierarchy within #P defined in a model-theoretic way by Saluja
et al. We argue that our approach is better suited to study arithmetic circuit
classes such as #AC^0 which can be descriptively characterized as a class in
our framework.
