Арифметическое множество

---

Арифметическое множество — множество натуральных чисел ${\displaystyle S\subseteq \mathbb {N} }$, которое может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула ${\displaystyle \varphi (x)}$ с одной свободной переменной ${\displaystyle x}$, что ${\displaystyle x\in S\Leftrightarrow \varphi (x)}$. Аналогично, множество кортежей натуральных чисел ${\displaystyle S\subseteq \mathbb {N} ^{n}}$ называется арифметическим, если существует такая формула ${\displaystyle \varphi (x_{1},\ldots ,x_{n})}$, что ${\displaystyle (x_{1},\ldots ,x_{n})\in S\Leftrightarrow \varphi (x_{1},\ldots ,x_{n})}$. Также можно говорить об арифметических множествах кортежей натуральных чисел, конечных последовательностей натуральных чисел, формул (при любой их фиксированной гёделевской нумерации) и, вообще, об арифметических множествах любых объектов, кодируемых натуральными числами.

Функция ${\displaystyle \mathbb {N} \to \mathbb {N} }$ называется арифметической, если её график является арифметическим множеством. Аналогично, можно говорить об арифметичности функций ${\displaystyle \mathbb {N} ^{n}\to \mathbb {N} }$ и, вообще, функций, определённых на множествах любых конструктивных объектов.

Предикат (свойство) называется арифметическим, если он может быть задан при помощи арифметической формулы. Понятия предиката, свойства и множества часто отождествляют, из-за чего отождествляются и понятия арифметичности для них.

---