NIP (teoría del modelo)

En la teoría de modelos , una rama de la lógica matemática , se dice que una teoría completa T satisface NIP ("no la propiedad de independencia") si ninguna de sus fórmulas satisface la propiedad de independencia , es decir, si ninguna de sus fórmulas puede seleccionar una determinada subconjunto de un conjunto finito arbitrariamente grande.

Definición

Sea T una teoría L completa . Se dice que una fórmula L φ( x , y ) tiene la propiedad de independencia (con respecto a x , y ) si en todo modelo M de T existe, para cada n  = {0,1,..., n  − 1} < ω, una familia de tuplas b ₀ ,..., b _{n −1} tal que para cada uno de los 2 ⁿ subconjuntos X de n existe una tupla a en M para la cual

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

Se dice que la teoría T tiene la propiedad de independencia si alguna fórmula tiene la propiedad de independencia. Si ninguna fórmula L tiene la propiedad de independencia, entonces T se llama dependiente o se dice que satisface NIP. Se dice que una estructura L tiene la propiedad de independencia (respectivamente, NIP) si su teoría tiene la propiedad de independencia (respectivamente, NIP). La terminología proviene de la noción de independencia en el sentido de las álgebras booleanas .

En la nomenclatura de la teoría de Vapnik-Chervonenkis , podemos decir que una colección S de subconjuntos de X destroza un conjunto B  ⊆  X si cada subconjunto de B es de la forma B  ∩  S para algún S  ∈  S . Entonces T tiene la propiedad de independencia si en algún modelo M de T hay una familia definible ( S _a  |  a ∈ M ⁿ ) ⊆  M ^k que destruye subconjuntos finitos arbitrariamente grandes de M ^k . En otras palabras, ( S _a  |  a ∈ M ⁿ ) tiene dimensión infinita de Vapnik-Chervonenkis .

Ejemplos

Cualquier teoría completa T que tenga la propiedad de independencia es inestable . ^[1]

En aritmética, es decir, en la estructura ( N ,+,·), la fórmula " y divide x " tiene la propiedad de independencia. ^[2] Esta fórmula es solo

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

Entonces, para cualquier n finito tomamos las n 1-tuplas b _i como los primeros n números primos , y luego para cualquier subconjunto X de {0,1,..., n  − 1} dejamos que a sea el producto de esos b _i tales que i está en X . Entonces b _i divide a si y sólo si i  ∈  X .

Cada teoría o-mínimo satisface NIP. ^[3] Este hecho ha tenido aplicaciones inesperadas para el aprendizaje de redes neuronales. ^[4]

Ejemplos de teorías NIP incluyen también las teorías de todas las estructuras siguientes: ^[5] órdenes lineales , árboles , grupos abelianos ordenados linealmente, campos de valores algebraicamente cerrados y el campo p-ádico para cualquier p.

Notas

1. Ver Hodges.
2. Ver Poizat, página 249.
3. Pillay y Steinhorn, corolario 3.10 y Knight, Pillay y Steinhorn, teorema 0.2.
4. Consulte Anthony y Bartlett para obtener más detalles.
5. Ver Simón, Apéndice A.

Referencias

• Antonio, Martín; Bartlett, Peter L. (1999). Aprendizaje de redes neuronales: fundamentos teóricos . Prensa de la Universidad de Cambridge . ISBN 978-0-521-57353-5.
• Hodges, Wilfrid (1993). Teoría de modelos . Prensa de la Universidad de Cambridge . ISBN 978-0-521-30442-9.
• Caballero, Julia ; Pillay, Anand; Steinhorn, Charles (1986). "Conjuntos definibles en estructuras ordenadas II". Transacciones de la Sociedad Matemática Estadounidense . 295 (2): 593–605. doi : 10.2307/2000053 . JSTOR  2000053.
• Pillay, Anand; Steinhorn, Charles (1986). "Conjuntos definibles en estructuras ordenadas I". Transacciones de la Sociedad Matemática Estadounidense . 295 (2): 565–592. doi : 10.2307/2000052 . JSTOR  2000052.
• Poizat, Bruno (2000). Un curso de teoría de modelos . Saltador. ISBN 978-0-387-98655-5.
• Simón, Pierre (2015). Una guía de teorías NIP . Prensa de la Universidad de Cambridge. ISBN 9781107057753.