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 finitely many 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 a specific vertex is definable, infinite and coinfinite.
Morley rank ω. Also referred to as the free pseudoplane.
See , .
\((\mathbb{Z},+,-,0,1)\)
Quantifier elimination up to the definable predicates P_{n}, which distinguish the elements divisible by n, for n > 0. This shows superstability.
Any set of prime numbers gives a complete type over \(\emptyset\) of an element divisible by exactly the prime numbers in the set. Thus \(S_1(\emptyset)\) is uncountable and the theory is not ω-stable.
See .
finitely refining equivalence relations
Infinitely many equivalence relations \(\{E_0,E_1,\ldots\}\) such that \(E_0\) has two infinite classes, and each \(E_i\)-class is partitioned into two infinite \(E_{i+1}\) classes.
See , .
infinitely refining equivalence relations
Infinitely many equivalence relations \(\{E_0,E_1,\ldots\}\) such that \(E_0\) has infinitely many infinite classes, and each \(E_i\)-class is partitioned into infinitely many infinite \(E_{i+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
Complete theory, with quantifier elimination in \(\mathcal{L}=\{+,\cdot,0,1,\lt\}\).
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 up to predicates P_{n} naming the elements divisible by n, for n > 0.
Not o-minimal since, e.g., 2\(\mathbb{Z}\) is a definable infinite discrete set.
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 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
Defined as ultraproducts of finite fields.
See .
ACFA
See .
QACFA
quasi-algebraically closed fields with a generic automorphism
See .
ultraproduct of \(\mathbb{Q}_p\)
\(\mathbb{Q}_p\) denotes the field of p-adic numbers
See .
generic K_{n}-free graph
Given
n ≥ 3,
K_{n} denotes the complete graph on
n vertices.
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
See , .
\((\mathbb{Q},\textrm{cyc})\)
The cyclic order on the rationals is cyc(a,b,c) if and only if a < b < c or b < c < a or c < a < b.
Can be interpreted in a real closed field, so NIP. The unique 1-type over \(\emptyset\) proves "x = 0, or x = 1, or cyc(0,x,1), or cyc(1,x,0)".
Each of these disjuncts divides over \(\emptyset\), so the type forks over \(\emptyset\), which shows that nonforking fails existence.
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,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,\ldots\}\) such that each \(E_i\) has two infinite classes, and for all \(n\lt\omega\) and \(I\subseteq n\),
\[\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 theory is the usual DLO. In general, the theory 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,\ldots\}\) such that each \(E_i\) has infinitely many infinite classes,
and for all \(i\lt\omega\), each \(E_{i+1}\) class splits each \(E_i\) 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\).
See , . In this theory is shown to be NSOP_{3} and not simple.
In it is shown to be NTP1. In it is claimed to be NSOP1, but the proof is currently under scrutiny. See also .
list of open examples
ω-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
See , . In this theory is shown to be NSOP_{3} and not simple;
and remarked to probably be NSOP_{1}. See also .
list of open examples
infinite-dimensional vector space with a bilinear form
Defined in the 2-sorted language of vector spaces over an algebraically closed field.
See , .
list of open examples
universal directed graph omitting all directed cycles
Complete theory of the universal and existentially closed countable directed graph omitting directed cycles of length ≤ n.
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 .
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, SOP, and not o-minimal
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} and NSOP_{∞}, 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 SOP_{∞}
It is unknown whether or not the strong order property hierarchy is strict inside NTP_{2}.
NSOP_{1} and TP_{2}
It is unknown whether or not the implication SOP_{1} ⇔ TP is strict.
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 ≥ 3
To keep this section distinct from the others, we would technically want to say 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}, NSOP_{∞}, and SOP_{n} for all n ≥ 1
TP_{2}, SOP_{∞}, and NSOP
TP_{2} and SOP
NIP, and not dp-minimal
ω-stable, and not dp-minimal
superstable, not ω-stable, and not dp-minimal
stable, not superstable, and not dp-minimal