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

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

Связанные определения

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

Арифметическая формула — формула в языке арифметики первого порядка.

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

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

Свойства

Примеры

Арифметическая иерархия

Рассмотрим язык арифметики первого порядка, содержащий предикатный символ сравнения чисел ( или ). Для такого языка определяется понятие ограниченных кванторов:

(или , для языков со строгим сравнением). Такие кванторы могут вводиться как сокращение для указанных справа формул, либо же как расширение языка. здесь может быть любым термом исходного языка, не содержащим свободного вхождения символа , а — любая формула. «Обычные» кванторы для подчёркивания отличия от ограниченных иногда называют неограниченными.

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

Арифметическая иерархия формул представляет собой иерархию классов -формул и -формул. Они определяются индуктивно:

формулу вида , где -формула, называют -формулой;
формулу вида , где -формула, называют -формулой.

Таким образом, ограниченная формула, предварённая группами чередующихся кванторов есть -формула, если в начале стоят кванторы существования, и -формула, если сначала стоят кванторы всеобщности.

Разумеется, не каждая арифметическая формула имеет такой вид. Однако, как известно из логики предикатов, любую формулу можно привести к предварённой нормальной форме. Это позволяет ввести понятия - и -формул в широком смысле: формула называется - ( -) формулой в широком смысле, если в логике предикатов она эквивалента некоторой - ( -) формуле в узком смысле (раскрытие и сворачивание ограниченных кванторов также длпускается). Такое определение однако позволяет одной и той же формуле принадлежать нескольким классам арифметической иерархии в зависимости от того, в каком порядке будут выноситься кванторы при приведении к предварённой нормальной формуле. Поэтому имеет смысл задача о наиболее простом классе арифметической иерархии, к которому принадлежит формула в широком смысле.

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

Классы арифметической иерархии имеют связь с теорией вычислимости. Класс представляет собой в точности все перечислимые множества, класс — коперечислимые, а класс — разрешимые. Остальные классы арифметической иерархии представляют собой скачки Тьюринга предыдущих: класс представляет собой в точности все -перечислимые множества, класс -коперечислимые, а класс -разрешимые. Таким образом, арифметические множества — это в точности все множества, которые можно получить из разрешимых степенью Тьюринга.

См. также

Литература

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

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