The arithmetic vocabulary has a binary symbol $\le$ and two ternary symbols for addition and multiplication. Every finite linear order interprets it canonically through the ranks of its elements: $\le$ is the order, $\mathrm{plus}(x, y, z)$ holds when the ranks satisfy $r(x) + r(y) = r(z)$ and $\mathrm{times}(x, y, z)$ when $r(x) \cdot r(y) = r(z)$. The two are graphs, hence truncated: a sum or a product that is not the rank of an element is related to nothing.

A decision problem $P$ over a relational vocabulary $L$ is AC⁰ definable when there is a first-order sentence $\varphi$ over $L$ and the arithmetic vocabulary such that, for every nonempty finite $L$-structure $A$ and every linear order on $A$, $A$ is a yes-instance of $P$ if and only if $\varphi$ holds in $A$ with the canonical arithmetic of that order. This is the logic FO($\le, +, \times$), which defines the problems of uniform AC⁰ by theorems of Barrington, Immerman and Straubing; no circuit model is introduced here.