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 \(\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 .
\(\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
,
.
\((\mathbb{Z},+,0,1)\)
- 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, but not superstable, by Sela (2006).
See .
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 .
\((\mathbb{Z},\lt)\)
Theory of discrete linear orders.
See .
\((\mathbb{Q},\lt)\)
Theory of dense linear orders.
See .
\((\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
.
\((\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 .
\((\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 .
\(\mathbb{Q}\)ACFA
See .
ultraproduct of \(\mathbb{Q}_p\)
\(\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 , .
\((\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 of these disjuncts 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 \[n=[F:F^p]\in\mathbb{Z}^+\cup\{\infty\}.\]
- Shown to be stable by Macintyre, Shelah, and Wood (1975).
See
.
\((\mathbb{R},+,\cdot,\lt,0,1,\textrm{exp})\)
the real exponential field
Shown to be o-minimal by Wilkie (1996).
See .
\(((\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:
\[\forall x\exists y\left(\bigwedge_{i\in I}E_i(x,y)\wedge\bigwedge_{i\in n\backslash I}\neg E_i(x,y)\right)\]
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 \(\mathcal{L}=\{\in\}\).
\((\mathbb{Z},+,\cdot,0,1)\)
Complete theory of the ring of integers (a completion of Peano Arithmetic).
\((\mathbb{Q}^n,\lt_1,\ldots,\lt_n)\)
Complete theory of \(\mathbb{Q}^n\), for n > 1, with coordinate orderings. In particular, given \(x,y\in\mathbb{Q}^n\), set \[x\lt_i y ~\Leftrightarrow~ x_i\lt y_i. \]
- When n = 1, this is 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 to use distance relations \(d(x,y)\leq r\), for \(r\in\mathbb{Q}\).
Alternatively, one consider the Urysohn sphere as a metric structure in continuous logic.
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 thought of as the same via
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 n < ω each E_{n+1} class splits each E_{n} class into infinitely many pieces.
See .
non-simple generic limit of \((\mathcal{K}_f,\leq)\) for good \(f\)
\((\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 \(f\).
\(f\) is good if \(\mathcal{K}_f\) is closed under free \(\leq\)-amalgamation.
We consider the theory of the generic structure \(\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 \(\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 \(\{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 defined over a field
K is
absolutely irreducible if it is not the union of two algebraic sets defined over some 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 it has characteristic 0, or if
K has characteristic
p then
K^{p} =
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 \(\mathcal{L}=\{P,Q,E\}\), where \(P,Q\) are unary relations and \(E\) is a ternary relation.
T_{feq} is the model completion of the following theory:
- \(P\) and \(Q\) form a partition.
- For all \(a\) in \(P\), \(E(a,x,y)\) is an equivalence relation on \(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 defined over a field
K is
absolutely irreducible if it is not the union of two algebraic sets defined over some 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 \(\hat{F}_\omega\), which is defined below.
Let \(F_\omega\) be the free group on countably many generators. Let \(\mathcal{N}\) be the family of normal, finite-index subgroups of \(F_\omega\) containing cofinitely many generators. Then
\[\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 defined over a field K is absolutely irreducible if it is not the union of two algebraic sets defined over some 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 .
\((\mathbb{Z}^{\omega},+,0)\)
Complete theory of the abelian group \((\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 , .
\((\mathbb{Z},+,0,\Gamma)\)
Complete theory of the abelian group \((\mathbb{Z},+,0)\) expanded by a predicate for a fixed finitely generated multiplicative submonoid \(\Gamma\) of \(\mathbb{Z}^+\).
Superstable of U-rank ω, and not dp-minimal.
See , for the case of one generator, and for the general case.
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 .
\((\mathbb{T},+,\cdot,0,1,\partial,\leq,\preccurlyeq)\)
ordered valued differential field of logarithmic-exponential transseries
\(\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 \(\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 .
\((\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.
See
.
\((\mathbb{Z},+,0,\text{Sqf})\)
Complete theory of the abelian group \((\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 \((\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 .
\((\mathbb{N},\cdot)\)
Also known as Skolem Arithmetic.
Skolem arithmetic is decidable.
See .
generic binary function
Given a first-order language \(\mathcal{L}\), the empty \(\mathcal{L}\)-theory has a model completion,
T_{0}, whose completions are determined by specifying the diagram of the constant symbols in \(\mathcal{L}\). Suppose
T is a completion of
T_{0}. Then:
- T is NSOP_{1}.
- If \(\mathcal{L}\) contains a function symbol of arity at least 2, then T is not simple.
- If \(\mathcal{L}\) contains a relation symbol of arity at least 2, then T is unstable.
- If all functions and relations in \(\mathcal{L}\) have arity at most 1, then T is superstable of U-rank 1.
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 .
\((\mathbb{R},+,\cdot,2^{\mathbb{Q}})\)
The real field expanded by a predicate for \(2^{\mathbb{Q}}\).
More generally, \(2^{\mathbb{Q}}\) can be replaced by any dense multiplicative subgroup of the positive reals with the Mann property, or by a dense transcendence basis for \(\mathbb{R}\) over \(\mathbb{Q}\).
See .
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}, and NSOP_{3}
It is unknown whether or not the implication SOP_{3} ⇒ TP_{1} is strict.
NTP_{2}, SOP_{3}, and NSOP_{4}
It is unknown whether or not 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 or not the strong order property hierarchy is strict inside NTP_{2}.
NTP_{2}, NFSOP, and SOP_{n} for all n ≥ 1
It is unknown whether or not the strong order property hierarchy is strict inside NTP_{2}.
NTP_{2}, NSOP, and FSOP
It is unknown whether or not the strong order property hierarchy is strict inside NTP_{2}.
NSOP_{1} and TP_{2}
NTP_{1} and SOP_{1}
It is unknown whether or not the implication TP_{1} ⇒ SOP_{1} is strict.
TP_{2}, TP_{1}, and NSOP_{3}
It is unknown whether or not 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 ≥ 1
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