NIP (model theory)

In model theory, a branch of mathematical logic, a complete theory T is said to satisfy NIP (or "not the independence property") if none of its formulae satisfy the independence property, that is if none of its formulae can pick out any given subset of an arbitrarily large finite set.
Contents
Definition
Let T be a complete Ltheory. An Lformula φ(x,y) is said to have the independence property (with respect to x, y) if in every model M of T there is, for each n = {0,1,…n − 1} < ω, a family of tuples b_{0},…,b_{n−1} such that for each of the 2^{n} subsets X of n there is a tuple a in M for which
The theory T is said to have the independence property if some formula has the independence property. If no Lformula has the independence property then T is called dependent, or said to satisfy NIP. An Lstructure is said to have the independence property (respectively, NIP) if its theory has the independence theory (respectively, NIP). The terminology comes from the notion of independence in the sense of boolean algebras.
In the nomenclature of Vapnik–Chervonenkis theory, we may say that a collection S of subsets of X shatters a set B ⊆ X if every subset of B is of the form B ∩ S for some S ∈ S. Then T has the independence property if in some model M of T there is a definable family (S_{a}  a∈M^{n}) ⊆ M^{k} that shatters arbitrarily large finite subsets of M^{k}. In other words, (S_{a}  a∈M^{n}) has infinite Vapnik–Chervonenkis dimension.
Examples
Any complete theory T that has the independence property is unstable.^{[1]}
In arithmetic, i.e. the structure (N,+,·), the formula "y divides x" has the independence property.^{[2]} This formula is just
So, for any finite n we take the n 1tuples b_{i} to be the first n prime numbers, and then for any subset X of {0,1,…n − 1} we let a be the product of those b_{i} such that i is in X. Then b_{i} divides a if and only if i ∈ X.
Every ominimal theory satisfies NIP.^{[3]} This fact has had unexpected applications to neural network learning.^{[4]}
Notes
References
 Anthony, Martin; Bartlett, Peter L. (1999). Neural network learning: theoretical foundations. Cambridge University Press. ISBN 052157353X.
 Hodges, Wilfrid (1993). Model theory. Cambridge University Press. ISBN 0521304423.
 Knight, Julia; Pillay, Anand; Steinhorn, Charles (1986). "Definable sets in ordered structures II". Transactions of the American Mathematical Society 295 (2): 593–605. doi:10.2307/2000053.
 Pillay, Anand; Steinhorn, Charles (1986). "Definable sets in ordered structures I". Transactions of the American Mathematical Society 295 (2): 565–592.
 Poizat, Bruno (2000). A Course in Model Theory. Springer. ISBN 0387986553.
Categories:
Wikimedia Foundation. 2010.
Look at other dictionaries:
Theory of relations — This article is about the theory of relations with regard to its specifically combinatorial aspects. For a general discussion of the basic definitions, see Binary relation and Finitary relation. The theory of relations treats the subject matter… … Wikipedia
HEBREW LANGUAGE — This entry is arranged according to the following scheme: pre biblical biblical the dead sea scrolls mishnaic medieval modern period A detailed table of contents precedes each section. PRE BIBLICAL nature of the evidence the sources phonology… … Encyclopedia of Judaism
HEBREW GRAMMAR — The following entry is divided into two sections: an Introduction for the non specialist and (II) a detailed survey. [i] HEBREW GRAMMAR: AN INTRODUCTION There are four main phases in the history of the Hebrew language: the biblical or classical,… … Encyclopedia of Judaism
United Kingdom — a kingdom in NW Europe, consisting of Great Britain and Northern Ireland: formerly comprising Great Britain and Ireland 1801 1922. 58,610,182; 94,242 sq. mi. (244,100 sq. km). Cap.: London. Abbr.: U.K. Official name, United Kingdom of Great… … Universalium
Double bind — Not to be confused with double blind, a method to eliminate bias in scientific experimentation. A double bind is an emotionally distressing dilemma in communication in which an individual (or group) receives two or more conflicting messages, in… … Wikipedia
Newton Howard — Dr. Newton Howard is the founder and chairman of the Center for Advanced Defense Studies, a Washington, D.C. National Security Group. He is a leading international researcher on the physics of cognition (PoC) and its applications to defense and… … Wikipedia
Список американских телепрограмм по дате начала показа — Содержание 1 2010 е 1.1 2011 1.1.1 Январь 1.1.2 Февраль … Википедия
Список телесериалов по наименованию — Содержание 1 Русскоязычные 2 На других языках 3 0 9 4 Латиница … Википедия
Australia — /aw strayl yeuh/, n. 1. a continent SE of Asia, between the Indian and the Pacific oceans. 18,438,824; 2,948,366 sq. mi. (7,636,270 sq. km). 2. Commonwealth of, a member of the Commonwealth of Nations, consisting of the federated states and… … Universalium
Narcissism — Narcissus by Caravaggio (Galleria Nazionale d Arte Antica, Rome) Narcissism is a term with a wide range of meanings, depending on whether it is used to describe a central concept of psychoanalytic theory, a mental illness, a social or cultural… … Wikipedia