ein Prädikat P auf den natürlichen Zahlen so, daß sich P(x₁,…, x_n) ausdrücken läßt mit Hilfe einer arithmetischen Formel, also einer Formel, die sich aus Aliquanteren, Existenzquantoren und einer Polynomgleichung zusammensetzt.

Jedes arithmetische Prädikat ist in der arithmetischen Hierarchie enthalten und umgekehrt.