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

Функция ${\displaystyle \mathbb {N} \to \mathbb {N} }$ называется арифметической, если её график является арифметическим множеством. Аналогично, можно говорить об арифметичности функций Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \N^n \to \N} и, вообще, функций, определённых на множествах любых конструктивных объектов.

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

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

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

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

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

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

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \forall (x \leq t) \varphi\ \overset{\mathrm{def}}\leftrightarrow\ \forall x\ x \leq t \rightarrow \varphi}

Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \exists (x \leq t) \varphi\ \overset{\mathrm{def}}\leftrightarrow\ \exists x\ x \leq t \wedge \varphi}

(или Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \forall (x < t) \varphi} , Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \exist (x < t) \varphi} для языков со строгим сравнением). Такие кванторы могут вводиться как сокращение для указанных справа формул, либо же как расширение языка. ${\displaystyle t}$ здесь может быть любым термом исходного языка, не содержащим свободного вхождения символа ${\displaystyle x}$, а ${\displaystyle \varphi }$ — любая формула. «Обычные» кванторы для подчёркивания отличия от ограниченных иногда называют неограниченными.

Формула называется ограниченной или ${\displaystyle \Delta _{0}}$-формулой, если она не содержит в себе неограниченные кванторы; при этом ограниченные она может содержать. Вводится также два синонимичных термина: ${\displaystyle \Sigma _{0}}$-формула и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Pi_0} -формула, которые обозначают то же самое, что и ${\displaystyle \Delta _{0}}$-формула.

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

формулу вида Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \exists x_1 \ldots \exists x_k\ \varphi} , где ${\displaystyle \varphi }$ — Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Pi_{n-1}} -формула, называют Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} -формулой;

формулу вида Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \forall x_1 \ldots \forall x_k\ \varphi} , где ${\displaystyle \varphi }$ — Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n-1}} -формула, называют Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Pi_{n}} -формулой.

Таким образом, ограниченная формула, предварённая ${\displaystyle n}$ группами чередующихся кванторов есть Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} -формула, если в начале стоят кванторы существования, и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} -формула, если сначала стоят кванторы всеобщности.

Разумеется, не каждая арифметическая формула имеет такой вид. Однако, как известно из логики предикатов, любую формулу можно привести к предварённой нормальной форме. Это позволяет ввести понятия Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} - и Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Pi_{n}} -формул в широком смысле: формула называется Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} - (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Pi_{n}} -) формулой в широком смысле, если в логике предикатов она эквивалента некоторой Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle \Sigma_{n}} - (Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\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}}$ представляет собой в точности все Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle 0^{(n-1)}} -перечислимые множества, класс ${\displaystyle \Pi _{n}}$ — Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle 0^{(n-1)}} -коперечислимые, а класс ${\displaystyle \Delta _{n}}$ — Невозможно разобрать выражение (SVG с запасным PNG (MathML можно включить с помощью плагина для браузера): Недопустимый ответ («Math extension cannot connect to Restbase.») от сервера «http://restbase-svc.restbase.svc.production22.local:7231/ru-mediawiki.ruwiki.svc.production22.local/v1/»:): {\displaystyle 0^{(n-1)}} -разрешимые. Таким образом, арифметические множества — это в точности все множества, которые можно получить из разрешимых степенью Тьюринга.