НПВ (теория моделей)

В теории моделей , разделе математической логики полная теория T , говорят, что удовлетворяет NIP («не свойству независимости»), если ни одна из ее формул не удовлетворяет свойству независимости , то есть если ни одна из ее формул не может выбрать какой-либо заданный параметр. подмножество сколь угодно большого конечного множества.

Определение

Пусть T — полная L -теория. Говорят, что L ) , -формула φ( x , y ) обладает свойством независимости (относительно x , y если в каждой модели M модели T существует для каждого n = {0,1,..., n − 1} < ω — семейство наборов b ₀ ,..., b _{n −1} такое, что для каждого из 2 ^н подмножеств X из n, существует кортеж a, в M для которого

$M\models \varphi ({\boldsymbol {a}},{\boldsymbol {b}}_{i})\quad \Leftrightarrow \quad i\in X.$

Говорят, что теория T обладает свойством независимости, если некоторая формула обладает свойством независимости. Если ни одна L -формула не обладает свойством независимости, то T называется зависимым или удовлетворяет NIP. -структура Говорят, что L обладает свойством независимости (соответственно NIP), если ее теория обладает свойством независимости (соответственно NIP). Терминология происходит от понятия независимости в смысле булевых алгебр .

В терминологии теории Вапника–Червоненкиса можно сказать, что совокупность S подмножеств X разрушает множество B ⊆ X , если каждое подмножество B имеет вид B ∩ S для некоторого S ∈ S . Тогда T обладает свойством независимости, если в некоторой модели M модели T существует определимое семейство ( S _a | a ∈ M ^н ) ⊆ М ^к который разбивает сколь угодно большие конечные подмножества M ^к . Другими словами, ( S _a | a ∈ M ^н ) имеет бесконечную размерность Вапника–Червоненкиса .

Примеры

Любая полная теория T , обладающая свойством независимости, неустойчива .

В арифметике, то есть в структуре ( N ,+,·), формула « y делит x » обладает свойством независимости. Эта формула просто

$(\exists k)(y\cdot k=x).$

Итак, для любого конечного n мы принимаем n 1-кортежей b _i в качестве первых n простых чисел , а затем для любого подмножества X из {0,1,..., n − 1} мы позволяем a быть произведением те b _i такие, что i находится в X . Тогда b _i делит a тогда и только тогда, когда i ∈ X .

Любая o-минимальная теория удовлетворяет NIP. Этот факт нашел неожиданное применение в обучении нейронных сетей.

Примеры теорий NIP включают также теории всех следующих структур: линейные порядки , деревья , абелевы линейно упорядоченные группы , алгебраически замкнутые поля со значениями и p-адическое поле для любого p.

Ссылки

• Энтони, Мартин; Бартлетт, Питер Л. (1999). Обучение нейронных сетей: теоретические основы . Издательство Кембриджского университета . ISBN  978-0-521-57353-5 .
• Ходжес, Уилфрид (1993). Модельная теория . Издательство Кембриджского университета . ISBN  978-0-521-30442-9 .
• Найт, Джулия ; Пиллэй, Ананд; Стейнхорн, Чарльз (1986). «Определимые множества в упорядоченных структурах II» . Труды Американского математического общества . 295 (2): 593–605. дои : 10.2307/2000053 . JSTOR   2000053 .
• Пиллэй, Ананд; Стейнхорн, Чарльз (1986). «Определимые множества в упорядоченных структурах I» . Труды Американского математического общества . 295 (2): 565–592. дои : 10.2307/2000052 . JSTOR   2000052 .
• Пуаза, Бруно (2000). Курс теории моделей . Спрингер. ISBN  978-0-387-98655-5 .
• Саймон, Пьер (2015). Руководство по теориям НПВ . Издательство Кембриджского университета. ISBN  9781107057753 .