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

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

Определение

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

• Множество ${displaystyle Asubseteq 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}) в A}$ если и только если ${displaystyle {mathcal {M}} модели 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}}}$ (с этими параметрами).

Примеры

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

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

${displaystyle varphi = exists x_ {0} cdots exists x_ {n-1} (x_ {0}$

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

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

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

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

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

${displaystyle varphi = exists y (ycdot yequiv x).}$

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

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

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

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

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

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

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

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

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

Рекомендации

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