Введение
Математическое понятие
В математической логике, арифметическое множество (или арифметическое множество) — это множество натуральных чисел, которое может быть определено формулой арифметики Пеано первого порядка. Арифметические множества классифицируются по арифметической иерархии. Определение может быть расширено на произвольное счетное множество A (например, множество n-кортежей целых чисел, множество рациональных чисел, множество формул в некотором формальном языке и т. д.) путем использования чисел Гёделя для представления элементов множества и объявления подмножества A арифметическим, если множество соответствующих чисел Гёделя является арифметическим. Функция называется арифметически определимой, если её график является арифметическим множеством. Действительное число называется арифметическим, если множество всех меньших рациональных чисел является арифметическим. Комплексное число называется арифметическим, если его действительная и мнимая части являются арифметическими.
In mathematical logic, an arithmetical set (or arithmetic set) is a set of natural numbers that can be defined by a formula of first order Peano arithmetic. The arithmetical sets are classified by the arithmetical hierarchy. The definition can be extended to an arbitrary countable set A (e. g. the set of n tuples of integers, the set of rational numbers, the set of formulas in some formal language, etc.) by using Gödel numbers to represent elements of the set and declaring a subset of A to be arithmetical if the set of corresponding Gödel numbers is arithmetical. A function is called arithmetically definable if the graph of is an arithmetical set. A real number is called arithmetical if the set of all smaller rational numbers is arithmetical. A complex number is called arithmetical if its real and imaginary parts are both arithmetical.
Формальное определение
Множество X натуральных чисел называется арифметическим или арифметически определяемым, если существует формула первого порядка φ(n) в языке арифметики Пеано такая, что каждое число n принадлежит X тогда и только тогда, когда φ(n) истинна в стандартной модели арифметики. Аналогично, k-арное отношение называется арифметическим, если существует формула, которая выполняется для всех k-ок натуральных чисел. Функция называется арифметической, если её график является арифметическим (k+1)-арным отношением. Множество A называется арифметическим относительно множества B, если A определяется арифметической формулой, в которой B является параметром множества.
Примеры
Множество всех простых чисел арифметическое. Каждое рекурсивно перечислимое множество является арифметическим. Каждая вычислимая функция арифметически определима. Множество, кодирующее проблему останова, арифметическое. Постоянная Чейтина Ω — арифметическое действительное число. Теорема Тарского о неопределимости показывает, что множество истинных формул арифметики первого порядка (числа Гёделя) не является арифметически определимым.
Свойства
Дополнение арифметического множества является арифметическим множеством. Тьюринг-прыжок арифметического множества является арифметическим множеством. Коллекция арифметических множеств счетна, но последовательность арифметических множеств не является арифметически определимой. Таким образом, не существует арифметической формулы φ(n, m), которая была бы истинна тогда и только тогда, когда m принадлежит n-му арифметическому предикату. На самом деле, такая формула описывала бы задачу решения для всех конечных Тьюринг-прыжков и, следовательно, принадлежала бы классу 0ω, который не может быть формализован в арифметике первого порядка, поскольку он не принадлежит арифметической иерархии первого порядка. Множество вещественных арифметических чисел счетно, плотно и упорядоченно изоморфно множеству рациональных чисел.