Определимый набор

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

Определение

Пусть будет языком первого порядка, -структурой с доменом , фиксированным подмножеством и натуральным числом . Тогда : ${\displaystyle {\mathcal {L}}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle M}$ ${\displaystyle X}$ ${\displaystyle M}$ ${\displaystyle m}$

• Множество определимо в с параметрами из тогда и только тогда, когда существует формула и элементы такие, что для всех , ${\displaystyle A\subseteq M^{m}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle \varphi [x_{1},\ldots ,x_{m},y_{1},\ldots ,y_{n}]}$ ${\displaystyle b_{1},\ldots ,b_{n}\in X}$ ${\displaystyle a_{1},\ldots ,a_{m}\in M}$

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$если и только если ${\displaystyle {\mathcal {M}}\models \varphi [a_{1},\ldots ,a_{m},b_{1},\ldots ,b_{n}].}$

Скобки здесь указывают на семантическую оценку свободных переменных в формуле.

• Множество определяется без параметров , если оно определяется с параметрами из пустого множества (то есть без параметров в определяющей формуле). ${\displaystyle A}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Функция определима в (с параметрами), если ее график определим (с этими параметрами) в . ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {M}}}$
• Элемент определяется в (с параметрами), если набор синглтонов определяется в (с этими параметрами). ${\displaystyle a}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle \{a\}}$ ${\displaystyle {\mathcal {M}}}$

Примеры

Натуральные числа, имеющие только отношение порядка

Пусть будет структурой, состоящей из натуральных чисел с обычным порядком ^{[ требуется пояснение ]} . Тогда каждое натуральное число определимо в без параметров. Число определяется формулой, утверждающей, что не существует элементов, меньших x : ${\displaystyle {\mathcal {N}}=(\mathbb {N} ,<)}$ ${\displaystyle {\mathcal {N}}}$ ${\displaystyle 0}$ ${\displaystyle \varphi (x)}$

${\displaystyle \varphi =\neg \exists y(y<x),}$

а натуральное число определяется формулой, утверждающей, что существует ровно элементов, меньших x : ${\displaystyle n>0}$ ${\displaystyle \varphi (x)}$ ${\displaystyle n}$

${\displaystyle \varphi =\exists x_{0}\cdots \exists x_{n-1}(x_{0}<x_{1}\land \cdots \land x_{n-1}<x\land \forall y(y<x\rightarrow (y\equiv x_{0}\lor \cdots \lor y\equiv x_{n-1})))}$

Напротив, невозможно определить какое-либо конкретное целое число без параметров в структуре, состоящей из целых чисел с обычным порядком (см. раздел об автоморфизмах ниже). ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$

Натуральные числа с их арифметическими операциями

Пусть будет структурой первого порядка, состоящей из натуральных чисел и их обычных арифметических операций и отношения порядка. Множества, определяемые в этой структуре, известны как арифметические множества и классифицируются в арифметической иерархии . Если структура рассматривается в логике второго порядка вместо логики первого порядка, то определяемые множества натуральных чисел в полученной структуре классифицируются в аналитической иерархии . Эти иерархии раскрывают множество связей между определяемостью в этой структуре и теорией вычислимости , а также представляют интерес для дескриптивной теории множеств . ${\displaystyle {\mathcal {N}}=(\mathbb {N} ,+,\cdot ,<)}$

Поле действительных чисел

Пусть будет структурой, состоящей из поля действительных чисел ^{[ требуется пояснение ]} . Хотя обычное отношение упорядочения не включено напрямую в структуру, существует формула, которая определяет множество неотрицательных действительных чисел, поскольку это единственные действительные числа, имеющие квадратные корни: ${\displaystyle {\mathcal {R}}=(\mathbb {R} ,0,1,+,\cdot )}$

${\displaystyle \varphi =\exists y(y\cdot y\equiv x).}$

Таким образом, любой является неотрицательным тогда и только тогда, когда . В сочетании с формулой, которая определяет аддитивную инверсию действительного числа в , можно использовать для определения обычного порядка в : для , набор тогда и только тогда, когда неотрицателен. Расширенная структура называется дефиниционным расширением исходной структуры. Она имеет ту же выразительную силу, что и исходная структура, в том смысле, что набор определим над расширенной структурой из набора параметров тогда и только тогда, когда он определим над исходной структурой из того же набора параметров. ${\displaystyle a\in \mathbb {R} }$ ${\displaystyle {\mathcal {R}}\models \varphi [a]}$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle \varphi }$ ${\displaystyle {\mathcal {R}}}$ ${\displaystyle a,b\in \mathbb {R} }$ ${\displaystyle a\leq b}$ ${\displaystyle b-a}$ ${\displaystyle {\mathcal {R}}^{\leq }=(\mathbb {R} ,0,1,+,\cdot ,\leq )}$

Теория имеет исключение кванторов . Таким образом , определяемые множества являются булевыми комбинациями решений полиномиальных равенств и неравенств; они называются полуалгебраическими множествами . Обобщение этого свойства действительной прямой приводит к изучению o-минимальности . ${\displaystyle {\mathcal {R}}^{\leq }}$

Инвариантность относительно автоморфизмов

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

Пусть будет -структурой с областью , , и определимой в с параметрами из . Пусть будет автоморфизмом , который является тождественным на . Тогда для всех , ${\displaystyle {\mathcal {M}}}$ ${\displaystyle {\mathcal {L}}}$ ${\displaystyle M}$ ${\displaystyle X\subseteq M}$ ${\displaystyle A\subseteq M^{m}}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle \pi :M\to M}$ ${\displaystyle {\mathcal {M}}}$ ${\displaystyle X}$ ${\displaystyle a_{1},\ldots ,a_{m}\in M}$

${\displaystyle (a_{1},\ldots ,a_{m})\in A}$если и только если ${\displaystyle (\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.}$

Этот результат иногда можно использовать для классификации определяемых подмножеств заданной структуры. Например, в случае выше любой перевод из является автоморфизмом, сохраняющим пустой набор параметров, и, таким образом, невозможно определить какое-либо конкретное целое число в этой структуре без параметров в . Фактически, поскольку любые два целых числа переносятся друг в друга переводом и его обратным, единственными наборами целых чисел, определяемыми в без параметров, являются пустой набор и он сам. Напротив, существует бесконечно много определяемых наборов пар (или, на самом деле, n -кортежей для любого фиксированного n > 1) элементов из : (в случае n = 2) Булевы комбинации наборов для . В частности, любой автоморфизм (перевод) сохраняет «расстояние» между двумя элементами. ${\displaystyle {\mathcal {Z}}=(\mathbb {Z} ,<)}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle {\mathcal {Z}}}$ ${\displaystyle \{(a,b)\mid a-b=m\}}$ ${\displaystyle m\in \mathbb {Z} }$

Дополнительные результаты

Тест Тарского–Воота используется для характеристики элементарных подструктур данной структуры.

Ссылки

• Хинман, Питер. Основы математической логики , AK Peters, 2005.
• Маркер, Дэвид. Теория моделей: Введение , Springer, 2002.
• Рудин, Уолтер . Принципы математического анализа , 3-е изд. McGraw-Hill, 1976.
• Слэман, Теодор А. и Вудин, У. Хью . Математическая логика: курс бакалавриата в Беркли . Весна 2006 г.