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

Арифметическое множество — множество натуральных чисел $S$, которое может быть определено формулой в языке арифметики первого порядка, то есть если существует такая формула $\phi (x)$ с одной свободной переменной $x,$ что $\forall x(x\in S\leftrightarrow \phi (x))$. Также можно говорить об арифметических множествах кортежей натуральных чисел, конечных последовательностей натуральных чисел, формул (при любой их фиксированной гёделевской нумерации) и, вообще, об арифметических множествах любых конструктивных объектов, кодируемых натуральными числами.

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

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

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

Свойства

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

Примеры

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

См. также

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

Литература

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