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

В теории моделей , разделе математической логики , полная теория 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 , для которого

${\displaystyle 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 ^k , которое разрушает произвольно большие конечные подмножества M ^k . Другими словами, ( S _a  |  a ∈ M ⁿ ) имеет бесконечную размерность Вапника–Червоненкиса .

Любая полная теория T , обладающая свойством независимости, нестабильна . ^[1]

В арифметике, т.е. структуре ( N ,+,·), формула " y делит x " имеет свойство независимости. ^[2] Эта формула просто

${\displaystyle (\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. ^[3] Этот факт нашел неожиданное применение в обучении нейронных сетей. ^[4]

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

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