Vapnik–Chervonenkis Density in Some Theories without the Independence Property, II

Authors

Matthias Aschenbrenner, Alf Dolich, Deirdre Haskell, Dugald Macpherson, Sergei Starchenko

Type: Article

Publication Date: 2013-01-01

Citations: 32

DOI: https://doi.org/10.1215/00294527-2143862

View Ask PDF

Abstract

We study the Vapnik–Chervonenkis (VC) density of definable families in certain stable first-order theories. In particular, we obtain uniform bounds on the VC density of definable families in finite U-rank theories without the finite cover property, and we characterize those abelian groups for which there exist uniform bounds on the VC density of definable families.

Locations

arXiv (Cornell University)
View PDF
Project Euclid (Cornell University)
View PDF
DataCite API
View
Notre Dame Journal of Formal Logic
View

Ask a Question About This Paper

Summary

Similar Works

Definable families of finite Vapnik Chervonenkis dimension

2008-04-25

Hunter Johnson

Vapnik-Chervonenkis density in some theories without the independence property, I

2011-01-01

M. Aschenbrenner , A. Dolich , Deirdre Haskell +2 more

Chat View PDF

Vapnik-Chervonenkis density in some theories without the independence property, I

2015-12-22

Matthias Aschenbrenner , Alf Dolich , Deirdre Haskell +2 more

We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, … We recast the problem of calculating Vapnik-Chervonenkis (VC) density into one of counting types, and thereby calculate bounds (often optimal) on the VC density for some weakly o-minimal, weakly quasi-o-minimal, and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P"> <mml:semantics> <mml:mi>P</mml:mi> <mml:annotation encoding="application/x-tex">P</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-minimal theories.

Chat View PDF

Vapnik–Chervonenkis Density on Indiscernible Sequences, Stability, and the Maximum Property

2015-01-01

Hunter Johnson

This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way … This paper presents some finite combinatorics of set systems with applications to model theory, particularly the study of dependent theories. There are two main results. First, we give a way of producing lower bounds on VCind-density and use it to compute the exact VCind-density of polynomial inequalities and a variety of geometric set families. The main technical tool used is the notion of a maximum set system, which we juxtapose to indiscernibles. In the second part of the paper we give a maximum set system analogue to Shelah’s characterization of stability using indiscernible sequences.

Chat View PDF

On Fraïssé’s Theorem for Uncountable Classes of Finitely Generated Structures

2018-01-01

K. Zh. Kudaîbergenov

Independence in 𝜔-stable classes

2009-07-24

John T. Baldwin

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.

Vaught’s Conjecture for Theories of Discretely Ordered Structures

2024-08-01

Predrag Tanović

A Survey of the Uncountable Spectra of Countable Theories

1997-01-01

Bradd Hart , M. Laskowski

Countable closed invariant sets

1988-01-01

Chris Preston

A generalized Borel-reducibility counterpart of Shelah’s main gap theorem

2017-02-02

Tapani Hyttinen , Vadim Kulikov , Miguel Moreno

Chat View PDF

VC density of definable families over valued fields

2018-04-17

Saugata Basu , Deepam Patel

We prove a tight bound on the number of realized $0/1$ patterns (or equivalently on the Vapnik-Chervonenkis codensity) of definable families in models of the theory of algebraically closed valued … We prove a tight bound on the number of realized $0/1$ patterns (or equivalently on the Vapnik-Chervonenkis codensity) of definable families in models of the theory of algebraically closed valued fields with a non-archimedean valuation. Our result improves the best known result in this direction proved by Aschenbrenner, Dolich, Haskell, Macpherson and Starchenko, who proved a weaker bound in the restricted case where the characteristics of the field $K$ and its residue field are both assumed to be $0$. The bound obtained here is optimal and without any restriction on the characteristics. We obtain the aforementioned bound as a consequence of another result on bounding the Betti numbers of semi-algebraic subsets of certain Berkovich analytic spaces, mirroring similar results known already in the case of o-minimal structures and for real closed, as well as, algebraically closed fields. The latter result is the first result in this direction and is possibly of independent interest. Its proof relies heavily on recent results of Hrushovski and Loeser on the topology of semi-algebraic subsets of Berkovich analytic spaces.

Chat View PDF

VC density of definable families over valued fields

2018-01-01

Saugata Basu , Deepam Patel

Chat View PDF

Cohomological VC-density: Bounds and Applications

2024-11-14

Saugata Basu , Deepam Patel

The concept of Vapnik-Chervonenkis (VC) density is pivotal across various mathematical fields, including model theory, discrete geometry, and probability theory. In this paper, we introduce a topological generalization of VC-density. … The concept of Vapnik-Chervonenkis (VC) density is pivotal across various mathematical fields, including model theory, discrete geometry, and probability theory. In this paper, we introduce a topological generalization of VC-density. Let $Y$ be a topological space and $\mathcal{X},\mathcal{Z}^{(0)},\ldots,\mathcal{Z}^{(q-1)}$ be families of subspaces of $Y$. We define a two parameter family of numbers, $\mathrm{vcd}^{p,q}_{\mathcal{X},\overline{\mathcal{Z}}}$, which we refer to as the degree $p$, order $q$, VC-density of the pair \[ (\mathcal{X},\overline{\mathcal{Z}} = (\mathcal{Z}^{(0)},\ldots,\mathcal{Z}^{(q-1)}). \] The classical notion of VC-density within this topological framework can be recovered by setting $p=0, q=1$. For $p=0, q > 0$, we recover Shelah's notion of higher-order VC-density for $q$-dependent families. Our definition introduces a new notion when $p>0$. Our main result establishes that that in any model of these theories \[ \mathrm{vcd}^{p,q}_{\mathcal{X},\overline{\mathcal{Z}}} \leq (p+q) \dim X. \] This result generalizes known VC-density bounds in these structures, extending them in multiple ways, as well as providing a uniform proof paradigm applicable to all of them. We give examples to show that our bounds are optimal. We present combinatorial applications of our higher-degree VC-density bounds, deriving topological analogs of well-known results such as the existence of $\varepsilon$-nets and the fractional Helly theorem. We show that with certain restrictions, these results extend to our higher-degree topological setting.

Chat View PDF

Vaught and Morley Conjectures for ω-Stable Countable Theories

1988-01-01

John T. Baldwin

On countably saturated linear orders and certain class of countably saturated graphs

2019-06-30

Ziemowit Kostana

The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique … The idea of this paper is to explore the existence of canonical countably saturated models for different classes of structures. It is well-known that, under CH, there exists a unique countably saturated linear order of cardinality $\mathfrak{c}$. We provide some examples of pairwise non-isomorphic countably saturated linear orders of cardinality $\mathfrak{c}$, under different set-theoretic assumptions. We give a new proof of the old theorem of Harzheim, that the class of countably saturated linear orders has a uniquely determined one-element basis. From our proof it follows that this minimal linear order is a Fraisse limit of certain Fraisse class. In particular, it is homogeneous with respect to countable subsets. Next, we prove the existence and uniqueness of the uncountable version of the random graph. This graph is isomorphic to $(H(\omega_1),\in \cup \ni)$, where $H(\omega_1)$ is the set of hereditarily countable sets, and two sets are connected if one of them is an element of the other. In the last section, an example of a prime countably saturated Boolean algebra is presented.

Independence results for uncountable superstable theories

1989-02-01

Ludomir Newelski

Introduction to countable equivalence relations

2008-09-10

Vladimir Kanovei

Definable $(ω, 2)$-theorem for families with VC-codensity less than $2$

2022-01-01

Pablo Andújar Guerrero

Let $\mathcal{S}$ be a family of sets with VC-codensity less than $2$. We prove that, if $\mathcal{S}$ has the $(\omega, 2)$-property (for any infinitely many sets in $\mathcal{S}$, at least … Let $\mathcal{S}$ be a family of sets with VC-codensity less than $2$. We prove that, if $\mathcal{S}$ has the $(\omega, 2)$-property (for any infinitely many sets in $\mathcal{S}$, at least $2$ among them intersect), then $\mathcal{S}$ can be partitioned into finitely many subfamilies, each with the finite intersection property. If $\mathcal{S}$ is definable in some first-order structure, then these subfamilies can be chosen definable too. This is a strengthening of the case $q=2$ of the definable $(p,q)$- conjecture in model theory and of the Alon-Kleitman-Matou\v{s}ek $(p,q)$-theorem in combinatorics.

Chat View PDF

A Borel-reducibility Counterpart of Shelah's Main Gap Theorem

2016-01-01

Tapani Hyttinen , Vadim Kulikov , Miguel Moreno

We study the Borel-reducibility of isomorphism relations of complete first order theories and show the consistency of the following: For all such theories T and T', if T is classifiable … We study the Borel-reducibility of isomorphism relations of complete first order theories and show the consistency of the following: For all such theories T and T', if T is classifiable and T' is not, then the isomorphism of models of T' is strictly above the isomorphism of models of T with respect to Borel-reducibility. In fact, we can also ensure that a range of equivalence relations modulo various non-stationary ideals are strictly between those isomorphism relations. The isomorphism relations are considered on models of some fixed uncountable cardinality obeying certain restrictions.

Chat View PDF

Cited by (32)

Vapnik-Chervonenkis density in some theories without the independence property, I

2015-12-22

Matthias Aschenbrenner , Alf Dolich , Deirdre Haskell +2 more

Chat View PDF

A NEW DP-MINIMAL EXPANSION OF THE INTEGERS

2019-03-04

Eran Alouf , Christian d’Elbée

Abstract We consider the structure $({\Bbb Z}, + ,0,|_{p_1 } , \ldots ,|_{p_n } )$ , where $x|_p y$ means $v_p \left( x \right) \leqslant v_p \left( y \right)$ and … Abstract We consider the structure $({\Bbb Z}, + ,0,|_{p_1 } , \ldots ,|_{p_n } )$ , where $x|_p y$ means $v_p \left( x \right) \leqslant v_p \left( y \right)$ and v p is the p -adic valuation. We prove that this structure has quantifier elimination in a natural expansion of the language of abelian groups, and that it has dp-rank n . In addition, we prove that a first order structure with universe ${\Bbb Z}$ which is an expansion of $({\Bbb Z}, + ,0)$ and a reduct of $({\Bbb Z}, + ,0,|_p )$ must be interdefinable with one of them. We also give an alternative proof for Conant’s analogous result about $({\Bbb Z}, + ,0, < )$ .

Chat View PDF

A definable (p,q)-theorem for NIP theories

2023-11-17

Itay Kaplan

Chat View PDF

VC-density for trees

2018-11-30

A. G. Bobkov

On expansions of (Z,+,0)

2020-03-25

Quentin Lambotte , Françoise Point

Chat View PDF

Unavoidable subprojections in union-closed set systems of infinite breadth

2021-02-21

Yemon Choi , Mahya Ghandehari , Hung Le Pham

Chat View PDF

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.

Cutting lemma and Zarankiewicz’s problem in distal structures

2020-03-16

Artem Chernikov , David Galvin , Sergei Starchenko

Chat View PDF

THICKET DENSITY

2021-02-15

Siddharth Bhaskar

Abstract We define a new type of “shatter function” for set systems that satisfies a Sauer–Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah’s two-rank instead of VC … Abstract We define a new type of “shatter function” for set systems that satisfies a Sauer–Shelah type dichotomy, but whose polynomial-growth case is governed by Shelah’s two-rank instead of VC dimension. We identify the least exponent bounding the rate of growth of the shatter function, the quantity analogous to VC density, with Shelah’s $\omega $ -rank.

Chat View PDF

On VC-minimal theories and variants

2013-05-27

Vincent Guingona , M. Laskowski

Chat View PDF

Strong ordered Abelian groups and dp-rank

2017-01-01

Rafel Farré

We provide an algebraic characterization of strong ordered Abelian groups: An ordered Abelian group is strong iff it has bounded regular rank and almost finite dimension. Moreover, we show that … We provide an algebraic characterization of strong ordered Abelian groups: An ordered Abelian group is strong iff it has bounded regular rank and almost finite dimension. Moreover, we show that any strong ordered Abelian group has finite Dp-rank. We also provide a formula that computes the exact valued of the Dp-rank of any ordered Abelian group. In particular characterizing those ordered Abelian groups with Dp-rank equal to $n$. We also show the Dp-rank coincides with the Vapnik-Chervonenkis density.

Chat View PDF

Vapnik–Chervonenkis Density on Indiscernible Sequences, Stability, and the Maximum Property

2015-01-01

Hunter Johnson

Chat View PDF

THERE ARE NO INTERMEDIATE STRUCTURES BETWEEN THE GROUP OF INTEGERS AND PRESBURGER ARITHMETIC

2018-03-01

Gabriel Conant

Abstract We show that if a first-order structure ${\cal M}$ , with universe ℤ, is an expansion of (ℤ,+,0) and a reduct of (ℤ,+,<,0), then ${\cal M}$ must be interdefinable … Abstract We show that if a first-order structure ${\cal M}$ , with universe ℤ, is an expansion of (ℤ,+,0) and a reduct of (ℤ,+,<,0), then ${\cal M}$ must be interdefinable with (ℤ ,+,0) or (ℤ ,+,<,0).

Chat View PDF

On VC-minimal fields and dp-smallness

2014-02-24

Vincent Guingona

Chat View PDF

dp-Rank and Forbidden Configurations

2012-12-14

Hunter Johnson

class in n parameters. class in n parameters.

Chat View PDF

Neighbourhood complexity of graphs of bounded twin-width

2023-08-01

Édouard Bonnet , Florent Foucaud , Tuomo Lehtilä +1 more

We give essentially tight bounds for, $\nu(d,k)$, the maximum number of distinct neighbourhoods on a set $X$ of $k$ vertices in a graph with twin-width at most~$d$. Using the celebrated … We give essentially tight bounds for, $\nu(d,k)$, the maximum number of distinct neighbourhoods on a set $X$ of $k$ vertices in a graph with twin-width at most~$d$. Using the celebrated Marcus-Tardos theorem, two independent works [Bonnet et al., Algorithmica '22; Przybyszewski '22] have shown the upper bound $\nu(d,k) \leqslant \exp(\exp(O(d)))k$, with a double-exponential dependence in the twin-width. The work of [Gajarsky et al., ICALP '22], using the framework of local types, implies the existence of a single-exponential bound (without explicitly stating such a bound). We give such an explicit bound, and prove that it is essentially tight. Indeed, we give a short self-contained proof that for every $d$ and $k$ $$\nu(d,k) \leqslant (d+2)2^{d+1}k = 2^{d+\log d+\Theta(1)}k,$$ and build a bipartite graph implying $\nu(d,k) \geqslant 2^{d+\log d+\Theta(1)}k$, in the regime when $k$ is large enough compared to~$d$.

Chat View PDF

Stability of characters and filters for weighted semilattices

2020-12-24

Yemon Choi , Mahya Ghandehari , Hung Le Pham

We continue the study of the AMNM property for weighted semilattices that was initiated in [Y. Choi, J. Austral. Math. Soc. 95 (2013), no. 1, 36-67; arXiv 1203.6691]. We reformulate … We continue the study of the AMNM property for weighted semilattices that was initiated in [Y. Choi, J. Austral. Math. Soc. 95 (2013), no. 1, 36-67; arXiv 1203.6691]. We reformulate this in terms of stability of filters with respect to a given weight function, and then provide a combinatorial condition which is necessary and sufficient for this "filter stability" property to hold. Examples are given to show that this new condition allows for easier and unified proofs of some results in [Choi, ibid.], and furthermore allows us to verify the AMNM property in situations not covered by the results of that paper. As a final application, we show that for a large class of semilattices, arising naturally as union-closed set systems, one can always construct weights for which the AMNM property fails.

Chat View PDF

Dp-Minimality: Basic Facts and Examples

2011-07-01

Alfred Dolich , John Goodrick , David Lippel

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.

Chat View PDF

Additivity of the dp-rank

2011-09-07

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 can not be reduced to the study of … 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 can not be reduced to the study of its dp-minimal types, and discuss the possible relations between dp-rank and VC-density.

Chat View PDF

Definability of types and VC density in differential topological fields

2017-12-26

Françoise Point

Multiplicative structure in stable expansions of the group of integers

2018-01-01

Gabriel Conant

We define two families of expansions of $(\mathbb{Z},+)$ by unary predicates, and prove that their theories are superstable of $U$-rank $\omega $. The first family consists of expansions $(\mathbb{Z},+,A)$, where … We define two families of expansions of $(\mathbb{Z},+)$ by unary predicates, and prove that their theories are superstable of $U$-rank $\omega $. The first family consists of expansions $(\mathbb{Z},+,A)$, where $A$ is an infinite subset of a finitely generated multiplicative submonoid of $\mathbb{Z}^{+}$. Using this result, we also prove stability for the expansion of $(\mathbb{Z},+)$ by all unary predicates of the form $\{q^{n}:n\in \mathbb{N}\}$ for some $q\in \mathbb{N}_{\geq 2}$. The second family consists of sets $A\subseteq \mathbb{N}$ which grow asymptotically close to a $\mathbb{Q}$-linearly independent increasing sequence $(\lambda_{n})_{n=0}^{\infty }\subseteq\mathbb{R}^{+}$ such that $\{\frac{\lambda_{n}}{\lambda_{m}}:m\leq n\}$ is closed and discrete.

Chat View PDF

Metric Entropy estimation using o-minimality Theory

2015-01-01

Alf Onshuus , Adolfo J. Quiróz

It is shown how tools from the area of Model Theory, specifically from the Theory of o-minimality, can be used to prove that a class of functions is VC-subgraph (in … It is shown how tools from the area of Model Theory, specifically from the Theory of o-minimality, can be used to prove that a class of functions is VC-subgraph (in the sense of Dudley, 1987), and therefore satisfies a uniform polynomial metric entropy bound. We give examples where the use of these methods significantly improves the existing metric entropy bounds. The methods proposed here can be applied to finite dimensional parametric families of functions without the need for the parameters to live in a compact set, as is sometimes required in theorems that produce similar entropy bounds (for instance Theorem 19.7 of van der Vaart, 1998).

Chat View PDF

On VC-minimal theories and variants

2011-10-19

Vincent Guingona , M. Laskowski

In this paper, we study VC-minimal theories and explore related concepts. We first define the notion of convex orderablility and show that this lies strictly between VC-minimality and dp-minimality. Next, … In this paper, we study VC-minimal theories and explore related concepts. We first define the notion of convex orderablility and show that this lies strictly between VC-minimality and dp-minimality. Next, we define the notion of weak VC-minimality, show it lies strictly between VC-minimality and dependence, and show that all unstable weakly VC-minimal theories interpret an infinite linear order. Finally, we define the notion full VC-minimality, show that this lies strictly between weak o-minimality and VC-minimality, and show that theories that are fully VC-minimal have low VC-density.

Chat View PDF

DP-MINIMAL VALUED FIELDS

2017-03-01

Franziska Jahnke , Pierre Simon , Erik Walsberg

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.

Chat View PDF

Dp-minimal valued fields

2015-07-14

Franziska Jahnke , Pierre Simon , Erik Walsberg

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.

Chat View PDF

THE DP-RANK OF ABELIAN GROUPS

2019-02-01

Yatir Halevi , Daniel Palacín

Abstract An equation to compute the dp-rank of any abelian group is given. It is also shown that its dp-rank, or more generally that of any one-based group, agrees with … Abstract An equation to compute the dp-rank of any abelian group is given. It is also shown that its dp-rank, or more generally that of any one-based group, agrees with its Vapnik–Chervonenkis density. Furthermore, strong abelian groups are characterised to be precisely those abelian groups A such that there are only finitely many primes p such that the group A / pA is infinite and for every prime p , there are only finitely many natural numbers n such that $\left( {p^n A} \right)[p]/\left( {p^{n + 1} A} \right)[p]$ is infinite. Finally, it is shown that an infinite stable field of finite dp-rank is algebraically closed.

Chat View PDF

On n-Dependence

2019-05-01

Artem Chernikov , Daniel Palacín , Kota Takeuchi

In this article, we develop and clarify some of the basic combinatorial properties of the new notion of n-dependence (for 1≤n<ω) recently introduced by Shelah. In the same way as … In this article, we develop and clarify some of the basic combinatorial properties of the new notion of n-dependence (for 1≤n<ω) recently introduced by Shelah. In the same way as dependence of a theory means its inability to encode a bipartite random graph with a definable edge relation, n-dependence corresponds to the inability to encode a random (n+1)-partite (n+1)-hypergraph with a definable edge relation. We characterize n-dependence by counting φ-types over finite sets (generalizing the Sauer–Shelah lemma, answering a question of Shelah), and in terms of the collapse of random ordered (n+1)-hypergraph indiscernibles down to order-indiscernibles (which implies that the failure of n-dependence is always witnessed by a formula in a single free variable).

Chat View PDF

Externally definable sets and dependent pairs II

2015-02-20

Artem Chernikov , Pierre Simon

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.

Chat View PDF

On VC-minimal fields and dp-smallness

2013-07-30

Vincent Guingona

In this paper, we show that VC-minimal ordered fields are real closed. We introduce a notion, strictly between convexly orderable and dp-minimal, that we call dp-small, and show that this … In this paper, we show that VC-minimal ordered fields are real closed. We introduce a notion, strictly between convexly orderable and dp-minimal, that we call dp-small, and show that this is enough to characterize many algebraic theories. For example, dp-small ordered groups are abelian divisible and dp-small ordered fields are real closed.

Chat View PDF

Regularity lemma for distal structures

2015-07-06

Artem Chernikov , Sergei Starchenko

It is known that families of graphs with a semialgebraic edge relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and that they can be decomposed into … It is known that families of graphs with a semialgebraic edge relation of bounded complexity satisfy much stronger regularity properties than arbitrary graphs, and that they can be decomposed into very homogeneous semialgebraic pieces up to a small error (e.g., see [33, 2, 16, 18]). We show that similar results can be obtained for families of graphs with the edge relation uniformly definable in a structure satisfying a certain model theoretic property called distality, with respect to a large class of generically stable measures. Moreover, distality characterizes these strong regularity properties. This applies in particular to graphs definable in arbitrary $o$-minimal structures and in $p$-adics.

Chat View PDF

Vapnik–Chervonenkis dimension and density on Johnson and Hamming graphs

2021-12-02

Isolde Adler , Bjarki Geir Benediktsson , Dugald Macpherson

Chat View PDF

Computability of validity and satisfiability in probability logics over finite and countable models

2015-10-02

Greg Yang

The -logic (which is called E-logic in this paper) of Terwijn is a variant of first-order logic (FOL) with the same syntax in which the models are equipped with probability … The -logic (which is called E-logic in this paper) of Terwijn is a variant of first-order logic (FOL) with the same syntax in which the models are equipped with probability measures and the quantifier is interpreted as ‘there exists a set A of a measure such that for each , ...’. Previously, Kuyper and Terwijn proved that the general satisfiability and validity problems for this logic are, i) for rational , respectively -complete and -hard, and ii) for , respectively decidable and -complete. The adjective ‘general’ here means ‘uniformly over all languages’. We extend these results in the scenario of finite models. In particular, we show that the problems of satisfiability and validity with respect to finite models in E-logic are, i) for rational , respectively -complete and -complete, and ii) for , respectively decidable and -complete. Although partial results toward the countable case are also achieved, the computability of E-logic over countable models still remains largely unsolved. In addition, most of the results here and of Kuyper and Terwijn do not apply to individual languages with a finite number of unary predicates. Reducing this requirement continues to be a major point of research. On the positive side, we derive the decidability of the corresponding problems for monadic relational languages – equality- and function-free languages with finitely-many unary and arbitrarily-many nullary predicates. This result holds for all three of the unrestricted, countable, and finite-model cases. Applications in computational learning theory (CLT), weighted graphs, and artificial neural networks (ANNs) are discussed in the context of these decidability and undecidability results.

Chat View PDF

References (40)

The model-theoretic content of Lang’s conjecture

2009-03-13

Anand Pillay

Types dans les corps valués

1996-01-01

Luc Bélair , Michel Bousquet

RESUME. L’analyse de Delon des types dans les corps values devient particulierement transparente dans le langage des corps values auquel on ajoute une ≪ application coeﬃcient ≫. On obtient ainsi … RESUME. L’analyse de Delon des types dans les corps values devient particulierement transparente dans le langage des corps values auquel on ajoute une ≪ application coeﬃcient ≫. On obtient ainsi une preuve du transfert a la Ax-Kochen-Ershov de la propriete d’independance en egale caracteristique zero. / ABSTRACT. Delon’s analysis of types in valued

Weakly Normal Groups

1987-01-01

U. Hrushovski , Anthony L. Pillay

Regularity Partitions and The Topology of Graphons

2010-01-01

László Lovász , Balázs Szegedy

Chat View PDF

𝛼_{𝑇} is finite for ℵ₁-categorical 𝑇

1973-01-01

John T. Baldwin

Let <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> be a complete countable <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi … Let <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> be a complete countable <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical theory. Definition. If <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a model of <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> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="1"> <mml:semantics> <mml:mn>1</mml:mn> <mml:annotation encoding="application/x-tex">1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-ary formula in <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper L left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>L</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">L(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> then <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A"> <mml:semantics> <mml:mi>A</mml:mi> <mml:annotation encoding="application/x-tex">A</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has rank 0 if <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">A(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is finite. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">A(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has rank <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> degree <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m"> <mml:semantics> <mml:mi>m</mml:mi> <mml:annotation encoding="application/x-tex">m</mml:annotation> </mml:semantics> </mml:math> </inline-formula> iff for every set of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="m plus 1"> <mml:semantics> <mml:mrow> <mml:mi>m</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">m + 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula> formulas <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B 1 comma midline-horizontal-ellipsis comma upper B Subscript m plus 1 Baseline element-of upper S 1 left-parenthesis upper L left-parenthesis script upper A right-parenthesis right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>B</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo>,</mml:mo> <mml:mo>⋯</mml:mo> <mml:mo>,</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>B</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi>m</mml:mi> <mml:mo>+</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:msub> </mml:mrow> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>L</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{B_1}, \cdots ,{B_{m + 1}} \in {S_1}(L(\mathcal {A}))</mml:annotation> </mml:semantics> </mml:math> </inline-formula> which partition <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">A(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> some <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper B Subscript i Baseline left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>B</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{B_i}(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has rank <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="less-than-or-slanted-equals n minus 1"> <mml:semantics> <mml:mrow> <mml:mo>⩽</mml:mo> <mml:mi>n</mml:mi> <mml:mo>−</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">\leqslant n - 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. Theorem. <italic>If <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> is <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical then for every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="script upper A"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathcal {A}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> a model of <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> and every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper A element-of upper S 1 left-parenthesis upper L left-parenthesis script upper A right-parenthesis right-parenthesis comma upper A left-parenthesis script upper A right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mi>A</mml:mi> <mml:mo>∈</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>S</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>L</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mo>,</mml:mo> <mml:mi>A</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi class="MJX-tex-caligraphic" mathvariant="script">A</mml:mi> </mml:mrow> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">A \in {S_1}(L(\mathcal {A})),A(\mathcal {A})</mml:annotation> </mml:semantics> </mml:math> </inline-formula> has finite rank</italic>. Corollary. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript upper T"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>T</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\alpha _T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <italic>is finite. The methods derive from Lemmas 9 and 11 in “On strongly minimal sets” by Baldwin and Lachlan. <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="alpha Subscript upper T"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>α</mml:mi> <mml:mi>T</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\alpha _T}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is defined in “Categoricity in power” by Michael Morley</italic>.

Chat View PDF

On $ω_1$-categorical theories of abelian groups

1971-01-01

Angus Macintyre

Chat View PDF

Unit distances in the Euclidean plane

1984-01-01

Joel Spencer , Endre Szemerédi , WT Trotter

Geometric Set Systems

1998-01-01

Jiřı́ Matoušek

A course on empirical processes

1984-01-01

R. M. Dudley

ℵ0-Categorical, ℵ0-stable structures

1985-03-01

Gregory Cherlin , Louise Harrington , A. H. Lachlan

Model theory of modules over a serial ring

1995-03-01

Paul C. Eklof , Ivo Herzog

Generically stable and smooth measures in NIP theories

2012-12-13

Ehud Hrushovski , Anand Pillay , Pierre Simon

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.

Chat View PDF

The theory of ordered abelian groups does not have the independence property

1984-01-01

Yuri Gurevich , Peter H. Schmitt

We prove that no complete theory of ordered abelian groups has the independence property, thus answering a question by B. Poizat. The main tool is a result contained in the … We prove that no complete theory of ordered abelian groups has the independence property, thus answering a question by B. Poizat. The main tool is a result contained in the doctoral dissertation of Yuri Gurevich and also in P. H. Schmitt’s <italic>Elementary properties of ordered abelian groups</italic>, which basically transforms statements on ordered abelian groups into statements on coloured chains. We also prove that every <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>-type in the theory of coloured chains has at most <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="2 Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{2^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> coheirs, thereby strengthening a result by B. Poizat.

Chat View PDF

On the density of families of sets

1972-07-01

N. Sauer

Essentially periodic ordered groups

2000-11-01

Françoise Point , Frank Olaf Wagner

Vapnik-Chervonenkis density in some theories without the independence property, I

2015-12-22

Matthias Aschenbrenner , Alf Dolich , Deirdre Haskell +2 more

Chat View PDF

The homeomorphic embedding of Kn in the m-cube

1976-10-01

Jehuda Hartman

Partially ordered sets and the independence property

1989-06-01

James H. Schmerl

Abstract No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning … Abstract No theory of a partially ordered set of finite width has the independence property, generalizing Poizat's corresponding result for linearly ordered sets. In fact, a question of Poizat concerning linearly ordered sets is answered by showing, moreover, that no theory of a partially ordered set of finite width has the multi-order property. It then follows that a distributive lattice is not finite-dimensional iff its theory has the independence property iff its theory has the multi-order property.

Magidor-Malitz quantifiers in modules

1984-03-01

Andreas Baudisch

Abstract We prove the elimination of Magidor-Malitz quantifiers for R -modules relative to certain -core sentences and positive primitive formulas. For complete extensions of the elementary theory of R-modules it … Abstract We prove the elimination of Magidor-Malitz quantifiers for R -modules relative to certain -core sentences and positive primitive formulas. For complete extensions of the elementary theory of R-modules it follows that all Ramsey quantifiers (ℵ 0 -interpretation) are eliminable. By a result of Baldwin and Kueker [1] this implies that there is no R -module having the finite cover property.

Closed asymptotic couples

2000-03-01

Matthias Aschenbrenner , Lou van den Dries

Strongly dependent theories

2014-07-28

Saharon Shelah

Chat View PDF

Rings of finite representation type and modules of finite Morley rank

1984-06-01

Mike Prest

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

1971-10-01

Saharon Shelah

A combinatorial problem; stability and order for models and theories in infinitary languages

1972-04-01

Saharon Shelah

DEFINITION 1.3.P3(λ, μ, a) holds if |S| DEFINITION 1.3.P3(λ, μ, a) holds if |S|

Chat View PDF

Dp-Minimality: Basic Facts and Examples

2011-07-01

Alfred Dolich , John Goodrick , David Lippel

Chat View PDF

Les groupes 𝜔-stables de rang fini

1985-01-01

Daniel Lascar

We prove that a 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> which is <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 … We prove that a 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> which is <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>-stable of finite Morley rank is nonmultidimensional. If moreover it is connected and does not have any infinite normal abelian definable subgroup, then it is isomorphic to <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal upper Pi upper H Subscript i slash upper K"> <mml:semantics> <mml:mrow> <mml:mi mathvariant="normal">Π</mml:mi> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:mi>K</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\Pi {H_i}/K</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, where the <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper H Subscript i"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>H</mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{H_i}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> are <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="omega 1"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ω</mml:mi> <mml:mn>1</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\omega _1}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical groups and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper K"> <mml:semantics> <mml:mi>K</mml:mi> <mml:annotation encoding="application/x-tex">K</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is a finite group.

Chat View PDF

Quasi-o-minimal structures

2000-09-01

Oleg Belegradek , Ya’acov Peterzil , Frank Olaf Wagner

Abstract A structure ( M , <, …) is called quasi-o-minimal if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0-definable subsets … Abstract A structure ( M , <, …) is called quasi-o-minimal if in any structure elementarily equivalent to it the definable subsets are exactly the Boolean combinations of 0-definable subsets and intervals. We give a series of natural examples of quasi-o-minimal structures which are not o-minimal; one of them is the ordered group of integers. We develop a technique to investigate quasi-o-minimality and use it to study quasi-o-minimal ordered groups (possibly with extra structure). Main results: any quasi-o-minimal ordered group is abelian; any quasi-o-minimal ordered ring is a real closed field, or has zero multiplication; every quasi-o-minimal divisible ordered group is o-minimal; every quasi-o-minimal archimedian densely ordered group is divisible. We show that a counterpart of quasi-o-minimality in stability theory is the notion of theory of U -rank 1.

Linear Equations in Variables which Lie in a Multiplicative Group

2002-05-01

Jan‐Hendrik Evertse , Hans Peter Schlickewei , Winfried Schmidt

Let K be a field of characteristic 0 and let n be a natural number.Let Γ be a subgroup of the multiplicative group (K * ) n of finite rank … Let K be a field of characteristic 0 and let n be a natural number.Let Γ be a subgroup of the multiplicative group (K * ) n of finite rank r.Given a 1 , . . ., a n ∈ K * write A(a 1 , . . ., a n , Γ) for the number of solutionsWe derive an explicit upper bound for A(a 1 , . . ., a n , Γ) which depends only on the dimension n and on the rank r.

Chat View PDF

A version of o-minimality for the p-adics

1997-12-01

Deirdre Haskell , Dugald Macpherson

In this paper we formulate a notion similar to o -minimality but appropriate for the p -adics. The paper is in a sense a sequel to [11] and [5]. In … In this paper we formulate a notion similar to o -minimality but appropriate for the p -adics. The paper is in a sense a sequel to [11] and [5]. In [11] a notion of minimality was formulated, as follows. Suppose that L, L + are first-order languages and + is an L + -structure whose reduct to L is . Then + is said to be -minimal if, for every N + elementarily equivalent to + , every parameterdefinable subset of its domain N + is definable with parameters by a quantifier-free L -formula. Observe that if L has a single binary relation which in is interpreted by a total order on M , then we have just the notion of strong o-minimality , from [13]; and by a theorem from [6], strong o -minimality is equivalent to o -minimality. If L has no relations, functions, or constants (other than equality) then the notion is just strong minimality . In [11], -minimality is investigated for a number of structures . In particular, the C-relation of [1] was considered, in place of the total order in the definition of strong o -minimality. The C -relation is essentially the ternary relation which naturally holds on the maximal chains of a sufficiently nice tree; see [1], [11] or [5] for more detail, and for axioms. Much of the motivation came from the observation that a C -relation on a field F which is preserved by the affine group AGL(1, F ) (consisting of permutations ( a,b ) : x ↦ ax + b , where a ∈ F \ {0} and b ∈ F ) is the same as a non-trivial valuation: to get a C -relation from a valuation ν, put C ( x;y,z ) if and only if ν( y − x ) < ν( y − z ).

Unavoidable Traces Of Set Systems

2005-12-01

József Balogh , Béla Bollobás

One-Dimensional p -Adic Subanalytic Sets

1999-02-01

Lou van den Dries , Deirdre Haskell , Dugald Macpherson

In this paper we extend two theorems from [2] on p-adic subanalytic sets, where p is a fixed prime number, Qp is the field of p-adic numbers and Zp is … In this paper we extend two theorems from [2] on p-adic subanalytic sets, where p is a fixed prime number, Qp is the field of p-adic numbers and Zp is the ring of p-adic integers. One of these theorems [2, 3.32] says that each subanalytic subset of Zp is semialgebraic. This is extended here as follows.

Maximum number of edges joining vertices on a cube

2003-05-19

Khaled Abdel-Ghaffar

Vapnik-Chervonenkis Classes of Definable Sets

1992-04-01

M. Laskowski

On Goldie and dual Goldie dimensions

1984-03-01

Piotr Grzeszczuk , E. R. Puczyłowski

On Lascar rank and Morley rank of definable groups in differentially closed fields

2002-09-01

Anand Pillay , Wai Yan Pong

Abstract Morley rank and Lascar rank are equal on generic types of definable groups in differentially closed fields with finitely many commuting derivations. Abstract Morley rank and Lascar rank are equal on generic types of definable groups in differentially closed fields with finitely many commuting derivations.

Zero-one laws for sparse random graphs

1988-01-01

Saharon Shelah , Joel Spencer

For random graph theorists (see, e.g., Bollobas [1] for general reference) p any constant is not the only, not even the most interesting case. Rather, they consider p = p(n), … For random graph theorists (see, e.g., Bollobas [1] for general reference) p any constant is not the only, not even the most interesting case. Rather, they consider p = p(n), a function approaching zero. In their seminal paper, Erd6s and Renyi [5] showed that for many interesting A there is a function p(n), which they called a threshold function, so that if r(n) < p(n) then f(n, r(n), A) -+ 0 while if p(n) < r(n) then f(n, r(n), A) 1-+ . (Notation: p < r means lim p/r = 0. All limits are as n approaches infinity.) Let us say p = p(n) satisfies the Zero-One Law if for all A in GRA, limf(n, p, A) = 0 or 1. We shall partially characterize those p = p(n) which satisfy the Zero-One Law.

Chat View PDF

On dp-minimality, strong dependence and weight

2011-07-06

Alf Onshuus , Alexander Usvyatsov

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.

Stable theories with a new predicate

2001-09-01

Enrique Casanovas , Martin Ziegler

Let M be an L -structure and A be an infinite subset of M . Two structures can be defined from A : • The induced structure on A has … Let M be an L -structure and A be an infinite subset of M . Two structures can be defined from A : • The induced structure on A has a name R φ for every ∅-definable relation φ ( M ) ∩ A n on A . Its language is A with its L ind -structure will be denoted by A ind . • The pair ( M, A ) is an L(P) -structure, where P is a unary predicate for A and L(P) = L ∪{ P }. We call A small if there is a pair ( N, B ) elementarily equivalent to ( M, A ) and such that for every finite subset b of N every L –type over Bb is realized in N . A formula φ ( x, y ) has the finite cover property (f.c.p) in M if for all natural numbers k there is a set of φ –formulas which is k –consistent but not consistent in M. M has the f.c.p if some formula has the f.c.p in M . It is well known that unstable structures have the f.c.p. (see [6].) We will prove the following two theorems. Theorem A. Let A be a small subset of M. If M does not have the finite cover property then, for every λ ≥ ∣ L ∣, if both M and A ind are λ– stable then (M, A) is λ– stable . Corollary 1.1 (Poizat [5]). If M does not have the finite cover property and N ≺ M is a small elementary substructure, then (M, N) is stable . Corollary 1.2 (Zilber [7]). If U is the group of wots of unity in the field ℂ of complex numbers the pair (ℂ, U ) is ω – stable . Proof. (See [4].) As a strongly minimal set ℂ is ω–stable and does not have the f.c.p. By the subspace theorem of Schmidt [3] every algebraic set intersects U in a finite union of translates of subgroups definable in the group structure of U alone. Whence U ind is nothing more than a (divisible) abelian group, which is ω –stable.

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.

Chat View PDF

A partition calculus in set theory

1956-01-01

Péter L. Erdős , R. Rado

Introduction.Dedekind's pigeon-hole principle, also known as the box argument or the chest of drawers argument (Schubfachprinzip) can be described, rather vaguely, as follows.If sufficiently many objects are distributed over not … Introduction.Dedekind's pigeon-hole principle, also known as the box argument or the chest of drawers argument (Schubfachprinzip) can be described, rather vaguely, as follows.If sufficiently many objects are distributed over not too many classes, then at least one class contains many of these objects.In 1930 F. P. Ramsey [12] discovered a remarkable extension of this principle which, in its simplest form, can be stated as follows.Let S be the set of all positive integers and suppose that all unordered pairs of distinct elements of S are distributed over two classes.Then there exists an infinite subset A of S such that all pairs of elements of A belong to the same class.As is well known, Dedekind's principle is the central step in many investigations.Similarly, Ramsey's theorem has proved itself a useful and versatile tool in mathematical arguments of most diverse character.The object of the present paper is to investigate a number of analogues and extensions of Ramsey's theorem.We shall replace the sets S and A by sets of a more general kind and the unordered pairs, as is the case already in the theorem proved by Ramsey, by systems of any fixed number r of elements of S. Instead of an unordered set S we consider an ordered set of a given order type, and we stipulate that the set A is to be of a prescribed order type.Instead of two classes we admit any finite or infinite number of classes.Further extension will be explained in § §2, 8 and 9.The investigation centres round what we call partition relations connecting given cardinal numbers or order types and in each given case the problem arises of deciding whether a particular partition relation is true or false.It appears that a large number of seemingly unrelated arguments in set theory are, in fact, concerned with just such a problem.It might therefore be of interest to study such relations for their own sake and to build up a partition calculus which might serve as a new and unifying principle in set theory.In some cases we have been able to find best possible partition relations, in one sense or another.In other cases the methods available to the authors do not seem to lead anywhere near the ultimate Part of this paper was material from an address delivered by P. Erdös under the title Combinatorial problems in set theory before the New York meeting of the Society on October 24, 1953, by invitation of the Committee to Select Hour Speakers for Eastern Sectional Meetings; received by the editors May 17, 1955.1956] «-> (ft, •••)*; <*-» (*o, •••)*• THEOREM 16.If a-*(j8 0 , ft, • • • )ï +4 ; ftr-KYo, Ti, • • • )ï, then «-» (TO, TI, • • • , ft, ft, • * • )*+*•In this proposition the types a, ft, y v may be replaced by cardinals.In formulating the last theorem we use an obvious extension of the symbol (2).PROOF.We consider the case of types.Let 5 = a, [S] r = Zfr < *]*ox + £[0 < * < 1 + *]*,.Put Ko = ]C [X </]JSTox.Then, by hypothesis, there are A CS\ P<1 +k

Chat View PDF