1. In a recursively constructed language, a measure of the number of applications of formation rules needed to construct a formula $\phi$ from atomic formulae. Atomic formulae are judged as having complexity $0$, while a conjunction of atomic formulae will have complexity $1$, etc.

2. A measure of the minimal number of alternations of universal and existential quantifiers needed to express the prenex normal form of a unary formula in number theory. If one says that all quantifier-free formulae in the language of arithmetic are ${\Delta }_0$, then one can define the complexity of a formula $\psi$ recursively:

• • A formula $\psi$ is ${\Sigma }_n$ if it is equivalent to a formula $\phi =\exists x_0...\exists x_m\xi$ where $\xi$ is ${\text{Π}}_{n-1}$

• • A formula $\psi$ is ${\text{Π}}_n$ if it is equivalent to a formula $\phi =\forall x_0...\forall x_m\xi$ where $\xi$ is ${\Sigma }_{n-1}$

• • A formula $\psi$ is ${\Delta }_n$ if it is both ${\Sigma }_n$ and ${\text{Π}}_n$

Then we say that a set $S\subseteq \mathbb{N}$ is a member of a complexity class if there exists a formula $\phi \left(x\right)$ of that complexity such that $S$ is defined by $\phi \left(x\right)$, that is, for all natural numbers $n$, $n\in S$ if and only if $\phi \left(n\right)$ is true in number theory. A set of natural numbers that is a member of one of these classes is known as arithmetical, whence the collection of these sets is known as the arithmetical hierarchy.