Abstract We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has nonempty interior, and …
Abstract We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has nonempty interior, and any theory of pure tree is dp-minimal.
We formulate the measure analogue of generically stable types in first order theories with $NIP$ (without the independence property), giving several characterizations, answering some questions from an earlier paper by …
We formulate the measure analogue of generically stable types in first order theories with $NIP$ (without the independence property), giving several characterizations, answering some questions from an earlier paper by Hrushovski and Pillay, and giving another treatment of uniqueness results from the same paper. We introduce a notion of "generic compact domination", relating it to stationarity of the Keisler measures, and also giving definable group versions. We also prove the "approximate definability" of arbitrary Borel probability measures on definable sets in the real and $p$-adic fields.
We continue investigating the structure of externally definable sets in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> …
We continue investigating the structure of externally definable sets in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> theories and preservation of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; over a model, a family of non-forking instances of a formula (with parameters ranging over a type-definable set) can be covered with finitely many invariant types; we give some criteria for the boundedness of an expansion by a new predicate in a distal theory; naming an arbitrary small indiscernible sequence preserves <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, while naming a large one doesn’t; there are models of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> theories over which all 1-types are definable, but not all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-types.
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, …
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, give a proof of the conjecture of Petrykowski connecting existence of bounded orbits with definable amenability in the NIP case, and prove the Ellis group conjecture of Newelski and Pillay connecting the model-theoretic connected component of an NIP group with the ideal subgroup of its Ellis enveloping semigroup.
Abstract We show that dp-minimal valued fields are henselian and give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.
Abstract We show that dp-minimal valued fields are henselian and give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.
$\operatorname {NTP}_{2}$ is a large class of first-order theories defined by Shelah generalizing simple and NIP theories. Algebraic examples of $\operatorname {NTP}_{2}$ structures are given by ultra-products of $p$-adics and …
$\operatorname {NTP}_{2}$ is a large class of first-order theories defined by Shelah generalizing simple and NIP theories. Algebraic examples of $\operatorname {NTP}_{2}$ structures are given by ultra-products of $p$-adics and certain valued difference fields (such as a non-standard Frobenius automorphism living on an algebraically closed valued field of characteristic 0). In this note we present some results on groups and fields definable in $\operatorname {NTP}_{2}$ structures. Most importantly, we isolate a chain condition for definable normal subgroups and use it to show that any $\operatorname {NTP}_{2}$ field has only finitely many Artin-Schreier extensions. We also discuss a stronger chain condition coming from imposing bounds on burden of the theory (an appropriate analogue of weight) and show that every strongly dependent valued field is Kaplansky.
Abstract This paper has two parts. In the first one, we prove that an invariant dp-minimal type is either finitely satisfiable or definable. We also prove that a definable version …
Abstract This paper has two parts. In the first one, we prove that an invariant dp-minimal type is either finitely satisfiable or definable. We also prove that a definable version of the (p,q)-theorem holds in dp-minimal theories of small or medium directionality. In the second part, we study dp-rank in dp-minimal theories and show that it enjoys many nice properties. It is continuous, definable in families and it can be characterised geometrically with no mention of indiscernible sequences. In particular, if the structure expands a divisible ordered abelian group, then dp-rank coincides with the dimension coming from the order.
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP …
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is …
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is a good notion of dimension on definable sets, definable functions are almost everywhere continuous, and definable sets are finite unions of graphs of definable continuous "multivalued functions." This generalizes known statements about weakly o-minimal, C-minimal, and P-minimal theories.
We apply the work of Bourgain, Fremlin and Talagrand on compact subsets of the first Baire class to show new results about $\phi $-types for $\phi $ NIP. In particular, …
We apply the work of Bourgain, Fremlin and Talagrand on compact subsets of the first Baire class to show new results about $\phi $-types for $\phi $ NIP. In particular, we show that if $M$ is a countable model, then an $M$-invariant $\phi $-type is Borel-
We study invariant types in NIP theories. Amongst other things: we prove a definable version of the (p,q)-theorem in theories of small or medium directionality; we construct a canonical retraction …
We study invariant types in NIP theories. Amongst other things: we prove a definable version of the (p,q)-theorem in theories of small or medium directionality; we construct a canonical retraction from the space of M-invariant types to that of M-finitely satisfiable types; we show some amalgamation results for invariant types and list a number of open questions.
We prove in particular that, in a large class of dp-minimal theories including the p-adics, definable types are dense amongst non-forking types.
We prove in particular that, in a large class of dp-minimal theories including the p-adics, definable types are dense amongst non-forking types.
We study definably amenable NIP groups. We develop a theory of generics, showing that various definitions considered previously coincide, and study invariant measures. Applications include: characterization of regular ergodic measures, …
We study definably amenable NIP groups. We develop a theory of generics, showing that various definitions considered previously coincide, and study invariant measures. Applications include: characterization of regular ergodic measures, a proof of the conjecture of Petrykowski connecting existence of bounded orbits with definable amenability in the NIP case, and the Ellis group conjecture of Newelski and Pillay connecting the model-theoretic connected component of an NIP group with the ideal subgroup of its Ellis enveloping semigroup.
We show that the groups $AGL_{n}\left (\mathbb {Q}\right )$ (for $n\geq 2$) and $PGL_{n}\left (\mathbb {Q}\right )$ (for $n\geq 3$), seen as closed subgroups of $S_{\omega }$, are maximal-closed.
We show that the groups $AGL_{n}\left (\mathbb {Q}\right )$ (for $n\geq 2$) and $PGL_{n}\left (\mathbb {Q}\right )$ (for $n\geq 3$), seen as closed subgroups of $S_{\omega }$, are maximal-closed.
We show that if the restriction of the Lascar equivalence relation to a KP-strong type is non-trivial, then it is non-smooth (when viewed as a Borel equivalence relation on an …
We show that if the restriction of the Lascar equivalence relation to a KP-strong type is non-trivial, then it is non-smooth (when viewed as a Borel equivalence relation on an appropriate space of types).
We prove that many properties and invariants of definable groups in NIP theories, such as definable amenability, G/G 00 , etc., are preserved when passing to the theory of the …
We prove that many properties and invariants of definable groups in NIP theories, such as definable amenability, G/G 00 , etc., are preserved when passing to the theory of the Shelah expansion by externally definable sets, M ext , of a model M .In the light of these results we continue the study of the "definable topological dynamics" of groups in NIP theories.In particular we prove the Ellis group conjecture relating the Ellis group to G/G 00 in some new cases, including definably amenable groups in o-minimal structures.
In this paper, we develop three different subjects. We study and prove alternative versions of Hrushovski’s ‘stabilizer theorem’, we generalize part of the basic theory of definably amenable NIP groups …
In this paper, we develop three different subjects. We study and prove alternative versions of Hrushovski’s ‘stabilizer theorem’, we generalize part of the basic theory of definably amenable NIP groups to $\text{NTP}_{2}$ theories, and finally, we use all this machinery to study groups with f-generic types definable in bounded pseudo real closed fields.
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite …
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite topological rank of the automorphism group of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure can go down to reducts. Together, those results prove that a large number of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structures that appear in the literature have an automorphism group of finite topological rank. In fact, we are not aware of any <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure to which they do not apply (assuming the automorphism group has no compact quotients). We end with a few questions and conjectures.
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of …
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of stable and order-like components. More precisely, we prove that any type in an NIP theory can be decomposed into a stable part (a generically stable partial type) and an order-like quotient.
In a recent paper, Chernikov and Starchenko prove that graphs defined in distal theories have strong regularity properties, generalizing previous results about graphs defined by semi-algebraic relations. We give a …
In a recent paper, Chernikov and Starchenko prove that graphs defined in distal theories have strong regularity properties, generalizing previous results about graphs defined by semi-algebraic relations. We give a shorter, purely model-theoretic proof of this fact, though with no explicit bounds.
We prove that in NTP_2 theories if p is a dependent type with dp-rank >= \kappa, then this can be witnessed by indiscernible sequences of tuples satisfying p. If p …
We prove that in NTP_2 theories if p is a dependent type with dp-rank >= \kappa, then this can be witnessed by indiscernible sequences of tuples satisfying p. If p has dp-rank infinity, then this can be witnessed by singletons (in any theory).
Abstract This work builds on previous papers by Hrushovski, Pillay and the author where Keisler measures over NIP theories are studied. We discuss two constructions for obtaining generically stable measures …
Abstract This work builds on previous papers by Hrushovski, Pillay and the author where Keisler measures over NIP theories are studied. We discuss two constructions for obtaining generically stable measures in this context. First, we show how to symmetrize an arbitrary invariant measure to obtain a generically stable one from it. Next, we show that suitable sigma-additive probability measures give rise to generically stable Keisler measures. Also included is a proof that generically stable measures over o-minimal theories and the p-adics are smooth.
A theory [Formula: see text] is said to have exact saturation at a singular cardinal [Formula: see text] if it has a [Formula: see text]-saturated model which is not [Formula: …
A theory [Formula: see text] is said to have exact saturation at a singular cardinal [Formula: see text] if it has a [Formula: see text]-saturated model which is not [Formula: see text]-saturated. We show, under some set-theoretic assumptions, that any simple theory has exact saturation. Also, an NIP theory has exact saturation if and only if it is not distal. This gives a new characterization of distality.
Abstract We prove that every ultraproduct of p -adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued …
Abstract We prove that every ultraproduct of p -adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic 0 in the RV language.
Abstract We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP ? Easily, if acl (A)=A for …
Abstract We address the following question: Can we expand an NIP theory by adding a linear order such that the expansion is still NIP ? Easily, if acl (A)=A for all A , then this is true. Otherwise, we give counterexamples. More precisely, there is a totally categorical theory for which every expansion by a linear order has IP . There is also an ω -stable NDOP theory for which every expansion by a linear order interprets pseudofinite arithmetic.
We show that dp-minimal valued fields are henselian and that a dp-minimal field admitting a definable type V topology is either real closed, algebraically closed or admits a non-trivial definable …
We show that dp-minimal valued fields are henselian and that a dp-minimal field admitting a definable type V topology is either real closed, algebraically closed or admits a non-trivial definable henselian valuation. We give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.
In this paper we develop three different subjects. We study and prove alternative versions of Hrushovski's "Stabilizer Theorem", we generalize part of the basic theory of definably amenable NIP groups …
In this paper we develop three different subjects. We study and prove alternative versions of Hrushovski's "Stabilizer Theorem", we generalize part of the basic theory of definably amenable NIP groups to NTP2 theories, and finally, we use all this machinery to study groups with f-generic types definable in bounded PRC fields.
A theory is NIP (resp. stable) if and only if every formula with parameters in two single variables is NIP (resp. does not have the order property).
A theory is NIP (resp. stable) if and only if every formula with parameters in two single variables is NIP (resp. does not have the order property).
We continue investigating the structure of externally definable sets in NIP theories and preservation of NIP after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; …
We continue investigating the structure of externally definable sets in NIP theories and preservation of NIP after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; over a model, a family of non-forking instances of a formula (with parameters ranging over a type-definable set) can be covered with finitely many invariant types; we give some criteria for the boundedness of an expansion by a new predicate in a distal theory; naming an arbitrary small indiscernible sequence preserves NIP, while naming a large one doesn't; there are models of NIP theories over which all 1-types are definable, but not all n-types.
We prove (Proposition 2.1) that if μ is a generically stable measure in an NIP (no independence property) theory, and μ(ϕ(x,b))=0 for all b, then for some n, μ(n)(∃y(ϕ(x1,y)∧⋯∧ϕ(xn,y)))=0. As …
We prove (Proposition 2.1) that if μ is a generically stable measure in an NIP (no independence property) theory, and μ(ϕ(x,b))=0 for all b, then for some n, μ(n)(∃y(ϕ(x1,y)∧⋯∧ϕ(xn,y)))=0. As a consequence we show (Proposition 3.2) that if G is a definable group with fsg (finitely satisfiable generics) in an NIP theory, and X is a definable subset of G, then X is generic if and only if every translate of X does not fork over ∅, precisely as in stable groups, answering positively an earlier problem posed by the first two authors.
We show that the groups AGL_n(Q) and PGL_n(Q), seen as closed subgroups of S_{\infty}, are maximal-closed.
We show that the groups AGL_n(Q) and PGL_n(Q), seen as closed subgroups of S_{\infty}, are maximal-closed.
Abstract Let T be an NIP ${\cal L}$ -theory and $\mathop T\limits^\~ $ be an enrichment. We give a sufficient condition on $\mathop T\limits^\~$ for the underlying ${\cal L}$ -type …
Abstract Let T be an NIP ${\cal L}$ -theory and $\mathop T\limits^\~ $ be an enrichment. We give a sufficient condition on $\mathop T\limits^\~$ for the underlying ${\cal L}$ -type of any definable (respectively invariant) type over a model of $\mathop T\limits^\~$ to be definable (respectively invariant). These results are then applied to Scanlon’s model completion of valued differential fields.
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove a grid theorem …
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove a grid theorem for classes of ordered graphs which have unbounded twin-width. From this we derive that the model-checking problem for first-order logic is fixed-parameter tractable over a hereditary class of ordered graphs if, and -- under common complexity-theoretic assumptions -- only if the class has bounded twin-width. For hereditary classes of ordered graphs, we show that bounded twin-width is equivalent to the NIP property from model theory, as well as the smallness condition from enumerative combinatorics. We prove the existence of a gap in the growth of hereditary classes of ordered graphs. Furthermore, we provide a grid theorem which applies to all monadically NIP classes of structures (ordered or unordered), or equivalently, classes which do not transduce the class of all finite graphs.
An interpretation is an operation that maps an input graph to an output graph by redefining its edge relation using a first-order formula. This rich framework includes operations such as …
An interpretation is an operation that maps an input graph to an output graph by redefining its edge relation using a first-order formula. This rich framework includes operations such as taking the complement or a fixed power of a graph as (very) special cases.
We prove that every ultraproduct of $p$-adics is inp-minimal (i.e., of burden $1$). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of …
We prove that every ultraproduct of $p$-adics is inp-minimal (i.e., of burden $1$). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic $0$ in the RV language.
Let [Formula: see text] be a monster model of an arbitrary theory [Formula: see text], let [Formula: see text] be any (possibly infinite) tuple of bounded length of elements of …
Let [Formula: see text] be a monster model of an arbitrary theory [Formula: see text], let [Formula: see text] be any (possibly infinite) tuple of bounded length of elements of [Formula: see text], and let [Formula: see text] be an enumeration of all elements of [Formula: see text] (so a tuple of unbounded length). By [Formula: see text] we denote the compact space of all complete types over [Formula: see text] extending [Formula: see text], and [Formula: see text] is defined analogously. Then [Formula: see text] and [Formula: see text] are naturally [Formula: see text]-flows (even [Formula: see text]-ambits). We show that the Ellis groups of both these flows are of bounded size (i.e. smaller than the degree of saturation of [Formula: see text]), providing an explicit bound on this size. Next, we prove that these Ellis groups do not depend (as groups equipped with the so-called [Formula: see text]-topology) on the choice of the monster model [Formula: see text]; thus, we say that these Ellis groups are absolute. We also study minimal left ideals (equivalently subflows) of the Ellis semigroups of the flows [Formula: see text] and [Formula: see text]. We give an example of a NIP theory in which the minimal left ideals are of unbounded size. Then we show that in each of these two cases, boundedness of a minimal left ideal (equivalently, of all the minimal left ideals) is an absolute property (i.e. it does not depend on the choice of [Formula: see text]) and that whenever such an ideal is bounded, then in some sense its isomorphism type is also absolute. Under the assumption that [Formula: see text] has NIP, we give characterizations (in various terms) of when a minimal left ideal of the Ellis semigroup of [Formula: see text] is bounded. Then we adapt the proof of Theorem 5.7 in Definably amenable NIP groups, J. Amer. Math. Soc. 31 (2018) 609–641 to show that whenever such an ideal is bounded, a certain natural epimorphism (described in [K. Krupiński, A. Pillay and T. Rzepecki, Topological dynamics and the complexity of strong types, Israel J. Math. 228 (2018) 863–932]) from the Ellis group of the flow [Formula: see text] to the Kim–Pillay Galois group [Formula: see text] is an isomorphism (in particular, [Formula: see text] is G-compact). We also obtain some variants of these results, formulate some questions, and explain differences (providing a few counterexamples) which occur when the flow [Formula: see text] is replaced by [Formula: see text].
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups …
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups with only finitely many convex subgroups (in articular archimedean ordered abelian groups), and abelian groups equipped with archimedean cyclic group orders. The latter allows us to describe unary definable sets in dp-minimal expansions of $(\mathbb{Z},+,C)$, where $C$ is a cyclic group order. Along the way we describe unary definable sets in dp-minimal expansions of ordered abelian groups. In the last section we give a canonical correspondence between dp-minimal expansions of $(\mathbb{Q},+,<)$ and o-minimal expansions $\mathcal{R}$ of $(\mathbb{R},+,<)$ such that $(\mathcal{R},\mathbb{Q})$ is a dense pair.
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP …
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [ 5 ] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [ 8 ] in the case of ordered graphs.
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of …
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of all elements of ${\mathfrak C}$. By $S_{\bar \alpha}({\mathfrak C})$ denote the compact space of all complete types over ${\mathfrak C}$ extending $tp(\bar \alpha/\emptyset)$, and $S_{\bar c}({\mathfrak C})$ is defined analogously. Then $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$ are naturally $Aut({\mathfrak C})$-flows. We show that the Ellis groups of both these flows are of bounded size (i.e. smaller than the degree of saturation of ${\mathfrak C}$), providing an explicit bound on this size. Next, we prove that these Ellis groups do not depend on the choice of the monster model ${\mathfrak C}$; thus, we say that they are absolute. We also study minimal left ideals (equivalently subflows) of the Ellis semigroups of the flows $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$. We give an example of a NIP theory in which the minimal left ideals are of unbounded size. We show that in each of these two cases, boundedness of a minimal left ideal is an absolute property (i.e. it does not depend on the choice of ${\mathfrak C}$) and that whenever such an ideal is bounded, then its isomorphism type is also absolute.
Assuming NIP, we give characterizations of when a minimal left ideal of the Ellis semigroup of $S_{\bar c}({\mathfrak C})$ is bounded. Then we adapt a proof of Chernikov and Simon to show that whenever such an ideal is bounded, the natural epimorphism (described by Krupinski, Pillay and Rzepecki) from the Ellis group of the flow $S_{\bar c}({\mathfrak C})$ to the Kim-Pillay Galois group $Gal_{KP}(T)$ is an isomorphism (in particular, $T$ is G-compact). We provide some counter-examples for $S_{\bar \alpha}({\mathfrak C})$ in place of $S_{\bar c}({\mathfrak C})$.
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite …
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite linear order. This partially answers a longstanding open question.
We classify the homogeneous finite-dimensional permutation structures, i.e. homogeneous structures in a language of finitely many linear orders, giving a nearly complete answer to a question of Cameron, and confirming …
We classify the homogeneous finite-dimensional permutation structures, i.e. homogeneous structures in a language of finitely many linear orders, giving a nearly complete answer to a question of Cameron, and confirming the classification conjectured by the first author. The primitive case was proven by the second author using model-theoretic methods, and those methods continue to appear here.
We show some basic facts about dp-minimal ordered structures. The main results are : dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has non-empty interior, …
We show some basic facts about dp-minimal ordered structures. The main results are : dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has non-empty interior, and any theory of pure tree is dp-minimal.
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups …
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups with only finitely many convex subgroups (in articular archimedean ordered abelian groups), and abelian groups equipped with archimedean cyclic group orders. The latter allows us to describe unary definable sets in dp-minimal expansions of $(\mathbb{Z},+,C)$, where $C$ is a cyclic group order. Along the way we describe unary definable sets in dp-minimal expansions of ordered abelian groups. In the last section we give a canonical correspondence between dp-minimal expansions of $(\mathbb{Q},+,<)$ and o-minimal expansions $\mathcal{R}$ of $(\mathbb{R},+,<)$ such that $(\mathcal{R},\mathbb{Q})$ is a dense pair.
We present a new proof of descent for stably dominated types in any theory, weakening the hypothesis of the existence of global invariant extensions. Additionally, we give a much simpler …
We present a new proof of descent for stably dominated types in any theory, weakening the hypothesis of the existence of global invariant extensions. Additionally, we give a much simpler proof of descent for stably dominated types in ACVF. Furthermore, we demonstrate that any stable set in an NIP theory has the bounded stabilizing property. This result is subsequently used to correct Proposition 6.7 from the book on stable domination and independence in ACVF.
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP …
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory. This has several consequences. First, it allows us to show that every hereditary class of ordered graphs either has at most exponential growth, or has at least factorial growth. This settles a question first asked by Balogh et al. [ 5 ] on the growth of hereditary classes of ordered graphs, generalizing the Stanley-Wilf conjecture/Marcus-Tardos theorem. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width. Finally, it settles the small conjecture [ 8 ] in the case of ordered graphs.
We study compressible types in the context of (local and global) NIP. By extending a result in machine learning theory (the existence of a bound on the recursive teaching dimension), …
We study compressible types in the context of (local and global) NIP. By extending a result in machine learning theory (the existence of a bound on the recursive teaching dimension), we prove density of compressible types. Using this, we obtain explicit uniform honest definitions for NIP formulas (answering a question of Eshel and the second author), and build compressible models in countable NIP theories.
Abstract We initiate a systematic study of generic stability independence and introduce the class of treeless theories in which this notion of independence is particularly well behaved. We show that …
Abstract We initiate a systematic study of generic stability independence and introduce the class of treeless theories in which this notion of independence is particularly well behaved. We show that the class of treeless theories contains both binary theories and stable theories and give several applications of the theory of independence for treeless theories. As a corollary, we show that every binary NSOP $_{3}$ theory is simple.
Abstract We study cofinal systems of finite subsets of $\omega _1$ . We show that while such systems can be NIP, they cannot be defined in an NIP structure. We …
Abstract We study cofinal systems of finite subsets of $\omega _1$ . We show that while such systems can be NIP, they cannot be defined in an NIP structure. We deduce a positive answer to a question of Chernikov and Simon from 2013: In an NIP theory, any uncountable externally definable set contains an infinite definable subset. A similar result holds for larger cardinals.
We generalize previous results about stable domination and residue field domination to henselian valued fields of equicharacteristic 0 with bounded Galois group, and we provide an alternate characterization of stable …
We generalize previous results about stable domination and residue field domination to henselian valued fields of equicharacteristic 0 with bounded Galois group, and we provide an alternate characterization of stable domination in algebraically closed valued fields for types over parameters in the field sort.
We initiate a systematic study of \emph{generic stability independence} and introduce the class of \emph{treeless theories} in which this notion of independence is particularly well-behaved. We show that the class …
We initiate a systematic study of \emph{generic stability independence} and introduce the class of \emph{treeless theories} in which this notion of independence is particularly well-behaved. We show that the class of treeless theories contains both binary theories and stable theories and give several applications of the theory of independence for treeless theories. As a corollary, we show that every binary NSOP$_{3}$ theory is simple.
An interpretation is an operation that maps an input graph to an output graph by redefining its edge relation using a first-order formula. This rich framework includes operations such as …
An interpretation is an operation that maps an input graph to an output graph by redefining its edge relation using a first-order formula. This rich framework includes operations such as taking the complement or a fixed power of a graph as (very) special cases.
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP …
We establish a list of characterizations of bounded twin-width for hereditary classes of totally ordered graphs: as classes of at most exponential growth studied in enumerative combinatorics, as monadically NIP classes studied in model theory, as classes that do not transduce the class of all graphs studied in finite model theory, and as classes for which model checking first-order logic is fixed-parameter tractable studied in algorithmic graph theory.
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of …
We present a fixed-parameter tractable algorithm for first-order model checking on interpretations of graph classes with bounded local cliquewidth. Notably, this includes interpretations of planar graphs, and more generally, of classes of bounded genus. To obtain this result we develop a new tool which works in a very general setting of dependent classes and which we believe can be an important ingredient in achieving similar results in the future.
We study cofinal systems of finite subsets of $\omega_1$. We show that while such systems can be NIP, they cannot be defined in an NIP structure. We deduce a positive …
We study cofinal systems of finite subsets of $\omega_1$. We show that while such systems can be NIP, they cannot be defined in an NIP structure. We deduce a positive answer to a question of Chernikov and Simon from 2013: in an NIP theory, any uncountable externally definable set contains an infinite definable subset. A similar result holds for larger cardinals.
We generalize previous results about stable domination and residue field domination to henselian valued fields of equicharacteristic 0 with bounded Galois group, and we provide an alternate characterization of stable …
We generalize previous results about stable domination and residue field domination to henselian valued fields of equicharacteristic 0 with bounded Galois group, and we provide an alternate characterization of stable domination in algebraically closed valued fields for types over parameters in the field sort.
For $G$ an algebraic group definable over a model of $\operatorname{ACVF}$, or more generally a definable subgroup of an algebraic group, we study the stable completion $\widehat{G}$ of $G$, as …
For $G$ an algebraic group definable over a model of $\operatorname{ACVF}$, or more generally a definable subgroup of an algebraic group, we study the stable completion $\widehat{G}$ of $G$, as introduced by Loeser and the second author. For $G$ connected and stably dominated, assuming $G$ commutative or that the valued field is of equicharacteristic 0, we construct a pro-definable $G$-equivariant strong deformation retraction of $\widehat{G}$ onto the generic type of $G$. For $G=S$ a semiabelian variety, we construct a pro-definable $S$-equivariant strong deformation retraction of $\widehat{S}$ onto a definable group which is internal to the value group. We show that, in case $S$ is defined over a complete valued field $K$ with value group a subgroup of $\mathbb{R}$, this map descends to an $S(K)$-equivariant strong deformation retraction of the Berkovich analytification $S^{\mathrm{an}}$ of $S$ onto a piecewise linear group, namely onto the skeleton of $S^{\mathrm{an}}$. This yields a construction of such a retraction without resorting to an analytic (non-algebraic) uniformization of $S$. Furthermore, we prove a general result on abelian groups definable in an NIP theory: any such group $G$ is a directed union of $\infty$-definable subgroups which all stabilize a generically stable Keisler measure on $G$.
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove a grid theorem …
We consider hereditary classes of graphs equipped with a total order. We provide multiple equivalent characterisations of those classes which have bounded twin-width. In particular, we prove a grid theorem for classes of ordered graphs which have unbounded twin-width. From this we derive that the model-checking problem for first-order logic is fixed-parameter tractable over a hereditary class of ordered graphs if, and -- under common complexity-theoretic assumptions -- only if the class has bounded twin-width. For hereditary classes of ordered graphs, we show that bounded twin-width is equivalent to the NIP property from model theory, as well as the smallness condition from enumerative combinatorics. We prove the existence of a gap in the growth of hereditary classes of ordered graphs. Furthermore, we provide a grid theorem which applies to all monadically NIP classes of structures (ordered or unordered), or equivalently, classes which do not transduce the class of all finite graphs.
A theory is NIP (resp. stable) if and only if every formula with parameters in two single variables is NIP (resp. does not have the order property).
A theory is NIP (resp. stable) if and only if every formula with parameters in two single variables is NIP (resp. does not have the order property).
We study finitely homogeneous dependent rosy structures, adapting results of Cherlin, Harrington, and Lachlan proved for $ω$-stable $ω$-categorical structures. In particular, we prove that such structures have finite þ-rank and …
We study finitely homogeneous dependent rosy structures, adapting results of Cherlin, Harrington, and Lachlan proved for $ω$-stable $ω$-categorical structures. In particular, we prove that such structures have finite þ-rank and are coordinatized by a þ-rank 1 set. We show that they admit a distal, finitely axiomatizable, expansion. These results show that there are, up to inter-definability, at most countably many dependent rosy structures M which are homogeneous in a finite relational language.
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of …
We establish a list of characterizations of bounded twin-width for hereditary, totally ordered binary structures. This has several consequences. First, it allows us to show that a (hereditary) class of matrices over a finite alphabet either contains at least $n!$ matrices of size $n \times n$, or at most $c^n$ for some constant $c$. This generalizes the celebrated Stanley-Wilf conjecture/Marcus-Tardos theorem from permutation classes to any matrix class over a finite alphabet, answers our small conjecture [SODA '21] in the case of ordered graphs, and with more work, settles a question first asked by Balogh, Bollob\'as, and Morris [Eur. J. Comb. '06] on the growth of hereditary classes of ordered graphs. Second, it gives a fixed-parameter approximation algorithm for twin-width on ordered graphs. Third, it yields a full classification of fixed-parameter tractable first-order model checking on hereditary classes of ordered binary structures. Fourth, it provides a model-theoretic characterization of classes with bounded twin-width.
We study compressible types in the context of (local and global) NIP. By extending a result in machine learning theory (the existence of a bound on the recursive teaching dimension), …
We study compressible types in the context of (local and global) NIP. By extending a result in machine learning theory (the existence of a bound on the recursive teaching dimension), we prove density of compressible types. Using this, we obtain explicit uniform honest definitions for NIP formulas (answering a question of Eshel and the second author), and build compressible models in countable NIP theories.
We prove a couple of results on NTP2 theories. First, we prove an amalgamation statement and deduce from it that the Lascar distance over extension bases is bounded by 2. …
We prove a couple of results on NTP2 theories. First, we prove an amalgamation statement and deduce from it that the Lascar distance over extension bases is bounded by 2. This improves previous work of Ben Yaacov and Chernikov. We propose a line of investigation of NTP2 theories based on S1 ideals with amalgamation and ask some questions. We then define and study a class of groups with generically simple generics, generalizing NIP groups with generically stable generics.
We classify the homogeneous finite-dimensional permutation structures, i.e. homogeneous structures in a language of finitely many linear orders, giving a nearly complete answer to a question of Cameron, and confirming …
We classify the homogeneous finite-dimensional permutation structures, i.e. homogeneous structures in a language of finitely many linear orders, giving a nearly complete answer to a question of Cameron, and confirming the classification conjectured by the first author. The primitive case was proven by the second author using model-theoretic methods, and those methods continue to appear here.
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of …
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of stable and order-like components. More precisely, we prove that any type in an NIP theory can be decomposed into a stable part (a generically stable partial type) and an order-like quotient.
Abstract We prove that every ultraproduct of p -adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued …
Abstract We prove that every ultraproduct of p -adics is inp-minimal (i.e., of burden 1). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic 0 in the RV language.
Let [Formula: see text] be a monster model of an arbitrary theory [Formula: see text], let [Formula: see text] be any (possibly infinite) tuple of bounded length of elements of …
Let [Formula: see text] be a monster model of an arbitrary theory [Formula: see text], let [Formula: see text] be any (possibly infinite) tuple of bounded length of elements of [Formula: see text], and let [Formula: see text] be an enumeration of all elements of [Formula: see text] (so a tuple of unbounded length). By [Formula: see text] we denote the compact space of all complete types over [Formula: see text] extending [Formula: see text], and [Formula: see text] is defined analogously. Then [Formula: see text] and [Formula: see text] are naturally [Formula: see text]-flows (even [Formula: see text]-ambits). We show that the Ellis groups of both these flows are of bounded size (i.e. smaller than the degree of saturation of [Formula: see text]), providing an explicit bound on this size. Next, we prove that these Ellis groups do not depend (as groups equipped with the so-called [Formula: see text]-topology) on the choice of the monster model [Formula: see text]; thus, we say that these Ellis groups are absolute. We also study minimal left ideals (equivalently subflows) of the Ellis semigroups of the flows [Formula: see text] and [Formula: see text]. We give an example of a NIP theory in which the minimal left ideals are of unbounded size. Then we show that in each of these two cases, boundedness of a minimal left ideal (equivalently, of all the minimal left ideals) is an absolute property (i.e. it does not depend on the choice of [Formula: see text]) and that whenever such an ideal is bounded, then in some sense its isomorphism type is also absolute. Under the assumption that [Formula: see text] has NIP, we give characterizations (in various terms) of when a minimal left ideal of the Ellis semigroup of [Formula: see text] is bounded. Then we adapt the proof of Theorem 5.7 in Definably amenable NIP groups, J. Amer. Math. Soc. 31 (2018) 609–641 to show that whenever such an ideal is bounded, a certain natural epimorphism (described in [K. Krupiński, A. Pillay and T. Rzepecki, Topological dynamics and the complexity of strong types, Israel J. Math. 228 (2018) 863–932]) from the Ellis group of the flow [Formula: see text] to the Kim–Pillay Galois group [Formula: see text] is an isomorphism (in particular, [Formula: see text] is G-compact). We also obtain some variants of these results, formulate some questions, and explain differences (providing a few counterexamples) which occur when the flow [Formula: see text] is replaced by [Formula: see text].
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite …
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite topological rank of the automorphism group of an <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure can go down to reducts. Together, those results prove that a large number of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structures that appear in the literature have an automorphism group of finite topological rank. In fact, we are not aware of any <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega"> <mml:semantics> <mml:mi>ω</mml:mi> <mml:annotation encoding="application/x-tex">\omega</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure to which they do not apply (assuming the automorphism group has no compact quotients). We end with a few questions and conjectures.
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is …
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is a good notion of dimension on definable sets, definable functions are almost everywhere continuous, and definable sets are finite unions of graphs of definable continuous "multivalued functions." This generalizes known statements about weakly o-minimal, C-minimal, and P-minimal theories.
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups …
A first order expansion of $(\mathbb{R},+,<)$ is dp-minimal if and only if it is o-minimal. We prove analogous results for algebraic closures of finite fields, $p$-adic fields, ordered abelian groups with only finitely many convex subgroups (in articular archimedean ordered abelian groups), and abelian groups equipped with archimedean cyclic group orders. The latter allows us to describe unary definable sets in dp-minimal expansions of $(\mathbb{Z},+,C)$, where $C$ is a cyclic group order. Along the way we describe unary definable sets in dp-minimal expansions of ordered abelian groups. In the last section we give a canonical correspondence between dp-minimal expansions of $(\mathbb{Q},+,<)$ and o-minimal expansions $\mathcal{R}$ of $(\mathbb{R},+,<)$ such that $(\mathcal{R},\mathbb{Q})$ is a "dense pair".
We establish new results on the possible growth rates for the sequence (f_n) counting the number of orbits of a given oligomorphic group on unordered sets of size n. Macpherson …
We establish new results on the possible growth rates for the sequence (f_n) counting the number of orbits of a given oligomorphic group on unordered sets of size n. Macpherson showed that for primitive actions, the growth is at least exponential (if the sequence is not constant equal to 1). The best lower bound previously known for the base of the exponential was obtained by Merola. We establishing the optimal value of 2 in the case where the structure is unstable. This allows us to improve on Merola's bound and also obtain the optimal value for structures homogeneous in a finite relational language. Finally, we show that the study of sequences (f_n) of sub-exponential growth reduces to the omega-stable case.
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite …
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite linear order. This partially answers a longstanding open question.
We classify primitive, rank 1, omega-categorical structures having polynomially many types over finite sets. For a fixed number of 4-types, we show that there are only finitely many such structures …
We classify primitive, rank 1, omega-categorical structures having polynomially many types over finite sets. For a fixed number of 4-types, we show that there are only finitely many such structures and that all are built out of finitely many linear orders interacting in a restricted number of ways. As an example of application, we deduce the classification of primitive structures homogeneous in a language consisting of n linear orders as well as all reducts of such structures.
In this paper, we develop three different subjects. We study and prove alternative versions of Hrushovski’s ‘stabilizer theorem’, we generalize part of the basic theory of definably amenable NIP groups …
In this paper, we develop three different subjects. We study and prove alternative versions of Hrushovski’s ‘stabilizer theorem’, we generalize part of the basic theory of definably amenable NIP groups to $\text{NTP}_{2}$ theories, and finally, we use all this machinery to study groups with f-generic types definable in bounded pseudo real closed fields.
This text is an introduction to de finably amenable NIP groups. It is based on a number of papers, mainly \[6], \[7] and \[4]. This subject has two origins, the …
This text is an introduction to de finably amenable NIP groups. It is based on a number of papers, mainly \[6], \[7] and \[4]. This subject has two origins, the fi rst one is the theory of stable groups and in particular generic types, which were fi rst defi ned by Poizat (see \[12]) and have since played a central role throughout stability theory. Later, part of the theory was generalized to groups in simple theories, where generic types are de ned as types, none of whose translates forks over the empty set.
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite …
We show that every unstable NIP theory admits a V-definable linear quasi-order, over a finite set of parameters. In particular, if the theory is omega-categorical, then it interprets an infinite linear order. This partially answers a longstanding open question.
We classify primitive, rank 1, omega-categorical structures having polynomially many types over finite sets. For a fixed number of 4-types, we show that there are only finitely many such structures …
We classify primitive, rank 1, omega-categorical structures having polynomially many types over finite sets. For a fixed number of 4-types, we show that there are only finitely many such structures and that all are built out of finitely many linear orders interacting in a restricted number of ways. As an example of application, we deduce the classification of primitive structures homogeneous in a language consisting of n linear orders as well as all reducts of such structures.
We establish new results on the possible growth rates for the sequence (f_n) counting the number of orbits of a given oligomorphic group on unordered sets of size n. Macpherson …
We establish new results on the possible growth rates for the sequence (f_n) counting the number of orbits of a given oligomorphic group on unordered sets of size n. Macpherson showed that for primitive actions, the growth is at least exponential (if the sequence is not constant equal to 1). The best lower bound previously known for the base of the exponential was obtained by Merola. We establishing the optimal value of 2 in the case where the structure is unstable. This allows us to improve on Merola's bound and also obtain the optimal value for structures homogeneous in a finite relational language. Finally, we show that the study of sequences (f_n) of sub-exponential growth reduces to the omega-stable case.
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, …
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, give a proof of the conjecture of Petrykowski connecting existence of bounded orbits with definable amenability in the NIP case, and prove the Ellis group conjecture of Newelski and Pillay connecting the model-theoretic connected component of an NIP group with the ideal subgroup of its Ellis enveloping semigroup.
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite …
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite topological rank of the automorphism group of an $\omega$-categorical structure can go down to reducts. Together, those results prove that a large number of $\omega$-categorical structures that appear in the literature have an automorphism group of finite topological rank. In fact, we are not aware of any $\omega$-categorical structure to which they do not apply (assuming the automorphism group has no compact quotients). We end with a few questions and conjectures.
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of …
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of all elements of ${\mathfrak C}$. By $S_{\bar \alpha}({\mathfrak C})$ denote the compact space of all complete types over ${\mathfrak C}$ extending $tp(\bar \alpha/\emptyset)$, and $S_{\bar c}({\mathfrak C})$ is defined analogously. Then $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$ are naturally $Aut({\mathfrak C})$-flows. We show that the Ellis groups of both these flows are of bounded size (i.e. smaller than the degree of saturation of ${\mathfrak C}$), providing an explicit bound on this size. Next, we prove that these Ellis groups do not depend on the choice of the monster model ${\mathfrak C}$; thus, we say that they are absolute. We also study minimal left ideals (equivalently subflows) of the Ellis semigroups of the flows $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$. We give an example of a NIP theory in which the minimal left ideals are of unbounded size. We show that in each of these two cases, boundedness of a minimal left ideal is an absolute property (i.e. it does not depend on the choice of ${\mathfrak C}$) and that whenever such an ideal is bounded, then its isomorphism type is also absolute.
Assuming NIP, we give characterizations of when a minimal left ideal of the Ellis semigroup of $S_{\bar c}({\mathfrak C})$ is bounded. Then we adapt a proof of Chernikov and Simon to show that whenever such an ideal is bounded, the natural epimorphism (described by Krupinski, Pillay and Rzepecki) from the Ellis group of the flow $S_{\bar c}({\mathfrak C})$ to the Kim-Pillay Galois group $Gal_{KP}(T)$ is an isomorphism (in particular, $T$ is G-compact). We provide some counter-examples for $S_{\bar \alpha}({\mathfrak C})$ in place of $S_{\bar c}({\mathfrak C})$.
Abstract We show that dp-minimal valued fields are henselian and give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.
Abstract We show that dp-minimal valued fields are henselian and give classifications of dp-minimal ordered abelian groups and dp-minimal ordered fields without additional structure.
Abstract Let T be an NIP ${\cal L}$ -theory and $\mathop T\limits^\~ $ be an enrichment. We give a sufficient condition on $\mathop T\limits^\~$ for the underlying ${\cal L}$ -type …
Abstract Let T be an NIP ${\cal L}$ -theory and $\mathop T\limits^\~ $ be an enrichment. We give a sufficient condition on $\mathop T\limits^\~$ for the underlying ${\cal L}$ -type of any definable (respectively invariant) type over a model of $\mathop T\limits^\~$ to be definable (respectively invariant). These results are then applied to Scanlon’s model completion of valued differential fields.
A theory [Formula: see text] is said to have exact saturation at a singular cardinal [Formula: see text] if it has a [Formula: see text]-saturated model which is not [Formula: …
A theory [Formula: see text] is said to have exact saturation at a singular cardinal [Formula: see text] if it has a [Formula: see text]-saturated model which is not [Formula: see text]-saturated. We show, under some set-theoretic assumptions, that any simple theory has exact saturation. Also, an NIP theory has exact saturation if and only if it is not distal. This gives a new characterization of distality.
We introduce the notion of an NTP$_{2}$-smooth measure and prove that they exist assuming NTP$_{2}$. Using this, we propose a notion of distality in NTP$_{2}$ that unfortunately does not intersect …
We introduce the notion of an NTP$_{2}$-smooth measure and prove that they exist assuming NTP$_{2}$. Using this, we propose a notion of distality in NTP$_{2}$ that unfortunately does not intersect simple theories trivially. We then prove a finite alternation theorem for a subclass of NTP$_{2}$ that contains resilient theories. In the last section we prove that under NIP, any type over a model of singular size is finitely satisfiable in a smaller model, and ask if a parallel result (with non-forking replacing finite satisfiability) holds in NTP$_{2}$.
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of …
Let ${\mathfrak C}$ be a monster model of an arbitrary theory $T$, $\bar \alpha$ any tuple of bounded length of elements of ${\mathfrak C}$, and $\bar c$ an enumeration of all elements of ${\mathfrak C}$. By $S_{\bar \alpha}({\mathfrak C})$ denote the compact space of all complete types over ${\mathfrak C}$ extending $tp(\bar \alpha/\emptyset)$, and $S_{\bar c}({\mathfrak C})$ is defined analogously. Then $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$ are naturally $Aut({\mathfrak C})$-flows. We show that the Ellis groups of both these flows are of bounded size (i.e. smaller than the degree of saturation of ${\mathfrak C}$), providing an explicit bound on this size. Next, we prove that these Ellis groups do not depend on the choice of the monster model ${\mathfrak C}$; thus, we say that they are absolute. We also study minimal left ideals (equivalently subflows) of the Ellis semigroups of the flows $S_{\bar \alpha}({\mathfrak C})$ and $S_{\bar c}({\mathfrak C})$. We give an example of a NIP theory in which the minimal left ideals are of unbounded size. We show that in each of these two cases, boundedness of a minimal left ideal is an absolute property (i.e. it does not depend on the choice of ${\mathfrak C}$) and that whenever such an ideal is bounded, then its isomorphism type is also absolute. Assuming NIP, we give characterizations of when a minimal left ideal of the Ellis semigroup of $S_{\bar c}({\mathfrak C})$ is bounded. Then we adapt a proof of Chernikov and Simon to show that whenever such an ideal is bounded, the natural epimorphism (described by Krupinski, Pillay and Rzepecki) from the Ellis group of the flow $S_{\bar c}({\mathfrak C})$ to the Kim-Pillay Galois group $Gal_{KP}(T)$ is an isomorphism (in particular, $T$ is G-compact). We provide some counter-examples for $S_{\bar \alpha}({\mathfrak C})$ in place of $S_{\bar c}({\mathfrak C})$.
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite …
We offer a criterion for showing that the automorphism group of an ultrahomogeneous structure is topologically 2-generated and even has a cyclically dense conjugacy class. We then show how finite topological rank of the automorphism group of an $\omega$-categorical structure can go down to reducts. Together, those results prove that a large number of $\omega$-categorical structures that appear in the literature have an automorphism group of finite topological rank. In fact, we are not aware of any $\omega$-categorical structure to which they do not apply (assuming the automorphism group has no compact quotients). We end with a few questions and conjectures.
We prove that every ultraproduct of $p$-adics is inp-minimal (i.e., of burden $1$). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of …
We prove that every ultraproduct of $p$-adics is inp-minimal (i.e., of burden $1$). More generally, we prove an Ax-Kochen type result on preservation of inp-minimality for Henselian valued fields of equicharacteristic $0$ in the RV language.
We study forking, Lascar strong types, Keisler measures and definable groups, under an assumption of NIP (not the independence property), continuing aspects of the paper [16]. Among key results are …
We study forking, Lascar strong types, Keisler measures and definable groups, under an assumption of NIP (not the independence property), continuing aspects of the paper [16]. Among key results are (i) if p = \mathrm{tp}(b/A) does not fork over A then the Lascar strong type of b over A coincides with the compact strong type of b over A and any global nonforking extension of p is Borel definable over \mathrm{bdd}(A) , (ii) analogous statements for Keisler measures and definable groups, including the fact that G^{000} = G^{00} for G definably amenable, (iii) definitions, characterizations and properties of “generically stable” types and groups, (iv) uniqueness of invariant (under the group action) Keisler measures on groups with finitely satisfiable generics, (v) a proof of the compact domination conjecture for (definably compact) commutative groups in o -minimal expansions of real closed fields.
Abstract We prove that in theories without the tree property of the second kind (which include dependent and simple theories) forking and dividing over models are the same, and in …
Abstract We prove that in theories without the tree property of the second kind (which include dependent and simple theories) forking and dividing over models are the same, and in fact over any extension base. As an application we show that dependence is equivalent to bounded non-forking assuming NTP 2 .
Abstract We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has nonempty interior, and …
Abstract We show basic facts about dp-minimal ordered structures. The main results are: dp-minimal groups are abelian-by-finite-exponent, in a divisible ordered dp-minimal group, any infinite set has nonempty interior, and any theory of pure tree is dp-minimal.
We formulate the measure analogue of generically stable types in first order theories with $NIP$ (without the independence property), giving several characterizations, answering some questions from an earlier paper by …
We formulate the measure analogue of generically stable types in first order theories with $NIP$ (without the independence property), giving several characterizations, answering some questions from an earlier paper by Hrushovski and Pillay, and giving another treatment of uniqueness results from the same paper. We introduce a notion of "generic compact domination", relating it to stationarity of the Keisler measures, and also giving definable group versions. We also prove the "approximate definability" of arbitrary Borel probability measures on definable sets in the real and $p$-adic fields.
Abstract Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely …
Abstract Dp-minimality is a common generalization of weak minimality and weak o-minimality. If T is a weakly o-minimal theory then it is dp-minimal (Fact 2.2), but there are dp-minimal densely ordered groups that are not weakly o-minimal. We introduce the even more general notion of inp-minimality and prove that in an inp-minimal densely ordered group, every definable unary function is a union of finitely many continuous locally monotonic functions (Theorem 3.2).
We discuss measures, invariant measures on definable groups, and genericity, often in an NIP (failure of the independence property) environment. We complete the proof of the third author's conjectures relating …
We discuss measures, invariant measures on definable groups, and genericity, often in an NIP (failure of the independence property) environment. We complete the proof of the third author's conjectures relating definably compact groups $G$ in saturated $o$-minimal structures to compact Lie groups. We also prove some other structural results about such $G$, for example the existence of a left invariant finitely additive probability measure on definable subsets of $G$. We finally introduce the new notion of "compact domination" (domination of a definable set by a compact space) and raise some new conjectures in the $o$-minimal case.
We continue investigating the structure of externally definable sets in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> …
We continue investigating the structure of externally definable sets in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> theories and preservation of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> after expanding by new predicates. Most importantly: types over finite sets are uniformly definable; over a model, a family of non-forking instances of a formula (with parameters ranging over a type-definable set) can be covered with finitely many invariant types; we give some criteria for the boundedness of an expansion by a new predicate in a distal theory; naming an arbitrary small indiscernible sequence preserves <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, while naming a large one doesn’t; there are models of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper N normal upper I normal upper P"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="normal">N</mml:mi> <mml:mi mathvariant="normal">I</mml:mi> <mml:mi mathvariant="normal">P</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathrm {NIP}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> theories over which all 1-types are definable, but not all <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n"> <mml:semantics> <mml:mi>n</mml:mi> <mml:annotation encoding="application/x-tex">n</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-types.
We classify dp-minimal pure fields up to elementary equivalence. Most are equivalent to Hahn series fields $K((t^\Gamma))$ where $\Gamma$ satisfies some divisibility conditions and $K$ is $\mathbb{F}_p^{alg}$ or a local …
We classify dp-minimal pure fields up to elementary equivalence. Most are equivalent to Hahn series fields $K((t^\Gamma))$ where $\Gamma$ satisfies some divisibility conditions and $K$ is $\mathbb{F}_p^{alg}$ or a local field of characteristic zero. We show that dp-small fields (including VC-minimal fields) are algebraically closed or real closed.
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of …
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of the rest of the paper is dedicated to examples. We establish via a simple proof that any weakly o-minimal theory is dp-minimal and then give an example of a weakly o-minimal group not obtained by adding traces of externally definable sets. Next we give an example of a divisible ordered Abelian group which is dp-minimal and not weakly o-minimal. Finally we establish that the field of p-adic numbers is dp-minimal.
We try to understand complete types over a somewhat saturated model of a complete first-order theory which is dependent (previously called NIP), by "decomposition theorems for such types". Our thesis …
We try to understand complete types over a somewhat saturated model of a complete first-order theory which is dependent (previously called NIP), by "decomposition theorems for such types". Our thesis is that the picture of dependent theory is the combination of the one for stable theories and the one for the theory of dense linear order or trees (and first, we should try to understand the quite saturated case). As a measure of our progress, we give several applications considering some test questions; in particular, we try to prove the generic pair conjecture and do it for measurable cardinals.
Abstract We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent theories.
Abstract We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent theories.
We note a parallel between some ideas of stable model theory and certain topics in finite combinatorics related to the sum-product phenomenon. For a simple linear group <inline-formula content-type="math/mathml"> <mml:math …
We note a parallel between some ideas of stable model theory and certain topics in finite combinatorics related to the sum-product phenomenon. For a simple linear group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, we show that a finite subset <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper X"> <mml:semantics> <mml:mi>X</mml:mi> <mml:annotation encoding="application/x-tex">X</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="StartAbsoluteValue upper X upper X Superscript negative 1 Baseline upper X EndAbsoluteValue slash StartAbsoluteValue upper X EndAbsoluteValue"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>X</mml:mi> <mml:msup> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msup> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> <mml:mi>X</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">|</mml:mo> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">|X X ^{-1}X |/ |X|</mml:annotation> </mml:semantics> </mml:math> </inline-formula> bounded is close to a finite subgroup, or else to a subset of a proper algebraic subgroup of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. We also find a connection with Lie groups, and use it to obtain some consequences suggestive of topological nilpotence. Model-theoretically we prove the independence theorem and the stabilizer theorem in a general first-order setting.
Abstract This paper has two parts. In the first one, we prove that an invariant dp-minimal type is either finitely satisfiable or definable. We also prove that a definable version …
Abstract This paper has two parts. In the first one, we prove that an invariant dp-minimal type is either finitely satisfiable or definable. We also prove that a definable version of the (p,q)-theorem holds in dp-minimal theories of small or medium directionality. In the second part, we study dp-rank in dp-minimal theories and show that it enjoys many nice properties. It is continuous, definable in families and it can be characterised geometrically with no mention of indiscernible sequences. In particular, if the structure expands a divisible ordered abelian group, then dp-rank coincides with the dimension coming from the order.
Abstract We consider VC-minimal theories admitting unpackable generating families, and show that in such theories, forking of formulae over a model M is equivalent to containment in global types definable …
Abstract We consider VC-minimal theories admitting unpackable generating families, and show that in such theories, forking of formulae over a model M is equivalent to containment in global types definable over M , generalizing a result of Dolich on o-minimal theories in [4].
We transpose Delon's analysis of types in valued fields to unramified henselian valued fields of mixed characteristic, by using coefficient maps of order $n$. This yields the Ax-Kochen-Ershov transfer principle …
We transpose Delon's analysis of types in valued fields to unramified henselian valued fields of mixed characteristic, by using coefficient maps of order $n$. This yields the Ax-Kochen-Ershov transfer principle for the independence property in this class of valued fields.
Abstract We study dp-minimal and strongly dependent theories and investigate connections between these notions and weight.
Abstract We study dp-minimal and strongly dependent theories and investigate connections between these notions and weight.
We study the action of $G = {\rm SL} (2,\mathbb R)$, viewed as a group definable in the structure $M = (\mathbb R,+,\times )$, on its type space $S_{G}(M)$. We …
We study the action of $G = {\rm SL} (2,\mathbb R)$, viewed as a group definable in the structure $M = (\mathbb R,+,\times )$, on its type space $S_{G}(M)$. We identify a minimal closed $G$-flow $I$ and an idempotent $r\in I$ (with respect to the Ellis se
The main result of this article is sub-additivity of the dp-rank. We also show that the study of theories of finite dp-rank cannot be reduced to the study of its …
The main result of this article is sub-additivity of the dp-rank. We also show that the study of theories of finite dp-rank cannot be reduced to the study of its dp-minimal types, and we discuss the possible relations between dp-rank and VC-density.
A first order theory is totally categorical if it has exactly one model in each infinite power. We prove here that every such theory admits a finite language, and is …
A first order theory is totally categorical if it has exactly one model in each infinite power. We prove here that every such theory admits a finite language, and is finitely axiomatizable in that language, modulo axioms stating that the structure is infinite. This was conjectured by Vaught. We also show that every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ<!-- ℵ --></mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-stable, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ<!-- ℵ --></mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure is a reduct of one that has finitely many models in small uncountable powers. In the case of structures of disintegrated type we nearly find an explicit structure theorem, and show that the remaining obstacle resides in certain nilpotent automorphism groups.
The notion of a randomization of a first-order structure was introduced by Keisler in the paper Randomizing a Model, Advances in Math. 1999. The idea was to form a new …
The notion of a randomization of a first-order structure was introduced by Keisler in the paper Randomizing a Model, Advances in Math. 1999. The idea was to form a new structure whose elements are random elements of the original first-order structure. In this paper we treat randomizations as continuous structures in the sense of Ben Yaacov and Usvyatsov. In this setting, the earlier results show that the randomization of a complete first-order theory is a complete theory in continuous logic that admits elimination of quantifiers and has a natural set of axioms. We show that the randomization operation preserves the properties of being omega-categorical, omega-stable, and stable.
A linearly ordered structure is weakly o-minimal if all of its definable sets in one variable are the union of finitely many convex sets in the structure. Weakly o-minimal structures …
A linearly ordered structure is weakly o-minimal if all of its definable sets in one variable are the union of finitely many convex sets in the structure. Weakly o-minimal structures were introduced by Dickmann, and they arise in several contexts. We here prove several fundamental results about weakly o-minimal structures. Foremost among these, we show that every weakly o-minimal ordered field is real closed. We also develop a substantial theory of definable sets in weakly o-minimal structures, patterned, as much as possible, after that for o-minimal structures.
Abstract This book gives an account of the fundamental results in geometric stability theory, a subject that has grown out of categoricity and classification theory. This approach studies the fine …
Abstract This book gives an account of the fundamental results in geometric stability theory, a subject that has grown out of categoricity and classification theory. This approach studies the fine structure of models of stable theories, using the geometry of forking; this often achieves global results relevant to classification theory. Topics range from Zilber-Cherlin classification of infinite locally finite homogenous geometries, to regular types, their geometries, and their role in superstable theories. The structure and existence of definable groups is featured prominently, as is work by Hrushovski. The book is unique in the range and depth of material covered and will be invaluable to anyone interested in modern model theory.
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of …
A first order theory is NIP if all definable families of subsets have finite VC-dimension. We provide a justification for the intuition that NIP structures should be a combination of stable and order-like components. More precisely, we prove that any type in an NIP theory can be decomposed into a stable part (a generically stable partial type) and an order-like quotient.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
A summary is not available for this content so a preview has been provided. Please use the Get access link above for information on how to access this content.
We prove that in NTP_2 theories if p is a dependent type with dp-rank >= \kappa, then this can be witnessed by indiscernible sequences of tuples satisfying p. If p …
We prove that in NTP_2 theories if p is a dependent type with dp-rank >= \kappa, then this can be witnessed by indiscernible sequences of tuples satisfying p. If p has dp-rank infinity, then this can be witnessed by singletons (in any theory).
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, …
We study definably amenable NIP groups. We develop a theory of generics showing that various definitions considered previously coincide, and we study invariant measures. As applications, we characterize ergodic measures, give a proof of the conjecture of Petrykowski connecting existence of bounded orbits with definable amenability in the NIP case, and prove the Ellis group conjecture of Newelski and Pillay connecting the model-theoretic connected component of an NIP group with the ideal subgroup of its Ellis enveloping semigroup.
A hyperimaginary is an equivalence class of a type-definable equivalence relation on tuples of possibly infinite length. The notion was recently introduced in [1], mainly with reference to simple theories. …
A hyperimaginary is an equivalence class of a type-definable equivalence relation on tuples of possibly infinite length. The notion was recently introduced in [1], mainly with reference to simple theories. It was pointed out there how hyperimaginaries still remain in a sense within the domain of first order logic. In this paper we are concerned with several issues: on the one hand, various levels of complexity of hyperimaginaries, and when hyperimaginaries can be reduced to simpler hyperimaginaries. On the other hand the issue of what information about hyperimaginaries in a saturated structure M can be obtained from the abstract group Aut(M) . In Section 2 we show that if T is simple and canonical bases of Lascar strong types exist in M eq then hyperimaginaries can be eliminated in favour of sequences of ordinary imaginaries. In Section 3, given a type-definable equivalence relation with a bounded number of classes, we show how the quotient space can be equipped with a certain compact topology. In Section 4 we study a certain group introduced in [5], which we call the Galois group of T , develop a Galois theory and make the connection with the ideas in Section 3. We also give some applications, making use of the structure of compact groups. One of these applications states roughly that bounded hyperimaginaries can be eliminated in favour of sequences of finitary hyperimaginaries. In Sections 3 and 4 there is some overlap with parts of Hrushovski's paper [2].
We introduce the notion of a weak generic type in a group. We improve our earlier results on countable coverings of groups and types.
We introduce the notion of a weak generic type in a group. We improve our earlier results on countable coverings of groups and types.
For a dependent theory <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="German upper C Subscript upper T"> <mml:semantics> <mml:msub> …
For a dependent theory <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"> <mml:semantics> <mml:mi>T</mml:mi> <mml:annotation encoding="application/x-tex">T</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="German upper C Subscript upper T"> <mml:semantics> <mml:msub> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="fraktur">C</mml:mi> </mml:mrow> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>T</mml:mi> </mml:mrow> </mml:msub> <mml:annotation encoding="application/x-tex">{\mathfrak {C}}_{T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> for every type definable group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper G"> <mml:semantics> <mml:mi>G</mml:mi> <mml:annotation encoding="application/x-tex">G</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, the intersection of type definable subgroups with bounded index is a type definable subgroup with bounded index.
We study invariant types in NIP theories. Amongst other things: we prove a definable version of the (p,q)-theorem in theories of small or medium directionality; we construct a canonical retraction …
We study invariant types in NIP theories. Amongst other things: we prove a definable version of the (p,q)-theorem in theories of small or medium directionality; we construct a canonical retraction from the space of M-invariant types to that of M-finitely satisfiable types; we show some amalgamation results for invariant types and list a number of open questions.
Our thesis is that for the family of classes of the form EC(T),T a com- plete first order theory with the dependence property (which is just the negation of the …
Our thesis is that for the family of classes of the form EC(T),T a com- plete first order theory with the dependence property (which is just the negation of the independence property) there is a substantial theory which means: a substantial body of basic results for all such classes and some complimentary results for the first order theories with the independence property, as for the family of stable (and the family of simple) first order theories. We examine some properties.
This book addresses a gap in the model-theoretic understanding of valued fields that had limited the interactions of model theory with geometry. It contains significant developments in both pure and …
This book addresses a gap in the model-theoretic understanding of valued fields that had limited the interactions of model theory with geometry. It contains significant developments in both pure and applied model theory. Part I of the book is a study of stably dominated types. These form a subset of the type space of a theory that behaves in many ways like the space of types in a stable theory. This part begins with an introduction to the key ideas of stability theory for stably dominated types. Part II continues with an outline of some classical results in the model theory of valued fields and explores the application of stable domination to algebraically closed valued fields. The research presented here is made accessible to the general model theorist by the inclusion of the introductory sections of each part.
We study definably amenable NIP groups. We develop a theory of generics, showing that various definitions considered previously coincide, and study invariant measures. Applications include: characterization of regular ergodic measures, …
We study definably amenable NIP groups. We develop a theory of generics, showing that various definitions considered previously coincide, and study invariant measures. Applications include: characterization of regular ergodic measures, a proof of the conjecture of Petrykowski connecting existence of bounded orbits with definable amenability in the NIP case, and the Ellis group conjecture of Newelski and Pillay connecting the model-theoretic connected component of an NIP group with the ideal subgroup of its Ellis enveloping semigroup.
Abstract We develop a new notion of independence (ϸ-independence, read “thorn”-independence) that arises from a family of ranks suggested by Scanlon (ϸ-ranks). We prove that in a large class of …
Abstract We develop a new notion of independence (ϸ-independence, read “thorn”-independence) that arises from a family of ranks suggested by Scanlon (ϸ-ranks). We prove that in a large class of theories (including simple theories and o-minimal theories) this notion has many of the properties needed for an adequate geometric structure. We prove that ϸ-independence agrees with the usual independence notions in stable, supersimple and o-minimal theories. Furthermore, we give some evidence that the equivalence between forking and ϸ-forking in simple theories might be closely related to one of the main open conjectures in simplicity theory, the stable forking conjecture. In particular, we prove that in any simple theory where the stable forking conjecture holds, ϸ-independence and forking independence agree.
Abstract We interpret the basic notions of topological dynamics in the model-theoretic setting, relating them to generic types of definable group actions and their generalizations.
Abstract We interpret the basic notions of topological dynamics in the model-theoretic setting, relating them to generic types of definable group actions and their generalizations.