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

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

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

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

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

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

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

Финитарная функция на множество натуральных чисел называются арифметической , если его график является арифметическим бинарным отношением.

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

Примеры

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

Характеристики

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

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

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

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

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

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

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

${\ Displaystyle \ forall п [п \ в Z \ Leftrightarrow \ phi (п)]}$.

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

Смотрите также

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

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

• Роджерс, Х. (1967). Теория рекурсивных функций и эффективной вычислимости. Макгроу-Хилл. OCLC  527706