NIP (modellteori)

I modellteori , en gren av matematisk logik , sägs en komplett teori T uppfylla NIP ("inte oberoendeegenskapen") om ingen av dess formler uppfyller oberoendeegenskapen - det vill säga om ingen av dess formler kan välja ut någon given delmängd av en godtyckligt stor ändlig mängd.

Definition

₀ Låt T vara en fullständig L -teori. En L -formel φ( x , y ) sägs ha oberoendeegenskapen (med avseende på x , y ) om det i varje modell M av T finns, för varje n = {0,1,…, n − 1} < ω, en familj av tuplar b ,..., b _{n −1} så att det för var och en av de 2 ⁿ delmängderna X av n finns en tupel a i M för vilken

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

Teorin T sägs ha egenskapen oberoende om någon formel har egenskapen oberoende. Om ingen L -formel har egenskapen oberoende kallas T beroende, eller sägs uppfylla NIP. En L -struktur sägs ha oberoendeegenskapen (respektive NIP) om dess teori har oberoendeegenskapen (respektive NIP). Terminologin kommer från begreppet oberoende i betydelsen booleska algebror .

I nomenklaturen för Vapnik–Chervonenkis teori kan vi säga att en samling S av delmängder av X splittrar en mängd B ⊆ X om varje delmängd av B är av formen B ∩ S för vissa S ∈ S . Då T oberoendeegenskapen om det i någon modell M av T finns en definierbar familj ( S _a | a ∈ M ⁿ ) ⊆ M ^k som splittrar godtyckligt stora ändliga delmängder av M ^k . Med andra ord, ( S _a | a ∈ M ⁿ ) har oändlig Vapnik–Chervonenkis dimension .

Exempel

Varje komplett teori T som har egenskapen oberoende är instabil .

I aritmetiken, dvs strukturen ( N ,+,·), har formeln " y delar x " egenskapen oberoende. Denna formel är bara

$(\exists k)(y\cdot k=x).$

Så för alla ändliga n tar vi n 1-tuplarna b _i att vara de första n primtalen , och sedan låter vi för varje delmängd X av {0,1,..., n − 1} a vara produkten av dessa b _i sådan att jag är i X . Då delar b _i a om och endast om i ∈ X .

Varje o-minimal teori uppfyller NIP. Detta faktum har haft oväntade tillämpningar för neurala nätverksinlärning.

Exempel på NIP-teorier inkluderar också teorierna för alla följande strukturer: linjära ordningar , träd , abelska linjärt ordnade grupper , algebraiskt slutna värderade fält och det p-adiska fältet för alla p.

Anteckningar

•   Anthony, Martin; Bartlett, Peter L. (1999). Neuralt nätverkslärande: teoretiska grunder . Cambridge University Press . ISBN 978-0-521-57353-5 .
•   Hodges, Wilfrid (1993). Modellteori . Cambridge University Press . ISBN 978-0-521-30442-9 .
•   Riddare, Julia ; Pillay, Anand; Steinhorn, Charles (1986). "Definierbara uppsättningar i ordnade strukturer II" . Transaktioner från American Mathematical Society . 295 (2): 593–605. doi : 10.2307/2000053 . JSTOR 2000053 .
•   Pillay, Anand; Steinhorn, Charles (1986). "Definierbara uppsättningar i ordnade strukturer I" . Transaktioner från American Mathematical Society . 295 (2): 565–592. doi : 10.2307/2000052 . JSTOR 2000052 .
•   Poizat, Bruno (2000). En kurs i modellteori . Springer. ISBN 978-0-387-98655-5 .
•   Simon, Pierre (2015). En guide till NIP-teorier . Cambridge University Press. ISBN 9781107057753 .