НИП (теория моделей) - NIP (model theory)

В теория моделей, филиал математическая логика, полная теория Т Говорят, что удовлетворяет НИП (или «не свойство независимости»), если ни одна из его формул не удовлетворяет независимая собственность, то есть если ни одна из его формул не может выделить любое заданное подмножество сколь угодно большого конечного множества.

Определение

Позволять Т быть полный L-теория. An L-формула φ (Икс,у), как говорят, обладает свойством независимости (относительно Икс, у) если в каждой модели M из Т есть для каждого п = {0,1,…,п - 1} <ω семейство кортежи б₀,…,б_п−1 такой, что для каждого из 2^п подмножества Икс из п есть кортеж а в M для которого

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

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

В номенклатуре Теория Вапника – Червоненкиса. можно сказать, что коллекция S подмножеств Икс разбивается множество B ⊆ Икс если каждое подмножество B имеет форму B ∩ S для некоторых S ∈ S. потом Т обладает свойством независимости, если в какой-либо модели M из Т есть определимая семья (S_а | а∈M^п) ⊆ M^k который разрушает сколь угодно большие конечные подмножества M^k. Другими словами, (S_а | а∈M^п) имеет бесконечное Размерность Вапника – Червоненкиса.

Примеры

Любая полная теория Т обладающий свойством независимости неустойчивый.^[1]

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

${\displaystyle (\exists k)(y\cdot k=x).}$

Итак, для любого конечного п мы берем п 1-кортежи б_я быть первым п простые числа, а затем для любого подмножества Икс из {0,1,…,п - 1} мы позволяем а быть продуктом тех б_я такой, что я в Икс. потом б_я разделяет а если и только если я ∈ Икс.

Каждые о-минимальная теория удовлетворяет НИП.^[3] Этот факт неожиданно нашел применение в обучении нейронных сетей.^[4]

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

Заметки

1. См. Ходжеса.
2. См. Poizat, стр. 249.
3. Пиллэй и Стейнхорн, следствие 3.10, и Найт, Пиллэй и Стейнхорн, теорема 0.2.
4. См. Подробности у Энтони и Бартлетта.
5. См. Саймон, Приложение A.

использованная литература

• Энтони, Мартин; Бартлетт, Питер Л. (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.
• Poizat, Бруно (2000). Курс теории моделей. Springer. ISBN  978-0-387-98655-5.
• Саймон, Пьер (2015). Руководство по теории НПВ. Издательство Кембриджского университета. ISBN  9781107057753.