Klassifikation von Formeln

Die arithmetische Hierarchie klassifiziert Formeln in der Sprache der Peano-Arithmetik in Klassen namens ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$ und ${\displaystyle \Delta _{n}^{0}}$ für natürliche Zahlen n.

Die niedrigste Stufe bilden Formeln, die eine entscheidbare Relation definieren. Diese bilden die Klasse ${\displaystyle \Delta _{0}^{0}=\Pi _{0}^{0}=\Sigma _{0}^{0}}$. Die weiteren Klassen werden für jede Zahl n induktiv wie folgt definiert:

• Wenn ${\displaystyle \varphi }$ äquivalent zu einer Formel ${\displaystyle \exists x_{1}\exists x_{2}\cdots \exists x_{k}\psi }$ ist, wobei ${\displaystyle \psi }$ in ${\displaystyle \Pi _{n}^{0}}$ liegt, dann liegt ${\displaystyle \varphi }$ in ${\displaystyle \Sigma _{n+1}^{0}}$.
• Wenn ${\displaystyle \varphi }$ äquivalent zu einer Formel ${\displaystyle \forall x_{1}\forall x_{2}\cdots \forall x_{k}\psi }$ ist, wobei ${\displaystyle \psi }$ in ${\displaystyle \Sigma _{n}^{0}}$ liegt, dann liegt ${\displaystyle \varphi }$ in ${\displaystyle \Pi _{n+1}^{0}}$.
• ${\displaystyle \Delta _{n}^{0}=\Sigma _{n}^{0}\cap \Pi _{n}^{0}}$ (für alle n)

Jede arithmetische Formel ist äquivalent zu einer Formel in Pränexnormalform, die abwechselnd einen All- und einen Existenzquantor hat. Bei einer ${\displaystyle \Sigma _{n}^{0}}$-Formel steht zuerst ein Existenzquantor; bei einer ${\displaystyle \Pi _{n}^{0}}$-Formel ein Allquantor. Jede ${\displaystyle \Pi _{n}^{0}}$-Formel ist äquivalent zur Negation einer ${\displaystyle \Sigma _{n}^{0}}$-Formel.

Da zu jeder Formel redundante Quantoren, die keine vorkommende Variable binden, hinzugefügt werden können, liegen alle Formeln in ${\displaystyle \Sigma _{n}^{0}}$ oder ${\displaystyle \Pi _{n}^{0}}$ auch in ${\displaystyle \Sigma _{m}^{0}}$ und ${\displaystyle \Pi _{m}^{0}}$ für alle m > n.

Alternativ kann die niedrigste Klasse ${\displaystyle \Delta _{0}^{0}=\Pi _{0}^{0}=\Sigma _{0}^{0}}$ so definiert werden, dass sie nur Formeln enthält, die zu einer Formel äquivalent sind, die nur beschränkte Quantoren hat. In diesem Fall enthält die niedrigste Klasse weniger Relationen; alle weiteren Klassen bleiben gleich.

Klassifikation von Mengen und Relationen

Eine Menge X von natürlichen Zahlen wird durch eine Formel ${\displaystyle \varphi (x)}$ in der Sprache der Peano-Arithmetik definiert, wenn X genau die Zahlen enthält, die ${\displaystyle \varphi (x)}$ erfüllen, d. h.:

${\displaystyle n\in X\Leftrightarrow \mathbb {N} \models \varphi ({\underline {n}}),}$

wobei ${\displaystyle {\underline {n}}}$ der Term in der Sprache der Arithmetik ist, der die Zahl ${\displaystyle n}$ repräsentiert. Eine Menge heißt arithmetisch, wenn sie durch eine Formel der Peano-Arithmetik definiert wird. Eine Menge X von natürlichen Zahlen ist ${\displaystyle \Sigma _{n}^{0}}$, ${\displaystyle \Pi _{n}^{0}}$, oder ${\displaystyle \Delta _{n}^{0}}$, wenn sie durch eine Formel in der entsprechenden Klasse definiert wird. Ebenso lassen sich auch Relationen bzw. Mengen von k-Tupeln natürlicher Zahlen klassifizieren, wenn man Formeln mit k freien Variablen betrachtet.