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

редактировать

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

Содержание

1 Определение
2 Примеры
- 2.1 Натуральные числа только с отношением порядка
- 2.2 Натуральные числа с их арифметическими операциями
- 2.3 Поле действительных чисел
3 Инвариантность относительно автоморфизмов
4 Дополнительные результаты
5 Ссылки

Определение

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

Набор $A ⊆ M m {\ displaystyle A \ substeq M ^ {m}}$ $A \ substeq M ^ {m}$ может быть определен в $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ с параметрами из $X {\ displaystyle X}$ $X$ тогда и только тогда, когда существует формула $φ [x 1,…, xm, y 1,…, yn ] {\ displaystyle \ varphi [x_ {1}, \ ldots, x_ {m}, y_ {1}, \ ldots, y_ {n}]}$ ${\ displaystyle \ varphi [x_ {1}, \ ldots, x_ {m}, y_ {1}, \ ldots, y_ {n}] }$ и элементы $b 1,…, bn ∈ X {\ displaystyle b_ {1}, \ ldots, b_ {n} \ in X}$ ${\ displaystyle b_ {1}, \ ldots, b_ {n} \ in X}$ такой, что для всех $a 1,…, am ∈ M {\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}$ ${\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}$ ,

(a 1,…, am) ∈ A {\ displaystyle (a_ {1}, \ ldots, a_ {m}) \ in A}

{\ displaystyle (a_ {1}, \ ldots, a_ {m}) \ in A}

тогда и только тогда, когда

M ⊨ φ [a 1,…, am, b 1,…, bn] {\ displaystyle {\ mathcal {M}} \ models \ varphi [a_ {1}, \ ldots, a_ {m}, b_ {1}, \ ldots, b_ {n}]}

{\ displaystyle {\ mathcal {M}} \ models \ varphi [a_ {1}, \ ldots, a_ {m}, b_ {1}, \ ldots, b_ {n}]}

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

Набор $A {\ displaystyle A}$ $A$ может быть определен в $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ без параметров, если он определен i n $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ с параметрами из пустого набора (то есть без параметров в определяющей формуле).

Функция может быть определена в $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ (с параметрами), если ее график определен (с этими параметрами) в $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ .

Элемент $a {\ displaystyle a}$ $a$ может быть определен в $M {\ displaystyle {\ mathcal {M}}}$ ${\ mathcal {M}}$ (с параметрами), если одноэлементный набор ${a} {\ displaystyle \ {a \}}$ $\ {a \}$ может быть определен в $M {\ displaystyle {\ mathcal {M }}}$ ${\ mathcal {M}}$ (с этими параметрами).

Примеры

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

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

$φ = ∃ x 0 ⋯ ∃ xn - 1 (x 0 < x 1 ∧ ⋯ ∧ x n − 1 < x ∧ ∀ y ( y < x → ( y ≡ x 0 ∨ ⋯ ∨ y ≡ x n − 1))) {\displaystyle \varphi =\exists x_{0}\cdots \exists x_{n-1}(x_{0}$ ${\ 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) })))}$

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

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

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

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

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

$φ = ∃ y (y ⋅ y ≡ x). {\ displaystyle \ varphi = \ exists y (y \ cdot y \ Equiv x).}$ ${\ displaystyle \ varphi = \ exists y (y \ cdot y \ Equiv x).}$

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

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

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

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

Пусть

M {\ displaystyle {\ mathcal {M}}}

{\ mathcal {M}}

быть

L {\ displaystyle {\ mathcal {L}}}

{\ mathcal {L}}

-структурой с доменом

M {\ displaystyle M}

M

Икс ⊆ M {\ displaystyle X \ substeq M}

{\ displaystyle X \ substeq M}

A ⊆ M m {\ displaystyle A \ substeq M ^ {m}}

A \ substeq M ^ {m}

определяется в

M {\ displaystyle {\ mathcal {M}}}

{\ mathcal {M}}

с параметрами из

X {\ displaystyle X}

X

. Пусть

π: M → M {\ displaystyle \ pi: M \ to M}

{\ displaystyle \ pi: M \ to M}

будет автоморфизмом

M {\ displaystyle {\ mathcal {M}}}

{\ mathcal {M}}

, который является идентификатором на

X {\ displaystyle X}

X

. Тогда для всех

a 1,…, am ∈ M {\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}

{\ displaystyle a_ {1}, \ ldots, a_ {m} \ in M}

(a 1,…, am) ∈ A {\ displaystyle ( a_ {1}, \ ldots, a_ {m}) \ in A}

{\ displaystyle (a_ {1}, \ ldots, a_ {m}) \ in A}

тогда и только тогда, когда

(π (a 1),…, π (am)) ∈ A {\ displaystyle ( \ pi (a_ {1}), \ ldots, \ pi (a_ {m})) \ in A}

{\ displaystyle (\ pi (a_ {1}), \ ldots, \ pi (a_ {m})) \ in A}

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

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

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

Ссылки

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