A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of …
A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of axioms. The primary example is forking in a simple theory, but o-minimal theories are also known to have an interesting independence relation. Our approach in this paper is to treat independence relations as mathematical objects worth studying. The main application is a better understanding of thorn-forking, which turns out to be closely related to modular pairs in the lattice of algebraically closed sets.
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is …
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is characterised in terms of modular pairs in the lattice of algebraically closed sets. Wherever possible, forking and thorn-forking are treated in a uniform way. They are dual in the sense that forking is the finest (most restrictive) and thorn-forking the coarsest independence relation worth examining. We finish by defining the kernel of a sequence of indiscernibles and studying its relation to canonical bases.
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as …
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as forking, dividing, thorn-forking, thorn-dividing, splitting or finite satisfiability share in all complete theories. We examine the relation between four additional axioms (extension, local character, full existence and symmetry) that one expects of a good notion of independence. We show that thorn-forking can be described in terms of local forking if we localize the number k in Kim's notion of "dividing with respect to k" (using Ben-Yaacov's "k-inconsistency witnesses") rather than the forking formulas. It follows that every theory with an M-symmetric lattice of algebraically closed sets (in T eq ) is rosy, with a simple lattice theoretical interpretation of thorn-forking.
Abstract We prove two results about generically stable types p in arbitrary theories. The first, on existence of strong germs, generalizes results from [2] on stably dominated types. The second …
Abstract We prove two results about generically stable types p in arbitrary theories. The first, on existence of strong germs, generalizes results from [2] on stably dominated types. The second is an equivalence of forking and dividing, assuming generic stability of p ( m ) for all m . We use the latter result to answer in full generality a question posed by Hasson and Onshuus: If P ( x ) ε S ( B ) is stable and does not fork over A then prestrictionA is stable. (They had solved some special cases.)
We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected by allowing fusion of …
We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected by allowing fusion of elements.
A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe …
A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe that this tameness notion from algorithmic graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property.
Abstract We prove two results about generically stable types p in arbitrary theories. The first, on existence of strong germs, generalizes results from [2] on stably dominated types. The second …
Abstract We prove two results about generically stable types p in arbitrary theories. The first, on existence of strong germs, generalizes results from [2] on stably dominated types. The second is an equivalence of forking and dividing, assuming generic stability of p ( m ) for all m . We use the latter result to answer in full generality a question posed by Hasson and Onshuus: If P ( x ) ε S ( B ) is stable and does not fork over A then prestrictionA is stable. (They had solved some special cases.)
A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe …
A class of graphs is nowhere dense if for every integer r there is a finite upper bound on the size of cliques that occur as (topological) r-minors. We observe that this tameness notion from algorithmic graph theory is essentially the earlier stability theoretic notion of superflatness. For subgraph-closed classes of graphs we prove equivalence to stability and to not having the independence property.
A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of …
A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of axioms. The primary example is forking in a simple theory, but o-minimal theories are also known to have an interesting independence relation. Our approach in this paper is to treat independence relations as mathematical objects worth studying. The main application is a better understanding of thorn-forking, which turns out to be closely related to modular pairs in the lattice of algebraically closed sets.
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as …
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as forking, dividing, thorn-forking, thorn-dividing, splitting or finite satisfiability share in all complete theories. We examine the relation between four additional axioms (extension, local character, full existence and symmetry) that one expects of a good notion of independence. We show that thorn-forking can be described in terms of local forking if we localize the number k in Kim's notion of "dividing with respect to k" (using Ben-Yaacov's "k-inconsistency witnesses") rather than the forking formulas. It follows that every theory with an M-symmetric lattice of algebraically closed sets (in T eq ) is rosy, with a simple lattice theoretical interpretation of thorn-forking.
We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected by allowing fusion of …
We give a simple proof that the straightforward generalisation of clique-width to arbitrary structures can be unbounded on structures of bounded tree-width. This can be corrected by allowing fusion of elements.
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is …
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is characterised in terms of modular pairs in the lattice of algebraically closed sets. Wherever possible, forking and thorn-forking are treated in a uniform way. They are dual in the sense that forking is the finest (most restrictive) and thorn-forking the coarsest independence relation worth examining. We finish by defining the kernel of a sequence of indiscernibles and studying its relation to canonical bases.
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is …
An axiomatic treatment of `independence relations' (notions of independence) for complete first-order theories is presented, the principal examples being forking (due to Shelah) and thorn-forking (due to Onshuus). Thorn-forking is characterised in terms of modular pairs in the lattice of algebraically closed sets. Wherever possible, forking and thorn-forking are treated in a uniform way. They are dual in the sense that forking is the finest (most restrictive) and thorn-forking the coarsest independence relation worth examining. We finish by defining the kernel of a sequence of indiscernibles and studying its relation to canonical bases.
We continue [2], developing simplicity in the framework of compact abstract theories. Due to the generality of the context we need to introduce definitions which differ somewhat from the ones …
We continue [2], developing simplicity in the framework of compact abstract theories. Due to the generality of the context we need to introduce definitions which differ somewhat from the ones use in first order theories. With these modified tools we obtain more or less classical behaviour: simplicity is characterized by the existence of a certain notion of independence, stability is characterized by simplicity and bounded multiplicity, and hyperimaginary canonical bases exist.
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.
We prove a property of generic homogeneity of tuples starting an infinite indiscernible sequence in a simple theory and we use it to give a shorter proof of the Independence …
We prove a property of generic homogeneity of tuples starting an infinite indiscernible sequence in a simple theory and we use it to give a shorter proof of the Independence Theorem for Lascar strong types. We also characterize the relation of starting an infinite indiscernible sequence in terms of coheirs.
Abstract notions of “smallness” are among the most important tools that model theory offers for the analysis of arbitrary structures. The two most useful notions of this kind are forking …
Abstract notions of “smallness” are among the most important tools that model theory offers for the analysis of arbitrary structures. The two most useful notions of this kind are forking (which is closely related to certain measure zero ideals) and thorn-forking (which generalizes the usual topological dimension). Under certain mild assumptions, forking is the finest notion of smallness, whereas thorn-forking is the coarsest. In this paper we study forking and thorn-forking, restricting ourselves to the class of generically stable types. Our main conclusion is that in this context these two notions coincide. We explore some applications of this equivalence.
Abstract We consider the notion of bounded m -ary patch-width defined in [9], and its very close relative m -constructibility defined below. We show that the notions of m -constructibility …
Abstract We consider the notion of bounded m -ary patch-width defined in [9], and its very close relative m -constructibility defined below. We show that the notions of m -constructibility all coincide for m ≥ 3, while 1-constructibility is a weaker notion. The same holds for bounded m -ary patch-width. The case m = 2 is left open.
We define the class of thick cats (compact abstract theories, which contains in particular semi-Hausdorff, Hausdorff and first order cats), and prove that in this class simplicity behaves as in …
We define the class of thick cats (compact abstract theories, which contains in particular semi-Hausdorff, Hausdorff and first order cats), and prove that in this class simplicity behaves as in first order theories. We consider well-known first order n
We show that a class of subsets of a structure uniformly definable by a first-order formula is a Vapnik-Chervonenkis class if and only if the formula does not have the …
We show that a class of subsets of a structure uniformly definable by a first-order formula is a Vapnik-Chervonenkis class if and only if the formula does not have the independence property. Via this connection we obtain several new examples of Vapnik-Chervonenkis classes, including sets of positivity of finitely subanalytic functions.
Abstract We examine several conditions, either the existence of a rank or a particular property of þ-forking that suggest the existence of a well-behaved independence relation, and determine the consequences …
Abstract We examine several conditions, either the existence of a rank or a particular property of þ-forking that suggest the existence of a well-behaved independence relation, and determine the consequences of each of these conditions towards the rosiness of the theory. In particular we show that the existence of an ordinal valued equivalence relation rank is a (necessary and) sufficient condition for rosiness.
Abstract Firstly, in this paper, we prove that the equivalence of simplicity and the symmetry of forking. Secondly, we attempt to recover definability part of stability theory to simplicity theory. …
Abstract Firstly, in this paper, we prove that the equivalence of simplicity and the symmetry of forking. Secondly, we attempt to recover definability part of stability theory to simplicity theory. In particular, using elimination of hyperimaginaries we prove that for any supersimple T . canonical base of an amalgamation class is the union of names of ψ -definitions of , ψ ranging over stationary L -formulas in . Also, we prove that the same is true with stable formulas for an 1-based theory having elimination of hyperimaginaries. For such a theory, the stable forking property holds, too.
Abstract We study the behaviour of stable types in rosy theories. The main technical result is that a non-þ-forking extension of an unstable type is unstable. We apply this to …
Abstract We study the behaviour of stable types in rosy theories. The main technical result is that a non-þ-forking extension of an unstable type is unstable. We apply this to show that a rosy group with a þ-generic stable type is stable. In the context of super-rosy theories of finite rank we conclude that non-trivial stable types of U þ -rank 1 must arise from definable stable sets.
Abstract Let T be a one-based theory. We define a notion of width, in the case of T having the finiteness property, for the lattice of finitely generated algebraically closed …
Abstract Let T be a one-based theory. We define a notion of width, in the case of T having the finiteness property, for the lattice of finitely generated algebraically closed sets and prove Theorem. Let T be one-based with the finiteness property. If T is of bounded width, then every type in T is nonorthogonal to a weight one type. If T is countable, the converse is true .
Abstract A set A of vertices of a graph G is called d -scattered in G if no two d -neighborhoods of (distinct) vertices of A intersect. In other words, …
Abstract A set A of vertices of a graph G is called d -scattered in G if no two d -neighborhoods of (distinct) vertices of A intersect. In other words, A is d -scattered if no two distinct vertices of A have distance at most 2d. This notion was isolated in the context of finite model theory by Ajtai and Gurevich and recently it played a prominent role in the study of homomorphism preservation theorems for special classes of structures (such as minor closed classes). This in turn led to the notions of wide, almost wide and quasi-wide classes of graphs. It has been proved previously that minor closed classes and classes of graphs with locally forbidden minors are examples of such classes and thus (relativized) homomorphism preservation theorem holds for them. In this paper we show that (more general) classes with bounded expansion and (newly defined) classes with bounded local expansion and even (very general) nowhere dense classes are quasi wide. This not only strictly generalizes the previous results but it also provides new proofs and algorithms for some of the old results. It appears that bounded expansion and nowhere dense classes are perhaps a proper setting for investigation of wide-type classes as in several instances we obtain a structural characterization. This also puts classes of bounded expansion in the new context. Our motivation stems from finite dualities. As a corollary we obtain that any homomorphism closed first order definable property restricted to a bounded expansion class is a restricted duality.
A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of …
A ternary relation [Formula: see text] between subsets of the big model of a complete first-order theory T is called an independence relation if it satisfies a certain set of axioms. The primary example is forking in a simple theory, but o-minimal theories are also known to have an interesting independence relation. Our approach in this paper is to treat independence relations as mathematical objects worth studying. The main application is a better understanding of thorn-forking, which turns out to be closely related to modular pairs in the lattice of algebraically closed sets.
We study the notions generic stability, regularity, homogeneous pregeometries, quasiminimality, and their mutual relations, in arbitrary first order theories. We prove that “infinite-dimensional homogeneous pregeometries” coincide with generically stable strongly …
We study the notions generic stability, regularity, homogeneous pregeometries, quasiminimality, and their mutual relations, in arbitrary first order theories. We prove that “infinite-dimensional homogeneous pregeometries” coincide with generically stable strongly regular types (p(x), x = x). We prove that in a theory without the strict order property, regular types are generically stable, and prove analogous results for quasiminimal structures. We prove that the “generic type” of a quasiminimal structure is “locally strongly regular”.
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.
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as …
We introduce the notion of a preindependence relation between subsets of the big model of a complete first-order theory, an abstraction of the properties which numerous concrete notions such as forking, dividing, thorn-forking, thorn-dividing, splitting or finite satisfiability share in all complete theories. We examine the relation between four additional axioms (extension, local character, full existence and symmetry) that one expects of a good notion of independence. We show that thorn-forking can be described in terms of local forking if we localize the number k in Kim's notion of "dividing with respect to k" (using Ben-Yaacov's "k-inconsistency witnesses") rather than the forking formulas. It follows that every theory with an M-symmetric lattice of algebraically closed sets (in T eq ) is rosy, with a simple lattice theoretical interpretation of thorn-forking.
Abstract. We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic ( CMSOL ) using one binary relation symbol and finitely many unary relation symbols, …
Abstract. We show that the spectrum of a sentence ϕ in Counting Monadic Second Order Logic ( CMSOL ) using one binary relation symbol and finitely many unary relation symbols, is ultimately periodic, provided all the models of ϕ are of clique width at most k , for some fixed k . We prove a similar statement for arbitrary finite relational vocabularies τ and a variant of clique width for τ -structures. This includes the cases where the models of ϕ are of tree width at most k . For the case of bounded tree-width, the ultimate periodicity is even proved for Guarded Second Order Logic GSOL . We also generalize this result to many-sorted spectra, which can be viewed as an analogue of Parikh's Theorem on context-free languages, and its analogues for context-free graph grammars due to Habel and Courcelle. Our work was inspired by Gurevich and Shelah (2003), who showed ultimate periodicity of the spectrum for sentences of Monadic Second Order Logic where only finitely many unary predicates and one unary function are allowed. This restriction implies that the models are all of tree width at most 2, and hence it follows from our result.
We investigate the parameterized complexity of generalisations and variations of the dominating set problem on classes of graphs that are nowhere dense. In particular, we show that the distance-$d$ dominating-set …
We investigate the parameterized complexity of generalisations and variations
of the dominating set problem on classes of graphs that are nowhere dense. In
particular, we show that the distance-$d$ dominating-set problem, also known
as the $(k,d)$-centres problem, is fixed-parameter tractable on any class that
is nowhere dense and closed under induced subgraphs. This generalises known
results about the dominating set problem on $H$-minor free classes, classes
with locally excluded minors and classes of graphs of bounded expansion. A
key feature of our proof is that it is based simply on the fact that these
graph classes are uniformly quasi-wide, and does not rely on a structural
decomposition. Our result also establishes that the distance-$d$
dominating-set problem is FPT on classes of bounded expansion, answering a
question of Ne{\v s}et{\v r}il and Ossona de Mendez.
We prove some results on the border of Ramsey theory (finite partition calculus) and model theory. Also a beginning of classification theory for classes of finite models is undertaken.
We prove some results on the border of Ramsey theory (finite partition calculus) and model theory. Also a beginning of classification theory for classes of finite models is undertaken.
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.
In a previous paper we developed the notions of th-independence and þ-ranks which define a geometric independence relation in a class of theories which we called ``rosy''. We proved that …
In a previous paper we developed the notions of th-independence and þ-ranks which define a geometric independence relation in a class of theories which we called ``rosy''. We proved that rosy theories include simple and o-minimal theories and that for any theory for which the stable forking conjecture was true, þ-forking coincides with forking independence. In this article, we continue to study properties of th-forking and find more examples of rosy theories. Among the new properties we prove in this paper are some alternative characterizations of rosy theories and some tools to prove and analyze rosiness in particular cases. Finally, we use this to find two examples of rosy non simple theories: pseudo real closed fields (PRC-fields) and the uniform companion of a large differential field defined by Marcus Tressl.
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.