Арифметическое множество — множество натуральных чисел ${\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} }$ и, вообще, функций, определённых на множествах любых конструктивных объектов.

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

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

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

Свойства

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

Примеры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

См. также

Литература

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