Eine Relation R ⊆ N r {\displaystyle {}R\subseteq \mathbb {N} ^{r}} heißt arithmetisch repräsentierbar , wenn es einen L A r {\displaystyle {}L^{\rm {Ar}}} -Ausdruck ψ {\displaystyle {}\psi } in r {\displaystyle {}r} freien Variablen derart gibt, dass für alle r {\displaystyle {}r} -Tupel ( n 1 , … , n r ) ∈ N r {\displaystyle {}(n_{1},\ldots ,n_{r})\in \mathbb {N} ^{r}} die Äquivalenz ( n 1 , … , n r ) ∈ R {\displaystyle {}(n_{1},\ldots ,n_{r})\in R} genau dann, wenn N ⊨ ψ ( n 1 , … , n r ) {\displaystyle {}\mathbb {N} \vDash \psi (n_{1},\ldots ,n_{r})} gilt.
