NIP（モデル理論）

数理論理学の一分野であるモデル理論では、完全な理論Tは、その理論の式のいずれもが独立性を満たさない場合、つまり、その理論の式のいずれもが、任意の大きさの有限集合の任意の部分集合を取り出すことができない場合、 NIP (「独立性ではない」)を満たすと言われます。

T を完全な L理論とする。L論理式 φ( x , y ) が独立性 ( x , yに関して) を持つとは、 TのすべてのモデルMにおいて、各n =  {0,1,..., n − 1} < ω に対して、組b ₀ ,..., b _{n −1} の族が存在し、 nの2 ^{n 個}の部分集合Xのそれぞれに対して、 Mに組aが存在し、

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

何らかの式が独立性を持つ場合、理論T は独立性を持つと言われます。独立性を持つL式がない場合、Tは従属的である、または NIP を満たすと言われます。L構造は、その理論が独立性 (それぞれ NIP) を持つ場合、独立性 (それぞれ NIP) を持つと言われます。この用語は、ブール代数の意味での独立性の概念に由来します。

ヴァプニク・チェルヴォネンキス理論の命名法では、 XのサブセットのコレクションSが集合B  ⊆  X を破壊するとは、 Bのすべてのサブセットが、何らかのS  ∈  Sに対してB  ∩  S の形式であると言うことができます。このとき、Tの何らかのモデルMに、 M ^kの任意に大きな有限サブセットを破壊する定義可能な族 ( S _a  |  a ∈ M ⁿ ) ⊆  M ^kが存在する場合、 Tは独立性を持ちます。 言い換えると、 ( S _a  |  a ∈ M ⁿ ) は無限のヴァプニク・チェルヴォネンキス次元を持ちます。

独立性を持つ完全な理論Tは不安定である。^[1]

算術、すなわち構造（N 、+、·）において、「 yはxを割る」という式は独立性を持つ。^[2] この式は

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

したがって、任意の有限nに対して、 n個の 1 組bi_を最初のn 個の素数とし、{0,1,..., n  − 1}の任意の部分集合Xに対して、 i が_Xに含まれるようなbiの積をaとします。すると、i  ∈  Xの場合にのみ、bi_がa を割り切ります。

すべてのO極小理論はNIPを満たす。^[3] この事実はニューラルネットワーク学習に予想外の応用があった。^[4]

NIP理論の例には、以下のすべての構造の理論も含まれます: ^[5] 線型順序、木、アーベル線型順序群、代数的に閉じた値体、および任意のpに対するp進体。

• アンソニー、マーティン、バートレット、ピーター L. (1999)。ニューラルネットワーク学習：理論的基礎。ケンブリッジ大学出版局。ISBN 978-0-521-57353-5。
• ホッジス、ウィルフリッド（1993）。モデル理論。ケンブリッジ大学出版局。ISBN 978-0-521-30442-9。
• ナイト、ジュリア; ピレイ、アナンド; スタインホーン、チャールズ (1986) 。「順序構造における定義可能集合 II」。アメリカ数学会誌。295 (2): 593–605。doi : 10.2307/2000053。JSTOR  2000053 。
• Pillay, Anand; Steinhorn, Charles (1986). 「順序構造における定義可能集合 I」.アメリカ数学会誌. 295 (2): 565–592. doi : 10.2307/2000052 . JSTOR  2000052.
• ポイザット、ブルーノ（2000）。モデル理論講座。シュプリンガー。ISBN 978-0-387-98655-5。
• サイモン、ピエール（2015）。NIP理論ガイド。ケンブリッジ大学出版局。ISBN 9781107057753。