В математической логике , А определимо множество представляет собой п - позиционной отношение на домене о наличии структуры , элементами которой являются именно те элементы , удовлетворяющие некоторую формулу в языке первого порядка этой структуры. Набор может быть определен с или без параметров , которые являются элементами домена , который может быть ссылка в формуле , определяющей соотношение.
Определение
Позволять быть языком первого порядка, ан -структура с доменом , фиксированное подмножество из, а также натуральное число . Потом:
- Множество можно определить в с параметрами из тогда и только тогда, когда существует формула и элементы такое, что для всех ,
- если и только если
- Обозначение скобок здесь указывает на семантическую оценку свободных переменных в формуле.
- Множество можно определить в без параметров, если это можно определить вс параметрами из пустого набора (то есть без параметров в определяющей формуле).
- Функция может быть определена в (с параметрами), если его график определен (с этими параметрами) в .
- Элемент можно определить в (с параметрами), если синглтон установлен можно определить в (с этими параметрами).
Примеры
Натуральные числа только с отношением порядка
Позволять - структура, состоящая из натуральных чисел с обычным порядком. Тогда каждое натуральное число определимо вбез параметров. Номер определяется формулой заявляя, что не существует элементов меньше x : и натуральное число определяется формулой заявляя, что существуют точно элементы меньше x :
Напротив, нельзя определить какое-либо конкретное целое число без параметров в структуресостоящий из целых чисел с обычным порядком (см. раздел об автоморфизмах ниже).
Натуральные числа с их арифметическими операциями
Позволять - структура первого порядка, состоящая из натуральных чисел и их обычных арифметических операций и отношения порядка. Наборы, определяемые в этой структуре, называются арифметическими наборами и классифицируются в арифметической иерархии . Если структура рассматривается в логике второго порядка, а не в логике первого порядка, определяемые наборы натуральных чисел в результирующей структуре классифицируются в аналитической иерархии . Эти иерархии выявляют множество взаимосвязей между определимостью в этой структуре и теорией вычислимости , а также представляют интерес для теории описательных множеств .
Поле действительных чисел
Позволять быть структура , состоящая из поля из действительных чисел . Хотя обычное отношение упорядочения не включено напрямую в структуру, существует формула, которая определяет набор неотрицательных вещественных чисел, поскольку это единственные действительные числа, которые имеют квадратные корни:
Таким образом, любой неотрицательно тогда и только тогда, когда . В сочетании с формулой, определяющей аддитивное обратное действительное число в, можно использовать определить обычный порядок в : для , набор если и только если неотрицательно. Увеличенная структураs называется дефиниционным расширением исходной структуры. Он обладает той же выразительной силой, что и исходная структура, в том смысле, что набор определяется над расширенной структурой из набора параметров тогда и только тогда, когда он определяется над исходной структурой из того же набора параметров.
Теория оимеет исключение квантора . Таким образом, определимые множества являются булевыми комбинациями решений полиномиальных равенств и неравенств; они называются полуалгебраическими множествами . Обобщение этого свойства действительной прямой приводит к изучению о-минимальности .
Инвариантность относительно автоморфизмов
Важный результат об определимых множествах состоит в том, что они сохраняются при автоморфизмах .
- Позволять быть -структура с доменом , , а также определяемый в с параметрами из . Позволять быть автоморфизмом что является тождеством на . Тогда для всех ,
- если и только если
Этот результат иногда можно использовать для классификации определяемых подмножеств данной структуры. Например, в случае выше, любой перевод является автоморфизмом, сохраняющим пустой набор параметров, и поэтому невозможно определить какое-либо конкретное целое число в этой структуре без параметров в . Фактически, поскольку любые два целых числа переводятся друг в друга посредством преобразования и обратного преобразования, единственные наборы целых чисел, определяемые в без параметров - пустой набор и сам. Напротив, существует бесконечно много определимых наборов пар (или действительно n -наборов для любого фиксированного n > 1) элементов, поскольку любой автоморфизм (перенос) сохраняет «расстояние» между двумя элементами.
Дополнительные результаты
Тест Тарского – Воота используется для характеристики элементарных подструктур данной структуры.
Рекомендации
- Хинман, Питер. Основы математической логики , А.К. Петерс, 2005.
- Маркер, Дэвид. Теория моделей: Введение , Springer, 2002.
- Рудин, Вальтер. Принципы математического анализа , 3-е. изд. Макгроу-Хилл, 1976.
- Сламан, Теодор А. и У. Хью Вудин. Математическая логика: бакалавриат в Беркли . Весна 2006 г.