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

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

Связанные определения

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

Арифметическая формула — формула в языке арифметики первого порядка.

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

Действительное число называется арифметическим, если множество рациональных чисел, меньших него, арифметично (или, что эквивалентно, если множество рациональных чисел, больших него, арифметично). Комплексное число называется арифметическим, если арифметичны и его действительная, и мнимая части.

Свойства

• Подмножество арифметического множества не обязательно арифметично.
• Совокупность всех арифметических множеств натуральных чисел является счётным множеством, а совокупность всех неарифметических множеств — несчётным.
• Множество комплексных арифметических чисел образует алгебраически замкнутое поле.
• Любое вычислимое число является арифметическим.
• Множество арифметических чисел (равно как и его дополнение) плотно в $\mathbb {R}$ и в $\mathbb {C} .$
• Порядок на множестве действительных арифметических чисел изоморфен порядку на множестве рациональных чисел.

Примеры

• Пустое множество является арифметическим.
• Любое перечислимое множество (в частности, любое разрешимое множество и любое конечное множество) являются арифметическими.
• Дополнение и проекция любого арифметического множества являются арифметическими.
• Объединение и пересечение конечного числа арифметических множеств также являются арифметическими.
• Множество чисел, начинающаяся с которых последовательность, определённая в гипотезе Коллатца, завершается единицей — арифметично, а в случае справедливости этой гипотезы — даже разрешимо тривиальным образом (всё множество натуральных чисел).
• Множество рациональных чисел, больших постоянной Хайтина Ω, арифметично, но неперечислимо.
• Множество номеров машин Тьюринга, не останавливающихся на пустом входе, арифметично (хотя и не перечислимо).
• Но множество номеров машин Тьюринга, реализующих операцию сравнения натуральных чисел, вполне упорядочивающую каким-либо образом множество $\mathbb {N} ,$ неарифметично.
• Множество утверждений, недоказуемых в ZFC, является арифметическим, но, при условии непротиворечивости ZFC — неперечислимым.
• Но множество истинных утверждений в арифметике первого порядка не является арифметическим (что составляет утверждение теоремы Тарского о невыразимости истины в арифметике), хотя множество доказуемых утверждений арифметично и даже перечислимо.

Арифметическая иерархия

Рассмотрим язык арифметики первого порядка, содержащий предикатный символ сравнения чисел ($<$ или $\leq$). Для такого языка определяется понятие ограниченных кванторов:

$\forall (x\leq t)\varphi \ {\overset {\mathrm {def} }{\leftrightarrow }}\ \forall x\ x\leq t\rightarrow \varphi$

$\exists (x\leq t)\varphi \ {\overset {\mathrm {def} }{\leftrightarrow }}\ \exists x\ x\leq t\wedge \varphi$

(или $\forall (x<t)\varphi$, $\exists (x<t)\varphi$ для языков со строгим сравнением). Такие кванторы могут вводиться как сокращение для указанных справа формул, либо же как расширение языка. $t$ здесь может быть любым термом исходного языка, не содержащим свободного вхождения символа $x$, а $\varphi$ — любая формула. «Обычные» кванторы для подчёркивания отличия от ограниченных иногда называют неограниченными.

Формула называется ограниченной или $\Delta _{0}$-формулой, если она не содержит в себе неограниченные кванторы; при этом ограниченные она может содержать. Вводится также два синонимичных термина: $\Sigma _{0}$-формула и $\Pi _{0}$-формула, которые обозначают то же самое, что и $\Delta _{0}$-формула.

Арифметическая иерархия формул представляет собой иерархию классов $\Sigma _{n}$-формул и $\Pi _{n}$-формул. Они определяются индуктивно:

формулу вида $\exists x_{1}\ldots \exists x_{k}\ \varphi$, где $\varphi$ — $\Pi _{n-1}$-формула, называют $\Sigma _{n}$-формулой;

формулу вида $\forall x_{1}\ldots \forall x_{k}\ \varphi$, где $\varphi$ — $\Sigma _{n-1}$-формула, называют $\Pi _{n}$-формулой.

Таким образом, ограниченная формула, предварённая $n$ группами чередующихся кванторов есть $\Sigma _{n}$-формула, если в начале стоят кванторы существования, и $\Sigma _{n}$-формула, если сначала стоят кванторы всеобщности.

Разумеется, не каждая арифметическая формула имеет такой вид. Однако, как известно из логики предикатов, любую формулу можно привести к предварённой нормальной форме. Это позволяет ввести понятия $\Sigma _{n}$- и $\Pi _{n}$-формул в широком смысле: формула называется $\Sigma _{n}$- ($\Pi _{n}$-) формулой в широком смысле, если в логике предикатов она эквивалента некоторой $\Sigma _{n}$- ($\Pi _{n}$-) формуле в узком смысле (раскрытие и сворачивание ограниченных кванторов также длпускается). Такое определение однако позволяет одной и той же формуле принадлежать нескольким классам арифметической иерархии в зависимости от того, в каком порядке будут выноситься кванторы при приведении к предварённой нормальной формуле. Поэтому имеет смысл задача о наиболее простом классе арифметической иерархии, к которому принадлежит формула в широком смысле.

Арифметическую иерархию можно рассмотреть и для множеств. Будем говорить, что множество $A$ принадлежит классу $\Sigma _{n}$ ($\Pi _{n}$), если его можно задать при помощи $\Sigma _{n}$- ($\Pi _{n}$-) формулы. Пересечение классов $\Sigma _{n}$ и $\Pi _{n}$ также называют классом $\Delta _{n}$-множеств. Нетрудно видеть, что арифметическая иерархия исчерпывает все арифметические множества.

Классы арифметической иерархии имеют связь с теорией вычислимости. Класс $\Sigma _{1}$ представляет собой в точности все перечислимые множества, класс $\Pi _{1}$ — коперечислимые, а класс $\Delta _{1}$ — разрешимые. Остальные классы арифметической иерархии представляют собой скачки Тьюринга предыдущих: класс $\Sigma _{n}$ представляет собой в точности все $0^{(n-1)}$-перечислимые множества, класс $\Pi _{n}$ — $0^{(n-1)}$-коперечислимые, а класс $\Delta _{n}$ — $0^{(n-1)}$-разрешимые. Таким образом, арифметические множества — это в точности все множества, которые можно получить из разрешимых степенью Тьюринга.

См. также

• Арифметическая иерархия
• Гиперарифметическая иерархия
• Аналитическая иерархия
• Проективная иерархия
• Борелевская иерархия

Литература

• Н. К. Верещагин, А. Шень. Часть 2. Языки и исчисления // Лекции по математической логике и теории алгоритмов. — 2-е изд.. — М.: МЦНМО, 2002.