NIP and NSOP
- Home of the stable theories.
NIP and SOP
- Most 'tame' ordered structures live here.
IP and NSOP
- Simple unstable theories live here.
- The non-simple theories in this region are stratified by the SOP_{n} hierarchy.
IP and SOP
- Part of the region is better understood by the study of NTP_{2}.
infinite sets
This theory has quantifier elimination, so definable sets (in one variable) are finite or cofinite.
See .
ACF
algebraically closed fields
Axiomatized by the field axioms (in \(\large \mathcal{L}=\{+,\cdot,0,1\}\)), and the infinite axiom scheme saying every polynomial has a root.
characterization of forking
The theory can be completed by specifying the characteristic. By quantifier elimination, definable sets (in one variable) are Boolean combinations of polynomial zerosets, and so finite or cofinite.
See .
\(\large \mathbb{Q}\)-vector spaces
By quantifier elimination, definable sets (in one variable) are given as Boolean combinations of formulas of the form nx = a, where n is an integer and a is an arbitrary element.
Since the group is torsion free, such sets are finite or cofinite.
See .
DCF_{0}
Shown to be ω-stable by Blum.
See .
everywhere infinite forest
- Models consist of infinitely many infinitely branching trees.
- Not strongly minimal as the set of neighbors of any one vertex is definable, infinite and coinfinite.
- Morley rank ω.
- Also referred to as the free pseudoplane.
See
,
.
\(\large (\mathbb{Z},+,0)\)
- Quantifier elimination after adding definable binary relations ≡_{n} for congruence modulo n.
- Superstable and not ω-stable (by type-counting).
See
.
finitely refining equivalence relations
Infinitely many equivalence relations E_{0}, E_{1},… such that E_{0} has two infinite classes, and each E_{n}-class is partitioned into two infinite E_{n+1} classes.
See , .
infinitely refining equivalence relations
Infinitely many equivalence relations
E_{0},
E_{1},… such that
E_{0} has infinitely many infinite classes, and each
E_{n}-class is partitioned into infinitely many infinite
E_{n+1} classes.
characterization of forking
See , .
DCF_{p}
Shown to be stable, but not superstable, by Shelah (1973).
See .
free group on n > 1 generators
Shown to be stable by Sela (2006) . Non-superstability was proved much earlier by Gibone, and communicated by Poizat (see also ).
RCF
real closed fields
Axiomatized by the ordered field axioms (in \( \mathcal{L}=\{+,\cdot,0,1,\lt\}\)), an axiom saying that every positive element has a square root, and an infinite axiom scheme saying every polynomial of odd degree has a root.
See .
\(\large (\mathbb{Z},\lt)\)
Theory of discrete linear orders.
See .
\(\large (\mathbb{Q},\lt)\)
Theory of dense linear orders without endpoints.
See .
\(\large (\mathbb{Z},+,\lt,0,1)\)
Also known as Presburger Arithmetic.
- Quantifier elimination after adding definable binary relations ≡_{n} for congruence modulo n.
- Not o-minimal since, e.g., 2\(\mathbb{Z}\) is not a finite union of intervals.
See
.
\(\large (\mathbb{Z},~x\mapsto x+1)\)
By quantifier elimination, definable sets (in one variable) are of Boolean combinations of formulas of the form x = a + n, where a is an arbitrary element and n is an integer.
Since successors are unique, such sets are finite or cofinite.
See .
ACVF
algebraically closed valued fields
See .
\(\large (\mathbb{Q}_p,+,\cdot,v(x)\geq v(y))\)
p-adic field with valuation
See .
random graph
Axiomatized in the graph language by sentences saying that if
A and
B are finite disjoint sets of vertices then there is a vertex connected to everything in
A and nothing in
B.
characterization of forking
- Forking independence is the same as algebraic independence and algebraic closure is trivial, so the theory is supersimple.
- Not stable since xRy has the order property.
See
,
.
pseudo-finite fields
A field F is pseudo-finite if every sentence (in the field language) true of F holds in some finite field.
See .
ACFA
See .
\(\large \mathbb{Q}\)ACFA
See .
ultraproduct of \(\large \mathbb{Q}_p\)
\(\large \mathbb{Q}_p\) denotes the field of p-adic numbers
See .
generic K_{n}-free graph
Axiomatized in the graph language by sentences stating that if
A and
B are finite disjoint sets of vertices, with
A K_{n-1}-free, then there is a vertex connected to everything in
A and nothing in
B.
characterization of forking
Given n ≥ 3, K_{n} denotes the complete graph on n vertices.
See , .
\(\large (\mathbb{Q},\textrm{cyc})\)
The cyclic order on the rationals is the ternary relation cyc(a,b,c), which holds if and only if a<b<c or b<c<a or c<a<b.
- This theory can be interpreted in a real closed field, and thus is NIP.
- The unique 1-type over ∅ forks over ∅, since it implies "x = 0 or x = 1 or cyc(0,x,1) or cyc(1,x,0)", and each disjunct divides over ∅.
See
.
SCFp
n
separably closed fields of characteristic p and Eršov invariant n ≤ ∞
- Given a separably closed field F of characteristic p, the Eršov invariant is \[\large n=[F:F^p]\in\mathbb{Z}^+\cup\{\infty\}.\]
- Shown to be stable by Macintyre, Shelah, and Wood (1975).
See
.
\(\large (\mathbb{R},+,\cdot,\lt,0,1,\textrm{exp})\)
the real exponential field
Shown to be o-minimal by Wilkie (1996).
See .
\(\large ((\mathbb{Z}/4\mathbb{Z})^\omega,+)\)
Totally categorical of Morley rank 2.
See , .
finitely cross-cutting equivalence relations
Infinitely many equivalence relations E_{0}, E_{1},… such that E_{0} has two infinite classes, and for all n < ω and I ⊆ {1,…,n}, the following axiom holds:
\[\large \forall x\exists y\bigwedge_{i=1}^nE_i(x,y)^{i\in I}\]
See .
universal bowtie-free graph
Complete theory of the universal and existentially closed countable graph omitting a 'bowtie' (sum of two triangles sharing a single vertex).
See , .
universal graph omitting odd cycles of length ≤ n
Given odd n ≥ 3, the complete theory of the universal and existentially closed countable graph omitting all odd cycles of length at most n.
See , .
universal directed graph omitting cycles of length ≤ n
Complete theory of the universal and existentially closed countable directed graph omitting directed cycles of length ≤ n.
See .
ZFC
Theory of set theory in the language \(\large \mathcal{L}=\{\in\}\).
\(\large (\mathbb{Z},+,\cdot,0,1)\)
Complete theory of the ring of integers (a completion of Peano Arithmetic).
\(\large (\mathbb{Q}^n,\lt_1,\ldots,\lt_n)\)
Complete theory of \(\large \mathbb{Q}^n\), for n > 1, with coordinate orderings. In particular, given \(\large x,y\in\mathbb{Q}^n\), set \[\large x\lt_i y ~\Leftrightarrow~ x_i\lt y_i. \]
- When n = 1, this is the theory of dense linear orders.
- Has dp-rank n.
See
.
Urysohn sphere
There are few options for what language to use for this structure. One is a relational language with binary relations \(\large d(x,y)\leq r\), for \(\large r\in \mathbb{Q}\cap[0,1]\).
Alternatively, consider the Urysohn sphere as a metric structure in continuous logic with the empty language.
See , .
free n^{th} root of the complete graph
This theory was originally defined with graph relations
R^{i} for 0 ≤
i ≤
n, where
R^{i}(x,y) holds if and only if
x and
y can be connected by a path of length
i.
The graph structure and metric structure can be identified via the equation
d(x,y) = min{i : R^{i}(x,y)}.
See
,
.
Hrushovski's new strongly minimal set
Hrushovski constructed an example of a strongly minimal theory, which is not locally modular and does not interpret an infinite group.
This disproved Zilber's conjecture that a strongly minimal theory must either be locally modular or interpret an infinite field.
See , .
infinitely cross-cutting equivalence relations
Infinitely many equivalence relations E_{0}, E_{1},… such that each E_{n} has infinitely many infinite classes, and for all m < n < ω every E_{n}-class intersects every E_{m}-class in an infinite set.
See .
non-simple generic limit of \(\large (\mathcal{K}_f,\leq)\) for good \(\large f\)
\(\large (\mathcal{K}_f,\leq)\) is a class of finite structures (in a finite relational language), which is closed under free amalgamation and is equipped with a predimension and a control function \(\large f\).
\(\large f\) is good if \(\large \mathcal{K}_f\) is closed under free \(\large \leq\)-amalgamation.
We consider the theory of the generic structure \(\large \mathcal{M}_f\). These theories are always NSOP_{4}, and the non-simple case is always SOP_{3} and TP2.
The simple case can also be characterized by the closure of \(\large \mathcal{K}_f\) under independence theorem diagrams.
See .
VFA_{0}
The limit theory (as p→∞) of the Frobenius automorphism acting on an algebraically closed valued field of characteristic p.
See .
atomless Boolean algebras
The theory of the Fraissé limit of Boolean algebras in the language \(\large \{0,1,\neg,\wedge,\vee\}\).
See .
generic Kr
n-free r-graph
See .
a strictly stable superflat graph
Given integers
m and
n, let
Km
n be the class of graphs obtained
from the complete graph on
n vertices by replacing each edge with a path containing at most
m new vertices.
A graph
G is
superflat if for all
m there is some
n such that
G omits
Km
n.
G is
ultraflat if there is some
n such that for all
m,
G omits
Km
n.
Define the following strictly stable superflat graph. Begin with vertex set ω
^{<ω}∪ω
^{ω}. For each σ in ω
^{ω}
and
m < ω, add a path from σ to σ|
m containing
m new vertices.
characterization of forking
Any superflat graph is stable; any ultraflat graph (and so any planar graph) is superstable.
The graph above interprets infinitely refining equivalence relations, and so is strictly stable.
See , , .
imperfect bounded PAC fields
A variety over a field
K is
absolutely irreducible if it is not the union of two algebraic sets over an algebraically closed extension of
K.
A field
K is
pseudo-algebraically closed (PAC) if every absolutely irreducible variety defined over
K has a
K-rational point.
K is
perfect if either
char(K)=0 or
K^{char(K)} =
K.
K is
bounded if for all
n > 1,
K has finitely many separably algebraic extensions of degree
n.
characterization of forking
If K is a PAC field then Th(K) is simple if and only if K is bounded. The theory of a perfect bounded PAC field is supersimple.
See , , .
T_{feq}
Consider the language \(\large \mathcal{L}=\{P,Q,E\}\), where \(\large P,Q\) are unary relations and \(\large E\) is a ternary relation.
T_{feq} is the model completion of the following theory:
- \(\large P\) and \(\large Q\) form a partition.
- For all \(\large a\) in \(\large P\), \(\large E(a,x,y)\) is an equivalence relation on \(\large Q\).
Shown to be NSOP_{1} in (this was first claimed in , but errors were found in the proof). See also , , .
ω-free PAC fields
A variety over a field
K is
absolutely irreducible if it is not the union of two algebraic sets over an algebraically closed extension of
K.
A field
K is
pseudo-algebraically closed (PAC) if every absolutely irreducible variety defined over
K has a
K-rational point.
A PAC field
K is
ω-free if there is an elementary substructure
L of
K, whose absolute Galois group
Aut(L^{sep}/L) is isomorphic to \(\large \hat{F}_\omega\), which is defined below.
Let \(\large F_\omega\) be the free group on countably many generators. Let \(\large \mathcal{N}\) be the family of normal, finite-index subgroups of \(\large F_\omega\) containing cofinitely many generators. Then
\[\large \hat{F}_{\!\omega}=\varprojlim_{N\in\mathcal{N}}F_\omega/N\]
characterization of forking
Shown to be NSOP_{1} in . See also , , .
infinite-dimensional vector spaces with a bilinear form
Defined in the 2-sorted language of vector spaces over an algebraically closed field.
Shown to be NSOP_{1} in . See also , .
densely ordered random graph
Model completion of the theory of ordered graphs.
See , .
bounded pseudo real closed fields
A field K, of characteristic 0, is bounded if, for every n, K has only finitely many extensions of degree n.
A variety over a field K is absolutely irreducible if it is not the union of two algebraic sets over an algebraically closed extension of K.
A field K is pseudo real closed if, for every absolutely irreducible variety V defined over K,
if V has a K^{r}-rational point for every real closure K^{r} of K,
then V has a K-rational point.
We assume here that the pseudo real closed field K is not real closed or algebraically closed, which ensures the independence property, and also that K has at least one order, which ensures the strict order property (a pseudo real closed field with no orders is pseudo algebraically closed).
See .
\(\large (\mathbb{Z}^{\omega},+,0)\)
For a fixed prime p, the subgroups H_{n} of elements divisible by p^{n}, for n ≥ 0,
form a descending chain of definable subgroups, each of which is infinite index in the previous.
Therefore the theory is strictly stable.
See , .
\(\large (\mathbb{Z},+,0,\Gamma)\)
Complete theory of the abelian group \(\large (\mathbb{Z},+,0)\) expanded by a predicate for a fixed finitely generated multiplicative submonoid \(\large \Gamma\) of \(\large \mathbb{Z}^+\).
Superstable of U-rank ω, and not dp-minimal.
See or for the case of one generator, and for the general case.
The failure of dp-minimality can be established using an elementary direct argument similar to Proposition 2.7 of . More generally, by , there are no proper stable expansions of \(\large (\mathbb{Z},+,0)\) with finite dp-rank.
extra-special p-group
Given an odd prime
p, there is a group
G satisfying the following properties:
- G is infinite,
- every nontrivial element of G has order p,
- Z(G) is cyclic of order p and equals G'.
Such a group
G is called an
extra-special p-group. The defining properties are expressible in the language of groups, and determine a complete theory.
Supersimple of SU-rank 1, and unstable.
See .
\(\large (\mathbb{T},+,\cdot,0,1,\partial,\leq,\preccurlyeq)\)
ordered valued differential field of logarithmic-exponential transseries
\(\large \mathbb{T}\) is a model of the theory T^{nl} of ω-free newtonian Liouville closed H-fields, which is the model companion of the theory of H-fields. The theory T^{nl} has two completions: one with small derivation of which \(\large \mathbb{T}\) is a model, and one which does not have small derivation.
Both completions of T^{nl} are NIP, unstable, and not dp-minimal.
See .
\(\large (\mathbb{Z},+,\le_p,0,1)\)
Given a prime p, let ≤_{p} denote the pre-order on integers induced from the p-valuation: x≤y if and only if v_{p}(x)≤v_{p}(y).
- Dp-minimal, unstable, and not o-minimal.
- Expanding by the preorders associated to n distinct primes yields dp-rank n.
- Distality fails since the quotient by the equivalence relation defined from the pre-order is stably embedded and has the structure of ℕ with successor.
See
.
\(\large (\mathbb{Z},+,0,\text{Sqf})\)
Complete theory of the abelian group \(\large (\mathbb{Z},+,0)\) expanded by a predicate for the set Sqf of squarefree integers.
Supersimple of SU-rank 1 and unstable.
See
. This result builds on
which, assuming
Dickson's Conjecture, gives the same classification of the expansion of \(\large (\mathbb{Z},+,0)\) by a predicate for the primes and their negatives.
multicolored directed graphs omitting directed cycles
Consider a language with countably many binary relation symbols (R_{n}). Let T be the model completion of the theory expressing that each R_{n} is a directed graph relation with no directed n-cycles.
TP_{2}, NSOP and SOP_{∞}.
See .
\(\large (\mathbb{N},\cdot)\)
Also known as Skolem Arithmetic.
Skolem arithmetic is decidable.
See .
generic binary function
Given a first-order language \(\large \mathcal{L}\), the empty \(\large \mathcal{L}\)-theory has a model completion,
T_{0}, whose completions are determined by specifying the diagram of the constant symbols in \(\large \mathcal{L}\). Suppose
T is a completion of
T_{0}. Then:
- T is NSOP_{1}.
- If \(\large \mathcal{L}\) contains a function symbol of arity at least 2, then T is not simple.
- If \(\large \mathcal{L}\) contains a relation symbol of arity at least 2, then T is unstable.
See
.
generic K_{m,n}-free bipartite graph
This theory is considered in the language of bipartite graphs consisting of a binary graph relation I, together with unary predicates P and L for the bipartition. Alternatively, one can view P and L as sorts for abstract points and lines, and I as an incidence relation. For example, if m = n = 2, then this is the model completion of the theory of combinatorial projective planes.
See .
Henson digraphs
Given a set F of finite tournaments, the the class of F-free directed graphs is a Fraïssé class with ℵ_{0}-categorical Fraïssé limit.
Constructed by Henson to exhibit continuum many pairwise nonisomorphic homogeneous directed graphs.
See .
\(\large (\mathbb{R},+,\cdot,2^{\mathbb{Q}})\)
The real field expanded by a predicate for \(\large 2^{\mathbb{Q}}\).
One can replace \(\large 2^{\mathbb{Q}}\) by any dense subgroup of \(\large \mathbb{R}^+\) with the Mann property, or by a dense transcendence basis for \(\large \mathbb{R}\).
See .
generic Steiner triple system
The Fraïssé limit of Steiner triple systems in the language of quasigroups.
A Steiner triple system is a set X together with a collection B of three-element subsets of X (called "blocks"), with the property that any two elements of X lie in a unique block in B. If X is a Steiner triple system, then there is a quasigroup operation on X, which sends pairs (x,x) to x, and sends pairs (x,y), with x and y distinct, to the third point on the block determined by x and y.
See .
a non-definably-amenable group in a simple theory
Let
K be an algebraically closed field of characteristic zero. Then there is a partition
SL_{2}(K) = C_{1} ∪ C_{2} ∪ C_{3} ∪ C_{4}
such that the theory of
G := (SL_{2}(K),⋅,C_{1},C_{2},C_{3},C_{4})
is supersimple, and for all 1≤
i≤4, SL
_{2}(
K) can be covered by three left translates of
C_{i}.
The conditions on the
C_{i}'s imply that there is no left-invariant finitely additive probability measure on the definable subsets of
G, i.e.,
G is not definably amenable.
See .
ACF_{p}G
Generic expansion of the theory of algebraically closed fields of characteristic p > 0 by an additive subgroup.
This theory is the model companion of ACF_{p} expanded by a predicate for an additive subgroup.
See .
\(\large (\mathbb{C}(t),+,\cdot,0,1)\)
The field of rational functions over the complex numbers.
This field is not superstable, since any infinite superstable field is algebraically closed ; and it is not dp-minimal (see for a classification of dp-minimal fields). The stable fields conjecture asserts that every infinite stable field is separably closed. \(\large \mathbb{C}(t)\) has become a canonical test case for this conjecture.
list of open examples
Farey graph
The vertex set of the Farey graph is the projective rational line (i.e., all rational numbers, and a point at infinity identified as 1/0). Two vertices
a/
b and
c/
d (in lowest terms) are connected by an edge if and only if |
ad -
bc| = 1.
picture of the Farey graph
characterization of forking
This graph is planar, and thus ultraflat, which implies it is superstable and dp-minimal. It is not strongly minimal since every vertex has an infinite and co-infinite neighborhood. For ω-stability, see .
See , , .
Artin braid groups
Given n > 2, the braid group B_{n} is the group with the following presentation
\( \langle x_1,\ldots,x_{n-1}\mid x_ix_{i+1}x_i=x_{i+1}x_ix_{i+1}\rangle\)
The center of B_{n} is an infinite cylic group, and thus B_{n} is not ω-stable. B_{n} contains the free group on 2 generators as a subgroup, and thus is not dp-minimal. It also unknown whether B_{m} and B_{n} are elementarily equivalent when m ≠ n.
list of open examples
a strictly stable expansion of \(\large (\mathbb{Z},+,0)\)
Let \(\large Q\) be the set of factorials and let \(\large \mathcal{Q}\) be an arbitrary structure with universe \(\large Q\). Consider the expansion \(\large (\mathbb{Z},+,0,\mathcal{Q})\) of \(\large (\mathbb{Z},+,0)\) obtained by naming \(\large Q\) with a unary predicate and enriching it with the structure \(\large \mathcal{Q}\). Then \(\large (\mathbb{Z},+,0,\mathcal{Q})\) is strictly stable if and only if \(\large \mathcal{Q}\) is. (The same holds for superstable, NIP, NTP_{2}, simple, and NSOP_{1}.)
See .
One can accomplish this with an expansion by a single unary predicate as follows. Suppose \(\large \mathcal{Q}\) is a graph \(\large (Q,E)\). Define
\[\large
A=Q\cup \{x+y:(x,y)\in E\}.
\]
Then \(\large (\mathbb{Z},+,0,A)\) is interdefinable with \(\large (\mathbb{Z},+,\mathcal{Q})\). For a strictly stable example, let \(\large \mathcal{Q}\) be a countable model of the graph defined here. Or one can construct a graph bi-interpretable with any given structure in a finite language (see Theorem 5.5.1 in ).
The failure of dp-minimality (which happens even in the reduct \(\large (\mathbb{Z},+,0,Q)\)) can be established using an elementary direct argument similar to Proposition 2.7 of . More generally, by , there are no proper stable expansions of \(\large (\mathbb{Z},+,0)\) with finite dp-rank.
strongly minimal
o-minimal
ω-stable, dp-minimal, and not strongly minimal
superstable, dp-minimal, and not ω-stable
stable, dp-minimal, and not superstable
dp-minimal, distal, and not o-minimal
NIP, SOP, dp-minimal, and not distal
NIP and SOP, but not dp-minimal or distal
IP, SOP, NTP_{2}
supersimple and unstable
simple and unstable, but not supersimple
NTP_{2}, TP_{1} (SOP_{1}/SOP_{2}), and NSOP_{3}
It is unknown whether the implication SOP_{3} ⇒ TP_{1} is strict.
NTP_{2}, SOP_{3}, and NSOP_{4}
It is unknown whether the strong order property hierarchy is strict inside NTP_{2}.
NTP_{2}, SOP_{n}, and NSOP_{n+1} for some n ≥ 4
It is unknown whether the strong order property hierarchy is strict inside NTP_{2}.
NTP_{2}, NFSOP, and SOP_{n} for all
n ≥ 3
It is unknown whether the strong order property hierarchy is strict inside NTP_{2}.
NTP_{2}, NSOP, and FSOP
It is unknown whether the strong order property hierarchy is strict inside NTP_{2}.
NTP_{1} (NSOP_{1}/NSOP_{2}) and TP_{2}
TP_{2}, TP_{1} (SOP_{1}/SOP_{2}), and NSOP_{3}
It is unknown whether the implication SOP_{3} ⇒ TP_{1} is strict.
TP_{2}, SOP_{3}, and NSOP_{4}
TP_{2}, SOP_{n}, and NSOP_{n+1} for some n ≥ 4
To keep this section distinct from the others, we assume n ≥ 4.
However every known example of a theory that is SOP_{n} and NSOP_{n+1} for some n ≥ 4, has some analogue for any n ≥ 3.
TP_{2}, NFSOP, and SOP_{n} for all
n ≥ 3
TP_{2}, FSOP, and NSOP
TP_{2} and SOP
distal and not dp-minimal
ω-stable, and not dp-minimal
superstable, not ω-stable, and not dp-minimal
stable, not superstable, and not dp-minimal