Введение
В математической логике, определяемое множество - это числовое отношение в области структуры, элементы которой удовлетворяют некоторой формуле в языке первого порядка этой структуры. Множество может быть определено с параметрами или без них, которые являются элементами области, на которые можно ссылаться в формуле, определяющей отношение.
Натуральные числа с их арифметическими операциями
Пусть будет первой структурой порядка, состоящей из натуральных чисел и их обычных арифметических операций и отношений порядка. Множества, определяемые в этой структуре, известны как арифметические множества и классифицируются в арифметической иерархии. Если структура рассматривается в логике второго порядка, а не в логике первого порядка, то определяемые множества натуральных чисел в полученной структуре классифицируются в аналитической иерархии. Эти иерархии раскрывают много связей между определяемостью в этой структуре и теорией вычислимости, а также представляют интерес в описательной теории множеств.
Поле действительных чисел
Пусть будет структура, состоящая из поля действительных чисел. Хотя обычная соотношение упорядочения не включено непосредственно в структуру, есть формула, которая определяет множество неотрицательных действительных чисел, так как это единственные действительные числа, которые обладают квадратными корнями: Таким образом, любое неотрицательно, если и только если В сочетании с формулой, которая определяет аддитивную обратную величину реального числа в , можно использовать для определения обычного упорядочения в: для , множество, если и только если неотрицательно. Расширенная структура называется расширением первоначальной структуры. Она имеет ту же экспрессивную силу, что и исходная структура, в том смысле, что множество можно определить по расширенной структуре из набора параметров, если и только если оно можно определить по исходной структуре из того же набора параметров. Теория устранения количественного знака. Таким образом, определяемые множества являются булевыми комбинациями решений полиномиальных равенств и неравенств; они называются полуалгебраическими множествами. Обобщение этого свойства реальной прямой приводит к изучению о-минимальности.
Thus any is nonnegative if and only if In conjunction with a formula that defines the additive inverse of a real number in , one can use to define the usual ordering in : for , set if and only if is nonnegative. The enlarged structure is called a definitional extension of the original structure. It has the same expressive power as the original structure, in the sense that a set is definable over the enlarged structure from a set of parameters if and only if it is definable over the original structure from that same set of parameters. The theory of has quantifier elimination. Thus the definable sets are Boolean combinations of solutions to polynomial equalities and inequalities; these are called semi algebraic sets. Generalizing this property of the real line leads to the study of o minimality.
Дополнительные результаты
Испытание Тарски-Ваута используется для характеристики элементарных подструктур данной структуры.