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

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

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

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

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

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

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

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

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

Примеры

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

Свойства

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

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

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

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

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

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

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

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

.

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

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

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

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

Число системы
Счетные множества	Натуральные числа ( ${ Displaystyle mathbb {N}}$ ) Целые числа ( ${ Displaystyle mathbb {Z}}$ ) Рациональное число ( ${ displaystyle mathbb {Q}}$ ) Конструируемые числа Алгебраические числа ( ${ displaystyle mathbb {A}}$ ) Периоды Вычислимые числа Определимые действительные числа Арифметические числа Гауссовские целые числа
Композиционные алгебры	Алгебры с делением: Действительные числа ( ${ Displaystyle mathbb {R}}$ ) Сложные числа ( ${ Displaystyle mathbb {C}}$ ) Кватернионы ( ${ displaystyle mathbb {H}}$ ) Октонионы ( ${ displaystyle mathbb {O}}$ )
Трещина типы	над ${ Displaystyle mathbb {R}}$ : Сплит-комплексные числа Сплит-кватернионы Сплит-октонионы над ${ Displaystyle mathbb {C}}$ : Бикомплексные числа Бикватернионы Биоктонионы
Другой гиперкомплекс	Двойные числа Двойные кватернионы Двойные комплексные числа Гиперболические кватернионы Седенионы ( ${ Displaystyle mathbb {S}}$ ) Сплит-бикватернионы Мультикомплексные номера Геометрическая алгебра Алгебра физического пространства Алгебра пространства-времени
Другие типы	Количественные числительные Иррациональные числа Нечеткие числа Гиперреальные числа Поле Леви-Чивита Сюрреалистические числа Трансцендентные числа Порядковые номера п-адический числа (п-адический соленоиды ) Сверхъестественные числа Сверхреальные числа
Классификация Список