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

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

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

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

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

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

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