Арифметический набор

В математической логике арифметическое множество (или арифметическое множество ) — это множество натуральных чисел , которое можно определить по формуле первого порядка арифметики Пеано . Арифметические множества классифицируются по арифметической иерархии .

Определение может быть расширено на произвольное счетное множество A (например, набор из n - кортежей целых чисел , набор рациональных чисел , набор формул на некотором формальном языке и т. д.), используя числа Гёделя для представления элементов набора. и объявление подмножества A . арифметическим, если набор соответствующих чисел Гёделя является арифметическим

Функция ​ $f:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$ называется арифметически определимым если график , $f$ представляет собой арифметическое множество.

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

Формальное определение

Множество X натуральных чисел является арифметическим или арифметически определимым , если существует формула первого порядка φ( n ) на языке арифметики Пеано такая, что каждое число n находится в X тогда и только тогда, когда φ( n ) выполняется в стандартной модели. арифметики. Аналогично, k -арное отношение $R(n_{1},\ldots ,n_{k})$ является арифметическим, если существует формула $\psi (n_{1},\ldots ,n_{k})$ такой, что $R(n_{1},\ldots ,n_{k})\iff \psi (n_{1},\ldots ,n_{k})$ справедливо для всех k -кортежей $(n_{1},\ldots ,n_{k})$ натуральных чисел.

Функция ​ $f:\subseteq \mathbb {N} ^{k}\to \mathbb {N}$ называется арифметическим, если его график представляет собой арифметическое ( k +1)-арное отношение.

Множество A называется арифметическим в множестве B, если A можно определить с помощью арифметической формулы, в которой B является параметром множества.

Примеры

• Множество всех простых чисел является арифметическим.
• Каждое рекурсивно перечислимое множество является арифметическим.
• Любая вычислимая функция арифметически определима.
• Набор, кодирующий проблему остановки, является арифметическим.
• Константа Чайтина Ω представляет собой действительное арифметическое число.
• Теорема неопределимости Тарского показывает, что множество (числа Гёделя) истинных формул арифметики первого порядка не является арифметически определимым.

Свойства

• Дополнением арифметического множества является арифметическое множество.
• Скачок Тьюринга арифметического множества — это арифметическое множество.
• Набор арифметических множеств счетен, но последовательность арифметических множеств не является арифметически определимой. Таким образом, не существует арифметической формулы φ( n , m ), которая была бы истинной тогда и только тогда, когда m является членом n -го арифметического предиката.

Фактически, такая формула описывала бы проблему решения для всех конечных прыжков Тьюринга и, следовательно, принадлежала 0 ^(ой) , который не может быть формализован в арифметике первого порядка , так как не принадлежит арифметической иерархии первого порядка .

• Множество действительных арифметических чисел счетно , плотно и по порядку изоморфно множеству рациональных чисел.

Неявно арифметические множества

В каждом арифметическом наборе есть арифметическая формула, которая определяет, входят ли в этот набор определенные числа. Альтернативное понятие определимости допускает формулу, которая не говорит, находятся ли определенные числа в наборе, но говорит, удовлетворяет ли сам набор некоторым арифметическим свойствам.

Набор Y натуральных чисел является неявно арифметическим или неявно арифметически определимым, если его можно определить с помощью арифметической формулы, которая может использовать Y в качестве параметра. То есть, если существует формула $\theta (Z)$ на языке арифметики Пеано без свободных числовых переменных, с новым заданным параметром Z и множеством отношений принадлежности $\in$ такое, что Y — единственное множество Z такое, что $\theta (Z)$ держит.

Каждый арифметический набор неявно арифметичен; если X арифметически определяется φ( n ), то он неявно определяется формулой

$\forall n[n\in Z\Leftrightarrow \phi (n)]$.

Однако не каждое неявно арифметическое множество является арифметическим. В частности, набор истинности арифметики первого порядка является неявно арифметическим, но не арифметическим.

См. также

• Арифметическая иерархия
• Вычислимое множество
• Вычислимое число

Дальнейшее чтение

• Хартли Роджерс младший (1967). Теория рекурсивных функций и эффективная вычислимость. МакГроу-Хилл. ОСЛК   527706