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

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

Определение

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

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

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

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

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

Примеры

Натуральные числа, имеющие

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

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

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

$\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})))$

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

Натуральные числа и их арифметические действия

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

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

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

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

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

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

Инвариантность

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

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

$(a_{1},\ldots ,a_{m})\in A$ тогда и только тогда, когда $(\pi (a_{1}),\ldots ,\pi (a_{m}))\in A.$

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

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

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

Ссылки

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