WikiDer > НИП (теория моделей)

NIP (model theory)

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

Определение

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

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

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

Примеры

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

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

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

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

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

Заметки

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

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