CLASSIFICATION THEORY FOR ELEMENTARY CLASSES WITH THE DEPENDENCE PROPERTY-A MODEST BEGINNING

Authors

Saharon Shelah

Type: Article

Publication Date: 2004-03-01

Citations: 40

View

Abstract

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.

Locations

Scientiae mathematicae Japonicae
View

Classification theory for theories with NIP - a modest beginning

2000-01-01

Saharon Shelah

A relevant thesis is that for the family of complete first order theories with NIP (i.e. without the independence property) there is a substantial theory, like the family of stable … A relevant thesis is that for the family of complete first order theories with NIP (i.e. without the independence property) there is a substantial theory, like the family of stable (and the family of simple) first order theories. We examine some properties.

Introduction to: classification theory for abstract elementary class

2009-01-01

Saharon Shelah

Classification theory of elementary classes deals with first order (elementary) classes of structures (i.e. fixing a set T of first order sentences, we investigate the class of models of T … Classification theory of elementary classes deals with first order (elementary) classes of structures (i.e. fixing a set T of first order sentences, we investigate the class of models of T with the elementary submodel notion). It tries to find dividing lines, prove their consequences, prove "structure theorems, positive theorems" on those in the "low side" (in particular stable and superstable theories), and prove "non-structure, complexity theorems" on the "high side". It has started with categoricity and number of non-isomorphic models. It is probably recognized as the central part of model theory, however it will be even better to have such (non-trivial) theory for non-elementary classes. Note also that many classes of structures considered in algebra are not first order; some families of such classes are close to first order (say have kind of compactness). But here we shall deal with a classification theory for the more general case without assuming knowledge of the first order case (and in most parts not assuming knowledge of model theory at all). The present paper includes an introduction to the forthcoming book on Classification Theory for Abstract Elementary Classes

Classification theory for non-elementary classes

2008-04-01

NSOP$_1$-like independence in AECats

2021-01-01

Mark Kamsma

The classes stable, simple and NSOP$_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them there is … The classes stable, simple and NSOP$_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them there is a canonicity theorem: there can be at most one nice independence relation. Independence in stable and simple first-order theories must come from forking and dividing (which then coincide), and for NSOP$_1$ theories it must come from Kim-dividing. We generalise this work to the framework of AECats (Abstract Elementary Categories) with the amalgamation property. These are a certain kind of accessible category generalising the category of (subsets of) models of some theory. We prove canonicity theorems for stable, simple and NSOP$_1$-like independence relations. The stable and simple cases have been done before in slightly different setups, but we provide them here as well so that we can recover part of the original stability hierarchy. We also provide abstract definitions for each of these independence relations as what we call isi-dividing, isi-forking and long Kim-dividing.

View PDF Chat

Dependent theories and the generic pair conjecture

2014-10-20

Saharon Shelah

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.

View PDF Chat

Dependent theories and the generic pair conjecture

2007-01-01

Saharon Shelah

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 … 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.

View PDF Chat

Dependent theories and the generic pair conjecture

2007-02-10

Saharon Shelah

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 … 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.

NSOP-LIKE INDEPENDENCE IN AECATS

2022-12-12

Mark Kamsma

Abstract The classes stable, simple, and NSOP $_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them … Abstract The classes stable, simple, and NSOP $_1$ in the stability hierarchy for first-order theories can be characterised by the existence of a certain independence relation. For each of them there is a canonicity theorem: there can be at most one nice independence relation. Independence in stable and simple first-order theories must come from forking and dividing (which then coincide), and for NSOP $_1$ theories it must come from Kim-dividing. We generalise this work to the framework of Abstract Elementary Categories (AECats) with the amalgamation property. These are a certain kind of accessible category generalising the category of (subsets of) models of some theory. We prove canonicity theorems for stable, simple, and NSOP $_1$ -like independence relations. The stable and simple cases have been done before in slightly different setups, but we provide them here as well so that we can recover part of the original stability hierarchy. We also provide abstract definitions for each of these independence relations as what we call isi-dividing, isi-forking, and long Kim-dividing.

View PDF Chat

On generically stable types in dependent theories

2007-01-01

Alexander Usvyatsov

We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent (NIP) theories. We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent (NIP) theories.

Introduction to theories without the independence property

2008-01-01

Hans H. Adler

We present an updated exposition of the classical theory of complete first order theories without the independence property (also called NIP theories or dependent theories). We present an updated exposition of the classical theory of complete first order theories without the independence property (also called NIP theories or dependent theories).

Local order property in nonelementary classes

2000-08-01

Rami Grossberg , Olivier Lessmann

Independence in 𝜔-stable classes

2009-07-24

John T. Baldwin

A strong base of elementary types of theories

1978-01-01

T. G. Mustafin

Generic Stability Independence and Treeless theories

2023-01-01

Itay Kaplan , Nicholas Ramsey , Pierre Simon

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.

View PDF Chat

A Proof and Formalization of the Initiality Conjecture of Dependent Type Theory

2020-01-01

Menno de Boer

In this licentiate thesis we present a proof of the initiality conjecture for Martin-Lof’s type theory with 0, 1, N, A+B, ∏AB, ∑AB, IdA(u,v), countable hierarchy of universes (Ui)iєN closed … In this licentiate thesis we present a proof of the initiality conjecture for Martin-Lof’s type theory with 0, 1, N, A+B, ∏AB, ∑AB, IdA(u,v), countable hierarchy of universes (Ui)iєN closed under t ...

On generically stable types in dependent theories

2009-01-04

Alexander Usvyatsov

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.

View PDF Chat

Ranks for strongly dependent theories

2013-01-01

M. Cohen , Saharon Shelah

There is much more known about the family of superstable theories when compared to stable theories. This calls for a search of an analogous "super-dependent" characterization in the context of … There is much more known about the family of superstable theories when compared to stable theories. This calls for a search of an analogous "super-dependent" characterization in the context of dependent theories. This problem has been treated in \cite{Sh:783,Sh:863}, where the candidates "Strongly dependent", "Strongly dependent^2" and others were considered. These families generated new families when we are considering intersections with the stable family. Here, continuing \cite[§2, §5E,F,G]{Sh:863}, we deal with several candidates, defined using dividing properties and related ranks of types. Those candidates are subfamilies of "Strongly dependent". Fulfilling some promises from \cite{Sh:863} in particular \cite[1.4(4)]{Sh:863}, we try to make this self contained within reason by repeating some things from there. More specifically we fulfil some promises from \cite{Sh:863} to to give more details, in particular: in \S4 for \cite[1.4(4)]{Sh:863}, in \S2 for \cite[5.47(2)=Ldw5.35(2)]{Sh:863} and in \S1 for \cite[5.49(2)]{Sh:863}

Generic Stability Independence and Treeless Theories

2024-01-01

Itay Kaplan , Nicholas Ramsey , Pierre Simon

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.

View PDF Chat

Examples in dependent theories

2010-01-01

Itay Kaplan , Saharon Shelah

In the first part we show a counterexample to a conjecture by Shelah regarding the existence of indiscernible sequences in dependent theories (up to the first inaccessible cardinal). In the … In the first part we show a counterexample to a conjecture by Shelah regarding the existence of indiscernible sequences in dependent theories (up to the first inaccessible cardinal). In the second part we discuss generic pairs, and give an example where the pair is not dependent. Then we define the notion of directionality which deals with counting the number of coheirs of a type and we give examples of the different possibilities. Then we discuss non-splintering, an interesting notion that appears in the work of Rami Grossberg, Andr\'es Villaveces and Monica VanDieren, and we show that it is not trivial (in the sense that it can be different than splitting) whenever the directionality of the theory is not small. In the appendix we study dense types in RCF.

View PDF Chat

Examples in dependent theories

2010-09-28

Itay Kaplan , Saharon Shelah

THEORIES WITH DISTAL SHELAH EXPANSIONS

2023-03-08

Gareth Boxall , Charlotte Kestner

Abstract We show that a complete first-order theory T is distal provided it has a model M such that the theory of the Shelah expansion of M is distal. Abstract We show that a complete first-order theory T is distal provided it has a model M such that the theory of the Shelah expansion of M is distal.

View PDF Chat

Introduction to theories without the independence property

2008-01-01

Hans H. Adler

A note on stable sets, groups, and theories with NIP

2007-05-18

Alf Onshuus , Ya’acov Peterzil

Abstract Let M be an arbitrary structure. Then we say that an M ‐formula φ ( x ) defines a stable set in M if every formula φ ( x … Abstract Let M be an arbitrary structure. Then we say that an M ‐formula φ ( x ) defines a stable set in M if every formula φ ( x ) ∧ α ( x , y ) is stable. We prove: If G is an M ‐definable group and every definable stable subset of G has U ‐rank at most n (the same n for all sets), then G has a maximal connected stable normal subgroup H such that G / H is purely unstable. The assumptions hold for example if M is interpretable in an o‐minimal structure. More generally, an M ‐definable set X is weakly stable if the M ‐induced structure on X is stable. We observe that, by results of Shelah, every weakly stable set in theories with NIP is stable. (© 2007 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)

Groups, measures, and the NIP

2007-02-02

Ehud Hrushovski , Ya’acov Peterzil , Anand Pillay

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.

View PDF Chat

Groups, measures, and the NIP

2006-01-01

Ehud Hrushovski , Ya’acov Peterzil , Anand Pillay

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 a new notion "compact domination" (domination of a definable set by a compact space) and raise some new conjectures in the $o$-minimal case.

Density of compressible types and some consequences

2024-02-18

Martin Bays , Itay Kaplan , Pierre Simon

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.

View PDF Chat

Regular partitions of gentle graphs

2020-07-22

Yiting Jiang , Jaroslav Nešetřil , Patrice Ossona de Mendez +1 more

View PDF Chat

Remarks on generic stability in independent theories

2019-09-05

Gabriel Conant , Kyle Gannon

View PDF Chat

On a common generalization of Shelah's 2-rank, dp-rank, and o-minimal dimension

2014-12-30

Vincent Guingona , Cameron Donnay Hill

View PDF Chat

Minimal stable types in Banach spaces

2019-08-19

Saharon Shelah , Alexander Usvyatsov

View PDF Chat

Distal and non-distal NIP theories

2012-11-01

Pierre Simon

View PDF Chat

Additivity of the dp-rank

2013-07-01

Itay Kaplan , Alf Onshuus , Alexander Usvyatsov

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.

Simple monadic theories and partition width

2011-05-02

Achim Blumensath

We study tree-like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the … We study tree-like decompositions of models of a theory and a related complexity measure called partition width. We prove a dichotomy concerning partition width and definable pairing functions: either the partition width of models is bounded, or the theory admits definable pairing functions. Our proof rests on structure results concerning indiscernible sequences and finitely satisfiable types for theories without definable pairing functions. © 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim

The characteristic sequence of a first-order formula

2010-10-04

M. Malliaris

Abstract For a first-order formula φ(x; y) we introduce and study the characteristic sequence ( P n : n < ω ) of hypergraphs defined by . We show that … Abstract For a first-order formula φ(x; y) we introduce and study the characteristic sequence ( P n : n < ω ) of hypergraphs defined by . We show that combinatorial and classification theoretic properties of the characteristic sequence reflect classification theoretic properties of φ and vice versa. The main results are a characterization of NIP and of simplicity in terms of persistence of configurations in the characteristic sequence. Specifically, we show that some tree properties are detected by the presence of certain combinatorial configurations in the characteristic sequence while other properties such as instability and the independence property manifest themselves in the persistence of complicated configurations under localization.

On generically stable types in dependent theories

2009-01-04

Alexander Usvyatsov

View PDF Chat

On Definability of Types in Dependent Theories

2011-01-01

Vincent Guingona

Title of dissertation: ON DEFINABILITY OF TYPES IN DEPENDENT THEORIES Vincent Guingona, Doctor of Philosophy, 2011 Dissertation directed by: Professor Michael Chris Laskowski Department of Mathematics Using definability of types … Title of dissertation: ON DEFINABILITY OF TYPES IN DEPENDENT THEORIES Vincent Guingona, Doctor of Philosophy, 2011 Dissertation directed by: Professor Michael Chris Laskowski Department of Mathematics Using definability of types for stable formulas, one develops the powerful tools of stability theory, such as canonical bases, a nice forking calculus, and stable embeddability. When one passes to the class of dependent formulas, this notion of definability of types is lost. However, as this dissertation shows, we can recover suitable alternatives to definability of types for some dependent theories. Using these alternatives, we can recover some of the power of stability theory. One alternative is uniform definability of types over finite sets (UDTFS). We show that all formulas in dp-minimal theories have UDTFS, as well as formulas with VC-density < 2. We also show that certain Henselian valued fields have UDTFS. Another alternative is isolated extensions. We show that dependent formulas are characterized by the existence of isolated extensions, and show how this gives a weak stable embeddability result. We also explore the idea of UDTFS rank and show how it relates to VC-density. Finally, we use the machinery developed in this dissertation to show that VCminimal theories satisfy the Kueker Conjecture. ON DEFINABILITY OF TYPES IN DEPENDENT THEORIES

Persistence and NIP in the characteristic sequence

2009-01-01

M. Malliaris

For a first-order formula $\phi(x;y)$ we introduce and study the characteristic sequence $<P_n : n < \omega>$ of hypergraphs defined by $P_n(y_1,...,y_n) := (\exists x) \bigwedge_{i \leq n} \phi(x;y_i)$. We … For a first-order formula $\phi(x;y)$ we introduce and study the characteristic sequence $<P_n : n < \omega>$ of hypergraphs defined by $P_n(y_1,...,y_n) := (\exists x) \bigwedge_{i \leq n} \phi(x;y_i)$. We show that combinatorial and classification theoretic properties of the characteristic sequence reflect classification theoretic properties of $\phi$ and vice versa. Specifically, we show that some tree properties are detected by the presence of certain combinatorial configurations in the characteristic sequence while other properties such as instability and the independence property manifest themselves in the persistence of complicated configurations under localization.

View PDF Chat

RAMSEY GROWTH IN SOME NIP STRUCTURES

2019-02-19

Artem Chernikov , Sergei Starchenko , Margaret E. M. Thomas

Abstract We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek ( Duke Mathematical … Abstract We investigate bounds in Ramsey’s theorem for relations definable in NIP structures. Applying model-theoretic methods to finitary combinatorics, we generalize a theorem of Bukh and Matousek ( Duke Mathematical Journal 163 (12) (2014), 2243–2270) from the semialgebraic case to arbitrary polynomially bounded $o$ -minimal expansions of $\mathbb{R}$ , and show that it does not hold in $\mathbb{R}_{\exp }$ . This provides a new combinatorial characterization of polynomial boundedness for $o$ -minimal structures. We also prove an analog for relations definable in $P$ -minimal structures, in particular for the field of the $p$ -adics. Generalizing Conlon et al. ( Transactions of the American Mathematical Society 366 (9) (2014), 5043–5065), we show that in distal structures the upper bound for $k$ -ary definable relations is given by the exponential tower of height $k-1$ .

View PDF Chat

Strict independence

2014-06-23

Itay Kaplan , Alexander Usvyatsov

We investigate the notions of strict independence and strict non-forking, and establish basic properties and connections between the two. In particular, it follows from our investigation that in resilient theories … We investigate the notions of strict independence and strict non-forking, and establish basic properties and connections between the two. In particular, it follows from our investigation that in resilient theories strict non-forking is symmetric. Based on this study, we develop notions of weight which characterize NTP 2 , dependence and strong dependence. Many of our proofs rely on careful analysis of sequences that witness dividing. We prove simple characterizations of such sequences in resilient theories, as well as of Morley sequences which are witnesses. As a by-product we obtain information on types co-dominated by generically stable types in dependent theories. For example, we prove that every Morley sequence in such a type is a witness.

Model-theoretic applications of cofinality spectrum problems

2017-05-08

M. Malliaris , Saharon Shelah

View PDF Chat

Stability Theoretic Methods in Unstable Theories

2009-01-01

Bradd Hart , Alf Onshuus , Anand Pillay +2 more

The idea of applying methods and results from stability theory to unstable theories has been an important theme over the past 25 years, with o-minimality, smoothly approximable structures, and simple … The idea of applying methods and results from stability theory to unstable theories has been an important theme over the past 25 years, with o-minimality, smoothly approximable structures, and simple theories being key examples. But there have been some key recent developments which bring new ideas and techniques to the table. One of these is the investigation of abstract notions of independence, leading for example to the notions of thorn forking and rosiness. Another is the discovery that forking, weight, and related notions from stability are meaningful in dependent theories. Another is the formulation of notions of stable, compact, or more general domination, coming from the analysis of theories such as algebraically closed valued fields and o-minimal theories. The level of different approaches and techniques which end up overlapping was the reason we decided it would be a perfect time for a research meeting where the most prominent researchers would come together and discuss the ideas, results and goals that were showing up in different contexts. The dominant subjects of the meeting were the following.

A monotonicity theorem for dp-minimal densely ordered groups

2010-01-25

John Goodrick

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).

On dp-minimal ordered structures

2011-05-19

Pierre Simon

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.

View PDF Chat

Dependent theories and the generic pair conjecture

2014-10-20

Saharon Shelah

View PDF Chat

Dependent first order theories, continued

2009-09-01

Saharon Shelah

View PDF Chat

Regularity lemmas for stable graphs

2013-08-29

M. Malliaris , Saharon Shelah

We develop a framework in which Szemerédi's celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory … We develop a framework in which Szemerédi's celebrated Regularity Lemma for graphs interacts with core model-theoretic ideas and techniques. Our work relies on a coincidence of ideas from model theory and graph theory: arbitrarily large half-graphs coincide with model-theoretic instability, so in their absence, structure theorems and technology from stability theory apply. In one direction, we address a problem from the classical Szemerédi theory. It was known that the "irregular pairs" in the statement of Szemerédi's Regularity Lemma cannot be eliminated, due to the counterexample of half-graphs (i.e., the order property, corresponding to model-theoretic instability). We show that half-graphs are the only essential difficulty, by giving a much stronger version of Szemerédi's Regularity Lemma for models of stable theories of graphs (i.e. graphs with the non-$k_*$-order property), in which there are no irregular pairs, the bounds are significantly improved, and each component satisfies an indivisibility condition. In the other direction, we take a more model-theoretic approach, and give several new Szemerédi-type partition theorems for models of stable theories of graphs. The first theorem gives a partition of any such graph into indiscernible components, meaning here that each component is either a complete or an empty graph, whose interaction is strongly uniform. This relies on a finitary version of the classic model-theoretic fact that stable theories admit large sets of indiscernibles, by showing that in models of stable theories of graphs one can extract much larger indiscernible sets than expected by Ramsey's theorem. The second and third theorems allow for a much smaller number of components at the cost of weakening the "indivisibility" condition on the components. We also discuss some extensions to graphs without the independence property. All graphs are finite and all partitions are equitable, i.e. the sizes of the components differ by at most 1. In the last three theorems, the number of components depends on the size of the graph; in the first theorem quoted, this number is a function of $\epsilon$ only as in the usual Szemerédi Regularity Lemma.

View PDF Chat

Finding generically stable measures

2012-01-20

Pierre Simon

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.

View PDF Chat

Generic stability, forking, and þ-forking

2012-07-24

Darío García , Alf Onshuus , Alexander Usvyatsov

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.

Strongly dependent theories

2014-07-28

Saharon Shelah

View PDF Chat

Definable valuations induced by multiplicative subgroups and NIP fields

2019-02-09

Katharina Dupont , Assaf Hasson , Salma Kuhlmann

View PDF Chat

Strict independence in dependent theories

2012-08-20

Itay Kaplan , Alexander Usvyatsov

We investigate the notions of strict independence and strict non-forking, and establish basic properties and connections between the two. In particular it follows from our investigation that in resilient theories … We investigate the notions of strict independence and strict non-forking, and establish basic properties and connections between the two. In particular it follows from our investigation that in resilient theories strict non-forking is symmetric. Based on this study, we develop notions of weight which characterize NTP2, dependence and strong dependence. Many of our proofs rely on careful analysis of sequences that witness dividing. We prove simple characterizations of such sequences in resilient theories, as well as of Morley sequences which are witnesses. As a by-product we obtain information on types co-dominated by generically stable types in dependent theories. For example, we prove that every Morley sequence in such a type is a witness.

Stable types in rosy theories

2010-10-04

Assaf Hasson , Alf Onshuus

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.

Simple monadic theories and indiscernibles

2011-02-01

Achim Blumensath

Aiming for applications in monadic second-order model theory, we study first-order theories without definable pairing functions. Our main results concern forking-properties of sequences of indiscernibles. These turn out to be … Aiming for applications in monadic second-order model theory, we study first-order theories without definable pairing functions. Our main results concern forking-properties of sequences of indiscernibles. These turn out to be very well-behaved for the theories under consideration (© 2011 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)

DEPENDENT FIRST ORDER THEORIES, CONTINUED SH783

2015-01-01

Saharon Shelah

A dependent theory is a (first order complete theory) which does not have the independence property. A major result here is: if we expand a model of by the traces … A dependent theory is a (first order complete theory) which does not have the independence property. A major result here is: if we expand a model of by the traces on it of sets definable in a bigger model then we preserve its being dependent. Another one justifies the cofinality restriction in the theorem (from a previous work) saying that pairwise perpendicular indiscernible sequences, can have arbitrary dual-cofinalities in some models containing them. We introduce strongly dependent T and look at definable groups in such models; also look at forking and relatives.

On Vapnik‐Chervonenkis density over indiscernible sequences

2014-01-29

Vincent Guingona , Cameron Donnay Hill

In this paper, we study Vapnik‐Chervonenkis density (VC‐density) over indiscernible sequences (denoted VC ind ‐density). We answer an open question in [1], showing that VC ind ‐density is always integer … In this paper, we study Vapnik‐Chervonenkis density (VC‐density) over indiscernible sequences (denoted VC ind ‐density). We answer an open question in [1], showing that VC ind ‐density is always integer valued. We also show that VC ind ‐density and dp‐rank coincide in the natural way.

Nowhere dense graph classes, stability, and the independence property

2010-01-01

Hans H. Adler , Isolde Adler

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.

On NIP and invariant measures

2011-05-13

Ehud Hrushovski , Anand Pillay

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.

View PDF Chat

On what I do not understand (and have something to say), model theory

1999-01-01

Saharon Shelah

This is a non-standard paper, containing some problems, mainly in model theory, which I have, in various degrees, been interested in. Sometimes with a discussion on what I have to … This is a non-standard paper, containing some problems, mainly in model theory, which I have, in various degrees, been interested in. Sometimes with a discussion on what I have to say; sometimes, of what makes them interesting to me, sometimes the problems are presented with a discussion of how I have tried to solve them, and sometimes with failed tries, anecdote and opinion. So the discussion is quite personal, in other words, egocentric and somewhat accidental. As we discuss many problems, history and side references are erratic, usually kept at a minimum ("See..." means: see the references there and possibly the paper itself). The base were lectures in Rutgers Fall '97 and reflect my knowledge then. The other half, math.LO/9906113, concentrating on set theory, is in print, but the two halves are independent. We thank A. Blass, G. Cherlin and R. Grossberg for some corrections.

Proper and Improper Forcing

1998-01-01

Saharon Shelah

This work deals with set-theoretic independence results (independence from the usual set-theoretic ZFC axioms), in particular for problems on the continuum. Consequently, the theory of iterated forcing is developed. The … This work deals with set-theoretic independence results (independence from the usual set-theoretic ZFC axioms), in particular for problems on the continuum. Consequently, the theory of iterated forcing is developed. The author gives a complete presentation of the theory of proper forcing and its relatives, starting from the beginning and avoiding the metamathematical considerations. In addition to particular consistency results, the author shows methods which can be used for such independence results. Many of these are presented in an axiomatic framework (a la Martin's axiom) for this reason. The main aim of this book is to enable a researcher interested in an independence result of the appropriate kind, to have much of the work done for him, thus allowing him to quote general results.

Stability, the f.c.p., and superstability; model theoretic properties of formulas in first order theory

1971-10-01

Saharon Shelah

The Karp complexity of unstable classes

2001-02-01

M. Laskowski , Saharon Shelah

View PDF Chat

Toward classifying unstable theories

1996-08-01

Saharon Shelah

Local order property in nonelementary classes

2000-08-01

Rami Grossberg , Olivier Lessmann

Finite diagrams stable in power

1970-09-01

Saharon Shelah

Six classes of theories

1976-05-01

H. Jerome Keisler

A theory T is said to κ-stable if, given a pair of models U ⊂ B of T with U of power κ, there are only κ types of elements … A theory T is said to κ-stable if, given a pair of models U ⊂ B of T with U of power κ, there are only κ types of elements of B over U (types are defined below). This notion was introduced by Morley (1965) who gave a powerful analysis of ω-stable theories. Shelah (1971) showed that there are only four possibilities for the set of κ in which a countable theory is stable. This partition of all theories into four classes (ω-stable, superstable, stable, and unstable theories) has proved to be of great value. However, most familiar examples of theories are unstable.

View PDF Chat

Dependent first order theories, continued

2009-09-01

Saharon Shelah

View PDF Chat

Notes on monadic logic. Part B: Complexity of linear orders in ZFC

1990-02-01

Saharon Shelah

Vapnik-Chervonenkis Classes of Definable Sets

1992-04-01

M. Laskowski

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.

Monadic logic and löwenheim numbers

1985-03-01

Saharon Shelah

More on monadic logic. part C: Monadically interpreting in stable unsuperstable ℱ and the monadic theory of $$^\omega \lambda $$

1990-10-01

Saharon Shelah

Categoricity in power

1965-01-01

Michael Morley

Introduction. A theory, 1, (formalized in the first order predicate calculus) is categorical in power K if it has exactly one type of models of power K. This notion was … Introduction. A theory, 1, (formalized in the first order predicate calculus) is categorical in power K if it has exactly one type of models of power K. This notion was introduced by Los [ 9] and Vaught [ 16] in 1954. At that time they pointed out that a theory (e.g., the theory of dense linearly ordered sets without end points) may be categorical in power N0 and fail to be categorical in any higher power. Conversely, a theory may be categorical in every uncountable power and fail to be categorical in power N0 (e.g., the theory of algebraically closed fields of characteristic 0). Los' then raised the following question. Is a theory categorical in one uncountable power necessarily categorical in every uncountable power? The principal result of this paper is an affirmative answer to that question. We actually prove a stronger result, namely: If a theory is categorical in some uncountable power then every uncountable model of that theory is saturated. (Terminology used in the Introduction will be defined in the body of the paper; roughly speaking, a model is saturated, or universalhomogeneous, if it contains an element of every possible elementary type relative to its subsystems of strictly smaller power.) It is known(2) that a theory can have (up to isomorphism) at most one saturated model in each power. It is interesting to note that our results depend essentially on an analogue of the usual analysis of topological spaces in terms of their derived spaces and the Cantor-Bendixson theorem. The paper is divided into five sections. In ?1 terminology and some meta-mathematical results are summarized. In particular, for each theory, 1, there is described a theory, *, which has essentially the same models as z but is neater to work with. In ?2 is defined a topological space, S(A), corresponding to each subsystem, A, of a model of a theory, 1; the points of S(A) being the isomorphism types of elements with respect to A. With each monomorphism (= isomorphic imbedding), f: A -+ B, is associated a dual continuous map, f*: S(B) -+ S(A). Then there is defined for each S(A) a decreasing sequence ISa(A) I of subspaces which is analogous to (but different from)

View PDF Chat

On properties of theories which preclude the existence of universal models

2005-07-12

Mirna Džamonja , Saharon Shelah

View PDF Chat

Subsets of superstable structures are weakly benign

2005-03-01

B. S. Baizhanov , John T. Baldwin , Saharon Shelah

Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the … Baizhanov and Baldwin [1] introduce the notions of benign and weakly benign sets to investigate the preservation of stability by naming arbitrary subsets of a stable structure. They connect the notion with work of Baldwin, Benedikt, Bouscaren, Casanovas, Poizat, and Ziegler. Stimulated by [1], we investigate here the existence of benign or weakly benign sets. Definition 0.1. (1) The set A is benign in M if for every α, β ∊ M if p = tp(α/ A ) = tp(β/ A ) then tp * (α/ A ) = tp * (β/ A ) where the *-type is the type in the language L* with a new predicate P denoting A . (2) The set A is weakly benign in M if for every α,β ∊ M if p = stp(α/ A ) = stp(β/ A ) then tp * (α/ A ) = tp * (β/A) where the *-type is the type in language with a new predicate P denoting A . Conjecture 0.2 (too optimistic). If M is a model of stable theory T and A ⊆ M then A is benign . Shelah observed, after learning of the Baizhanov-Baldwin reductions of the problem to equivalence relations, the following counterexample. Lemma 0.3. There is an ω-stable rank 2 theory T with ndop which has a model M and set A such that A is not benign in M .

View PDF Chat

Karp complexity and classes with the independence property

2002-10-08

M. Laskowski , Saharon Shelah

View PDF Chat