Abstract We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with a particular emphasis on the …
Abstract We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with a particular emphasis on the set $D'$ comprised of differences between successive elements. In particular, if the burden of the structure is at most n , then the result of applying the operation $D \mapsto D'\ n$ times must be a finite set (Theorem 1.1). In the case when the structure is densely ordered and has burden $2$ , we show that any definable unary discrete set must be definable in some elementary extension of the structure $\langle \mathbb{R}; <, +, \mathbb{Z} \rangle $ (Theorem 1.3).
Abstract We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the …
Abstract We obtain some new results on the topology of unary definable sets in expansions of densely ordered Abelian groups of burden 2. In the special case in which the structure has dp‐rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle‐third set (Theorem 2.9). If it has burden 2 and both an infinite discrete set D and a dense‐codense set X are definable, then translates of X must witness the Independence Property (Theorem 2.26). In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense‐codense set are definable.
A visceral structure on M is given by a definable base for a uniform topology on its universe M in which all basic open sets are infinite and any infinite …
A visceral structure on M is given by a definable base for a uniform topology on its universe M in which all basic open sets are infinite and any infinite definable subset X⊆M has nonempty interior. Assuming only viscerality, we show that the definable sets in M satisfy some desirable topological tameness conditions. For example, any definable function f:M→M has a finite set of discontinuities; any definable function f:Mn→Mm is continuous on a nonnempty open set; and assuming definable finite choice, we obtain a cell decomposition result for definable sets. Under an additional topological assumption ("no space-filling functions"), we prove that the natural notion of topological dimension is invariant under definable bijections. These results generalize some of the theorems proved by Simon and Walsberg, who assumed dp-minimality in addition to viscerality. In the final section, we construct new examples of visceral structures.
We obtain some new results on the topology of unary definable sets in densely ordered Abelian groups of burden groups of burden 2. In the special case in which the …
We obtain some new results on the topology of unary definable sets in densely ordered Abelian groups of burden groups of burden 2. In the special case in which the structure has dp-rank 2, we show that the existence of an infinite definable discrete set precludes the definability of a set which is dense and codense in an interval, or of a set which is topologically like the Cantor middle-third set. If the structure has burden 2 and both an infinite discrete set D and a dense-codense set X are definable, then translates of X must witness the Independence Property. In the last section, an explicit example of an ordered Abelian group of burden 2 is given in which both an infinite discrete set and a dense-codense set are definable.
We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with particular emphasis on the set D' …
We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with particular emphasis on the set D' comprised of differences between successive elements. In particular, if the burden of the structure is at most n, then the result of applying the operation mapping D to D' n times must be a finite set (Theorem 2.13). In the case when the structure is densely ordered and has burden 2, we show that any definable unary discrete set must be definable in some elementary extension of the structure (R; <, +, Z) (Theorem 3.1).
Given a parametric lattice with a basis given by polynomials in $\Bbb{Z}[t]$, we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in $t$: that is, …
Given a parametric lattice with a basis given by polynomials in $\Bbb{Z}[t]$, we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in $t$: that is, they are given by formulas that are piecewise polynomial in $t$ (for sufficiently large $t$), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem and closest vector problem that are also eventually quasi-polynomial in $t$.
Let $f_1(n), \ldots, f_k(n)$ be polynomial functions of $n$. For fixed $n\in\mathbb{N}$, let $S_n\subseteq \mathbb{N}$ be the numerical semigroup generated by $f_1(n),\ldots,f_k(n)$. As $n$ varies, we show that many invariants …
Let $f_1(n), \ldots, f_k(n)$ be polynomial functions of $n$. For fixed $n\in\mathbb{N}$, let $S_n\subseteq \mathbb{N}$ be the numerical semigroup generated by $f_1(n),\ldots,f_k(n)$. As $n$ varies, we show that many invariants of $S_n$ are eventually quasi-polynomial in $n$, such as the Frobenius number, the type, the genus, and the size of the $\Delta$-set. The tool we use is expressibility in the logical system of parametric Presburger arithmetic. Generalizing to higher dimensional families of semigroups, we also examine affine semigroups $S_n\subseteq \mathbb{N}^m$ generated be vectors whose coordinates are polynomial functions of $n$, and we prove similar results; for example, the Betti numbers are eventually quasi-polynomial functions of $n$.
We show that parametric versions of the shortest vector problem (SVP) and closest vector problem (CVP), in which the lattice bases are given by polynomials in Z[t], have solutions which …
We show that parametric versions of the shortest vector problem (SVP) and closest vector problem (CVP), in which the lattice bases are given by polynomials in Z[t], have solutions which are eventually quasipolynomial in t: that is, there are formulas which are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period.
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, …
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem (SVP) and closest vector problem (CVP) that are also eventually quasi-polynomial in t.
Abstract We consider an expansion of Presburger arithmetic which allows multiplication by k parameters . A formula in this language defines a parametric set as varies in , and we …
Abstract We consider an expansion of Presburger arithmetic which allows multiplication by k parameters . A formula in this language defines a parametric set as varies in , and we examine the counting function as a function of t . For a single parameter, it is known that can be expressed as an eventual quasi‐polynomial (there is a period m such that, for sufficiently large t , the function is polynomial on each of the residue classes mod m ). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming ) we construct a parametric set such that is not even polynomial‐time computable on input . In contrast, for parametric sets with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that is always polynomial‐time computable in the size of t , and in fact can be represented using the gcd and similar functions.
Let $f_1(n), \ldots, f_k(n)$ be polynomial functions of $n$. For fixed $n\in\mathbb{N}$, let $S_n\subseteq \mathbb{N}$ be the numerical semigroup generated by $f_1(n),\ldots,f_k(n)$. As $n$ varies, we show that many invariants …
Let $f_1(n), \ldots, f_k(n)$ be polynomial functions of $n$. For fixed $n\in\mathbb{N}$, let $S_n\subseteq \mathbb{N}$ be the numerical semigroup generated by $f_1(n),\ldots,f_k(n)$. As $n$ varies, we show that many invariants of $S_n$ are eventually quasi-polynomial in $n$, such as the Frobenius number, the type, the genus, and the size of the $\Delta$-set. The tool we use is expressibility in the logical system of parametric Presburger arithmetic. Generalizing to higher dimensional families of semigroups, we also examine affine semigroups $S_n\subseteq \mathbb{N}^m$ generated be vectors whose coordinates are polynomial functions of $n$, and we prove similar results; for example, the Betti numbers are eventually quasi-polynomial functions of $n$.
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, …
Given a parametric lattice with a basis given by polynomials in Z[t], we give an algorithm to construct an LLL-reduced basis whose elements are eventually quasi-polynomial in t: that is, they are given by formulas that are piecewise polynomial in t (for sufficiently large t), such that each piece is given by a congruence class modulo a period. As a consequence, we show that there are parametric solutions of the shortest vector problem (SVP) and closest vector problem (CVP) that are also eventually quasi-polynomial in t.
We characterize all ordered Abelian groups whose first-order theory in the language {+, <, 0} is strongly dependent. The main result of this note was obtained independently by Halevi and …
We characterize all ordered Abelian groups whose first-order theory in the language {+, <, 0} is strongly dependent. The main result of this note was obtained independently by Halevi and Hasson [7] and Farré [5].
We consider an expansion of Presburger arithmetic which allows multiplication by $k$ parameters $t_1,\ldots,t_k$. A formula in this language defines a parametric set $S_\mathbf{t} \subseteq \mathbb{Z}^{d}$ as $\mathbf{t}$ varies in …
We consider an expansion of Presburger arithmetic which allows multiplication by $k$ parameters $t_1,\ldots,t_k$. A formula in this language defines a parametric set $S_\mathbf{t} \subseteq \mathbb{Z}^{d}$ as $\mathbf{t}$ varies in $\mathbb{Z}^k$, and we examine the counting function $|S_\mathbf{t}|$ as a function of $\mathbf{t}$. For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi-polynomial (there is a period $m$ such that, for sufficiently large $t$, the function is polynomial on each of the residue classes mod $m$). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming \textbf{P} $\neq$ \textbf{NP}) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1, t_2}|$ is not even polynomial-time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_\mathbf{t} \subseteq \mathbb{Z}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_\mathbf{t}|$ is always polynomial-time computable in the size of $\mathbf{t}$, and in fact can be represented using the gcd and similar functions.
We consider an expansion of Presburger arithmetic which allows multiplication by $k$ parameters $t_1,\ldots,t_k$. A formula in this language defines a parametric set $S_\mathbf{t} \subseteq \mathbb{Z}^{d}$ as $\mathbf{t}$ varies in …
We consider an expansion of Presburger arithmetic which allows multiplication by $k$ parameters $t_1,\ldots,t_k$. A formula in this language defines a parametric set $S_\mathbf{t} \subseteq \mathbb{Z}^{d}$ as $\mathbf{t}$ varies in $\mathbb{Z}^k$, and we examine the counting function $|S_\mathbf{t}|$ as a function of $\mathbf{t}$. For a single parameter, it is known that $|S_t|$ can be expressed as an eventual quasi-polynomial (there is a period $m$ such that, for sufficiently large $t$, the function is polynomial on each of the residue classes mod $m$). We show that such a nice expression is impossible with 2 or more parameters. Indeed (assuming \textbf{P} $\neq$ \textbf{NP}) we construct a parametric set $S_{t_1,t_2}$ such that $|S_{t_1, t_2}|$ is not even polynomial-time computable on input $(t_1,t_2)$. In contrast, for parametric sets $S_\mathbf{t} \subseteq \mathbb{Z}^d$ with arbitrarily many parameters, defined in a similar language without the ordering relation, we show that $|S_\mathbf{t}|$ is always polynomial-time computable in the size of $\mathbf{t}$, and in fact can be represented using the gcd and similar functions.
Parametric Presburger arithmetic concerns families of sets S_t in Z^d, for t in N, that are defined using addition, inequalities, constants in Z, Boolean operations, multiplication by t, and quantifiers …
Parametric Presburger arithmetic concerns families of sets S_t in Z^d, for t in N, that are defined using addition, inequalities, constants in Z, Boolean operations, multiplication by t, and quantifiers on variables ranging over Z. That is, such families are defined using quantifiers and Boolean combinations of formulas of the form a(t) x <= b(t), where a(t) is in Z[t]^d, b(t) in Z[t]. A function g: N -> Z is a quasi-polynomial if there exists a period m and polynomials f_0, ..., f_{m-1} in Q[t] such that g(t)=f_i(t) for t congruent to i (mod m.) Recent results of Chen, Li, Sam; Calegari, Walker; Roune, Woods; and Shen concern specific families in parametric Presburger arithmetic that exhibit quasi-polynomial behavior. For example, S_t might be an a quasi-polynomial function of t or an element x(t) in S_t might be specifiable as a function with quasi-polynomial coordinates, for sufficiently large t. Woods conjectured that all parametric Presburger sets exhibit this quasi-polynomial behavior. Here, we prove this conjecture, using various tools from logic and combinatorics.
Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior, Discrete Analysis 2017:4, 34 pp. Let $T$ be a triangle with vertices $(0,0)$, $(0,1/3)$, and $(1,0)$, and let $t$ be a positive …
Parametric Presburger arithmetic: logic, combinatorics, and quasi-polynomial behavior, Discrete Analysis 2017:4, 34 pp. Let $T$ be a triangle with vertices $(0,0)$, $(0,1/3)$, and $(1,0)$, and let $t$ be a positive integer. Then it is not hard to check that there are three quadratics $q_1,q_2$ and $q_3$ such that the number of integer points in $tT$ is $q_i(t)$ if $t\equiv i$ mod 3. In a situation like this, we say that the number of integer points is _quasipolynomial_ with period 3. In 1962, Ehrhart proved that if $P$ is a polytope in $\mathbb Z^d$ defined by a finite set of linear inequalities of the form $a_i.x\leq b_i$, where each of the $a_i$ belong to $\mathbb Z^d$ and $b$ belongs to $\mathbb Z$, then the number of lattice points in $tP$ is quasipolynomial with period $m$, where $m$ is the smallest integer such that the vertices of $mP$ are all lattice points. Since then, the same conclusion has been established for other families of sets $S_t\subset \mathbb Z^d$ by Chen, Li and Sam, by Calegari and Walker, and by Roune and Woods. After these results, it was tempting to wonder whether _all_ families of sets, provided that they are sufficiently nice in some appropriate sense, exhibit this quasipolynomial behaviour. The constraints would have to be reasonably strong -- for example, the number of lattice points inside the unit sphere of radius $t$ is certainly not quasipolynomial (and indeed, estimating it is a famous problem) -- but one could still hope for a general theorem that would encompass the known results and give a number of further ones. It turns out that the right behaviour to look for in general is that the size of $S_t$ should be _eventually_ quasipolynomial -- that is, it should agree with a quasipolynomial for sufficiently large $t$. Woods conjectured that eventual quasipolynomial behaviour should occur whenever the family is definable in _parametric Presburger arithmetic_. Roughly what this means (for a more precise definition, see the paper) is that the family $S_t$ of subsets of $\mathbb Z^d$ can be defined using addition, inequalities, integer constants, Boolean operations, multiplication by $t$, and quantification over $\mathbb Z$. The polytopes discussed earlier are examples. For a somewhat different kind of example, let $S_t$ be the set of positive integers $n$ such that there do not exist non-negative integers $a,b,c$ with $n=at+b(t+1)+c(t+2)$. This example involves quantification over $\mathbb Z$, but again the number of points in $S_t$ turns out to be quasipolynomial: in fact, it is $\lfloor t^2/4 \rfloor$ (the paper also discusses a quasipolynomial formula for the maximum element of $S_t$). Note that it is crucial in this definition that multiplication, except by the parameter $t$, should not be allowed, since otherwise we would have the full power of Peano arithmetic, which is undecidable. The main result of this paper is a proof of this very appealing conjecture. The proof uses a series of reductions that make the family simpler and simpler until the result can be shown using previously developed methods. One of the reductions uses the well-known technique of quantifier elimination. However, this cannot be applied straightforwardly, owing to the multiplication-by-$t$ operation, which is not part of standard Presburger arithmetic (hence the word "parametric"). The paper also discusses the power of parametric Presburger arithmetic, which, considering the necessary restrictions, is greater than one might expect. Thus, it proves eventual quasipolynomial behaviour for an extremely wide class of families and is probably the most general result one could hope for along these lines. <sup><sub>[Image created by Georgios Barmparis, Georgios Kopidakis and Ioannis Remediakis](http://www.mdpi.com/1996-1944/9/4/301/htm)</sub></sup>
We characterize all ordered Abelian groups whose first order theory in the language {+,<} is strongly dependent. The main result of this note was obtained independently by Halevi-Hasson and Farr\'e.
We characterize all ordered Abelian groups whose first order theory in the language {+,<} is strongly dependent. The main result of this note was obtained independently by Halevi-Hasson and Farr\'e.
We consider strong expansions of the theory of ordered Abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets …
We consider strong expansions of the theory of ordered Abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets in such theories, in particular as relates to definable infinite d
We prove that any left-ordered inp-minimal group is abelian, and we provide an example of a non-abelian left-ordered group of dp-rank 2.
We prove that any left-ordered inp-minimal group is abelian, and we provide an example of a non-abelian left-ordered group of dp-rank 2.
We generalize Cooper's method of quantifier elimination for classical Presburger arithmetic to give a new proof that all parametric Presburger families (as defined by Kevin Woods) are definable by formulas …
We generalize Cooper's method of quantifier elimination for classical Presburger arithmetic to give a new proof that all parametric Presburger families (as defined by Kevin Woods) are definable by formulas with polynomially bounded quantifiers in an expanded language with predicates for divisibility by f(t) for every polynomial f over the integers. In fact, this quantifier bounding method works more generally in expansions of Presburger arithmetic with multiplication by scalars from any ring of functions into Z.
We prove that any left-ordered inp-minimal group is abelian, and we provide an example of a non-abelian left-ordered group of dp-rank 2.
We prove that any left-ordered inp-minimal group is abelian, and we provide an example of a non-abelian left-ordered group of dp-rank 2.
We consider strong expansions of the theory of ordered abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets …
We consider strong expansions of the theory of ordered abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets in such theories, in particular as relates to definable infinite discrete sets. We also provide a range of examples of strong expansions of ordered abelian groups which demonstrate the great variety of such theories.
We show that in a stable first-order theory, the failure of higher dimensional type amalgamation can always be witnessed by algebraic structures that we call n-ary polygroupoids. This generalizes a …
We show that in a stable first-order theory, the failure of higher dimensional type amalgamation can always be witnessed by algebraic structures that we call n-ary polygroupoids. This generalizes a result of Hrushovski in [16] that failures of 4-amalgamation are witnessed by definable groupoids (which correspond to 2-ary polygroupoids in our terminology). The n-ary polygroupoids are definable in a mild expansion of the language (adding a predicate for a Morley sequence).
A visceral structure on a model is given by a definable base for a uniform topology on its universe M in which all basic open sets are infinite and any …
A visceral structure on a model is given by a definable base for a uniform topology on its universe M in which all basic open sets are infinite and any infinite definable subset X of M has non-empty interior. Assuming only viscerality, we show that the definable sets in M satisfy some desirable topological tameness conditions. For example, any definable unary function has a finite set of discontinuities; any definable function from some Cartesian power of M into M is continuous on an open set; and assuming definable finite choice, we obtain a cell decomposition result for definable sets. Under an additional topological assumption (no space-filling functions), we prove that the natural notion of topological dimension is invariant under definable bijections. These results generalize some of the theorems proved by Simon and Walsberg, who assumed dp-minimality in addition to viscerality. In the final two sections, we construct new examples of visceral structures a subclass of which are dp-minimal yet not weakly o-minimal.
This note contains a new, corrected proof of the dp-minimality of an example previously published by the same authors in Dp-minimality: basic facts and examples. The example is of an …
This note contains a new, corrected proof of the dp-minimality of an example previously published by the same authors in Dp-minimality: basic facts and examples. The example is of an ordered divisible abelian group which is dp-minimal and contains a unary predicate defining an open subset with infinitely many connected components.
A visceral structure on M is given by a definable base for a uniform topology on its universe in which all basic open sets are infinite and any infinite definable …
A visceral structure on M is given by a definable base for a uniform topology on its universe in which all basic open sets are infinite and any infinite definable subset X of M has non-empty interior. This context includes o-minimal ordered groups, p-adic fields, and other examples. Assuming only viscerality, we show that the definable sets in M satisfy some desirable topological tameness conditions. For example, any definable unary function on M has a finite set of discontinuities; any definable function on a Cartesian power of M is continuous on a nonempty open set; and assuming definable finite choice, we obtain a cell decomposition result for definable sets. Under an additional topological assumption ("no space-filling functions"), we prove that the natural notion of topological dimension is invariant under definable bijections. These results generalize theorems proved by Simon and Walsberg, who assumed dp-minimality in addition to viscerality. In the final section, we construct new examples of visceral structures.
We consider strong expansions of the theory of ordered abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets …
We consider strong expansions of the theory of ordered abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets in such theories, in particular as relates to definable infinite discrete sets. We also provide a range of examples of strong expansions of ordered abelian groups which demonstrate the great variety of such theories.
We give an explicit description of the homomorphism group H_n(p) of a strong type p in any stable theory under the assumption that for every non-forking extension q of p …
We give an explicit description of the homomorphism group H_n(p) of a strong type p in any stable theory under the assumption that for every non-forking extension q of p the groups H_i(q) are trivial for i at least 2 but less than n. The group H_n(p) turns out to be isomorphic to the automorphism group of a certain piece of the algebraic closure of n independent realizations of p; it was shown earlier by the authors that such a group must be abelian. We call this the correspondence in analogy with the Hurewicz Theorem in algebraic topology.
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result …
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result of Hrushovski that failures of 4-amalgamation in stable theories are witnessed by definable groupoids (which are 2-ary polygroupoids in our terminology). The n-ary polygroupoids are definable in a mild expansion of the language (adding a unary predicate for an infinite Morley sequence).
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result …
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result of Hrushovski that failures of 4-amalgamation in stable theories are witnessed by definable groupoids (which are 2-ary polygroupoids in our terminology). The n-ary polygroupoids are definable in a mild expansion of the language (adding a unary predicate for an infinite Morley sequence).
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result …
We show that in a stable first-order theory, the failure of higher-dimensional type amalgamation can always be witnessed by algebraic structures which we call n-ary polygroupoids. This generalizes a result of Hrushovski that failures of 4-amalgamation in stable theories are witnessed by definable groupoids (which are 2-ary polygroupoids in our terminology). The n-ary polygroupoids are definable in a mild expansion of the language (adding a unary predicate for an infinite Morley sequence).
We give an explicit description of the homomorphism group H_n(p) of a strong type p in any stable theory under the assumption that for every non-forking extension q of p …
We give an explicit description of the homomorphism group H_n(p) of a strong type p in any stable theory under the assumption that for every non-forking extension q of p the groups H_i(q) are trivial for i at least 2 but less than n. The group H_n(p) turns out to be isomorphic to the automorphism group of a certain piece of the algebraic closure of n independent realizations of p; it was shown earlier by the authors that such a group must be abelian. We call this the "Hurewicz correspondence" in analogy with the Hurewicz Theorem in algebraic topology.
A first-order theory<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"><mml:semantics><mml:mi>T</mml:mi><mml:annotation encoding="application/x-tex">T</mml:annotation></mml:semantics></mml:math></inline-formula>has the<italic>Schröder-Bernstein (SB) property</italic>if any pair of elementarily bi-embeddable models are isomorphic. We prove that<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>has an expansion by …
A first-order theory<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper T"><mml:semantics><mml:mi>T</mml:mi><mml:annotation encoding="application/x-tex">T</mml:annotation></mml:semantics></mml:math></inline-formula>has the<italic>Schröder-Bernstein (SB) property</italic>if any pair of elementarily bi-embeddable models are isomorphic. We prove that<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>has an expansion by constants with the SB property if and only 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 superstable and non-multidimensional. We also prove that among superstable theories<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>, the class of<inline-formula content-type="math/mathml"><mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a"><mml:semantics><mml:mi>a</mml:mi><mml:annotation encoding="application/x-tex">a</mml:annotation></mml:semantics></mml:math></inline-formula>-saturated models 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>has the SB property if and only 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>has no nomadic types.
Abstract We present definitions of homology groups H n ( p ), n ≥ 0, associated to a complete type p . We show that if the generalized amalgamation properties …
Abstract We present definitions of homology groups H n ( p ), n ≥ 0, associated to a complete type p . We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute the group H 2 ( p ) for strong types in stable theories and show that any profinite abelian group can occur as the group H 2 ( p ).
A first-order theory T has the Schroder-Bernstein (SB) property if any pair of elementarily bi-embeddable models are isomorphic. We prove that T has an expansion by constants that has the …
A first-order theory T has the Schroder-Bernstein (SB) property if any pair of elementarily bi-embeddable models are isomorphic. We prove that T has an expansion by constants that has the SB property if and only if T is superstable and non-multidimensional. We also prove that among superstable theories T, the class of a-saturated models of T has the SB property if and only if T has no nomadic types.
A first-order theory T has the Schr\"oder-Bernstein (SB) property if any pair of elementarily bi-embeddable models are isomorphic. We prove that T has an expansion by constants that has the …
A first-order theory T has the Schr\"oder-Bernstein (SB) property if any pair of elementarily bi-embeddable models are isomorphic. We prove that T has an expansion by constants that has the SB property if and only if T is superstable and non-multidimensional. We also prove that among superstable theories T, the class of a-saturated models of T has the SB property if and only if T has no nomadic types.
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of …
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of the rest of the paper is dedicated to examples. We establish via a simple proof that any weakly o-minimal theory is dp-minimal and then give an example of a weakly o-minimal group not obtained by adding traces of externally definable sets. Next we give an example of a divisible ordered Abelian group which is dp-minimal and not weakly o-minimal. Finally we establish that the field of p-adic numbers is dp-minimal.
We present definitions of homology groups associated to a family of amalgamation functors. We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute …
We present definitions of homology groups associated to a family of amalgamation functors. We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute the group H_2 for strong types in stable theories and show that in this context, the class of possible groups H_2 is precisely the profinite abelian groups.
Abstract Building on Hrushovski's work in [5], we study definable groupoids in stable theories and their relationship with 3-uniqueness and finite internal covers. We introduce the notion of retractability of …
Abstract Building on Hrushovski's work in [5], we study definable groupoids in stable theories and their relationship with 3-uniqueness and finite internal covers. We introduce the notion of retractability of a definable groupoid (which is slightly stronger than Hrushovski's notion of eliminability), give some criteria for when groupoids are retractable, and show how retractability relates to both 3-uniqueness and the splitness of finite internal covers. One application we give is a new direct method of constructing non-eliminable groupoids from witnesses to the failure of 3-uniqueness. Another application is a proof that any finite internal cover of a stable theory with a centerless liaison groupoid is almost split.
This paper continues the study of generalized amalgamation properties. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. …
This paper continues the study of generalized amalgamation properties. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. We show that such groupoids must be abelian and link the binding group of the groupoids to a certain automorphism group of the monster model, showing that the group must be abelian as well.
We also study connections between n-existence and n-uniqueness properties for various dimensions n in the wider context of simple theories. We introduce a family of weaker existence and uniqueness properties. Many of these properties did appear in the literature before; we give a category-theoretic formulation and study them systematically. Finally, we give examples of first-order simple unstable theories showing, in particular, that there is no straightforward generalization of the groupoid construction in an unstable context.
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).
This paper continues the study of generalized amalgamation properties. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. …
This paper continues the study of generalized amalgamation properties. Part of the paper provides a finer analysis of the groupoids that arise from failure of 3-uniqueness in a stable theory. We show that such groupoids must be abelian and link the binding group of the groupoids to a certain automorphism group of the monster model, showing that the group must be abelian as well. We also study connections between n-existence and n-uniqueness properties for various "dimensions" n in the wider context of simple theories. We introduce a family of weaker existence and uniqueness properties. Many of these properties did appear in the literature before; we give a category-theoretic formulation and study them systematically. Finally, we give examples of first-order simple unstable theories showing, in particular, that there is no straightforward generalization of the groupoid construction in an unstable context.
For a countable, weakly minimal theory, we show that the Schroeder-Bernstein property (any two elementarily bi-embeddable models are isomorphic) is equivalent to both a condition on orbits of rank 1 …
For a countable, weakly minimal theory, we show that the Schroeder-Bernstein property (any two elementarily bi-embeddable models are isomorphic) is equivalent to both a condition on orbits of rank 1 types and the property that the theory has no infinite collection of pairwise bi-embeddable, pairwise nonisomorphic models. We conclude that for countable weakly minimal theories, the Schroeder-Bernstein property is absolute between transitive models of ZFC.
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.
Abstract Building on Hrushovski's work in [5], we study definable groupoids in stable theories and their relationship with 3-uniqueness and finite internal covers. We introduce the notion of retractability of …
Abstract Building on Hrushovski's work in [5], we study definable groupoids in stable theories and their relationship with 3-uniqueness and finite internal covers. We introduce the notion of retractability of a definable groupoid (which is slightly stronger than Hrushovski's notion of eliminability), give some criteria for when groupoids are retractable, and show how retractability relates to both 3-uniqueness and the splitness of finite internal covers. One application we give is a new direct method of constructing non-eliminable groupoids from witnesses to the failure of 3-uniqueness. Another application is a proof that any finite internal cover of a stable theory with a centerless liaison groupoid is almost split.
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).
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.
Abstract This book gives an account of the fundamental results in geometric stability theory, a subject that has grown out of categoricity and classification theory. This approach studies the fine …
Abstract This book gives an account of the fundamental results in geometric stability theory, a subject that has grown out of categoricity and classification theory. This approach studies the fine structure of models of stable theories, using the geometry of forking; this often achieves global results relevant to classification theory. Topics range from Zilber-Cherlin classification of infinite locally finite homogenous geometries, to regular types, their geometries, and their role in superstable theories. The structure and existence of definable groups is featured prominently, as is work by Hrushovski. The book is unique in the range and depth of material covered and will be invaluable to anyone interested in modern model theory.
A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_{m-1}$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically - …
A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_{m-1}$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically - and "reasonably'' - appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable $t$, and defined by linear inequalities of the form $a_1x_1+\cdots+a_dx_d\le b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the $a_i$ are also allowed to vary with $t$. We discuss these "unreasonable'' results and conjecture a general class of sets that exhibit various (eventual) quasi-polynomial behaviors: sets $S_t\subseteq\mathbb{N}^d$ that are defined with quantifiers ($\forall$, $\exists$), boolean operations (and, or, not), and statements of the form $a_1(t)x_1+\cdots+a_d(t)x_d \le b(t)$, where $a_i(t)$ and $b(t)$ are polynomials in $t$. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures. The title is a play on Eugene Wigner's "The unreasonable effectiveness of mathematics in the natural sciences''.
Let T be a first-order theory. A correspondence is established between internal covers of models of T and definable groupoids within T. We also consider amalgamations of independent diagrams of …
Let T be a first-order theory. A correspondence is established between internal covers of models of T and definable groupoids within T. We also consider amalgamations of independent diagrams of algebraically closed substructures, and find strong relation between covers, uniqueness for 3-amalgamation, existence of 4-amalgamation, imaginaries of T\si, and definable groupoids. As a corollary, we describe the imaginary elements of families of finite-dimensional vector spaces over pseudo-finite fields.
The open core of an expansion of a dense linear order is its reduct, in the sense of definability, generated by the collection of all of its open definable sets. …
The open core of an expansion of a dense linear order is its reduct, in the sense of definability, generated by the collection of all of its open definable sets. In this paper, expansions of dense linear orders that have o-minimal open core are investigated, with emphasis on expansions of densely ordered groups. The first main result establishes conditions under which an expansion of a densely ordered group has an o-minimal open core. Specifically, the following is proved: <disp-quote> <italic>Let <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="German upper R"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="fraktur">R</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathfrak R</mml:annotation> </mml:semantics> </mml:math> </inline-formula> be an expansion of a densely ordered group <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-parenthesis upper R comma greater-than comma asterisk right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mo stretchy="false">(</mml:mo> <mml:mi>R</mml:mi> <mml:mo>,</mml:mo> <mml:mo>></mml:mo> <mml:mo>,</mml:mo> <mml:mo>∗</mml:mo> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">(R,>,*)</mml:annotation> </mml:semantics> </mml:math> </inline-formula> that is definably complete and satisfies the uniform finiteness property. Then the open core of <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="German upper R"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="fraktur">R</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">\mathfrak R</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is o-minimal.</italic> </disp-quote> Two examples of classes of structures that are not o-minimal yet have o-minimal open core are discussed: dense pairs of o-minimal expansions of ordered groups, and expansions of o-minimal structures by generic predicates. In particular, such structures have open core interdefinable with the original o-minimal structure. These examples are differentiated by the existence of definable unary functions whose graphs are dense in the plane, a phenomenon that can occur in dense pairs but not in expansions by generic predicates. The property of having no dense graphs is examined and related to uniform finiteness, definable completeness, and having o-minimal open core.
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.
Let T be a first-order theory. A correspondence is established between internal covers of models of T and definable groupoids within T. We also consider amalgamations of independent diagrams of …
Let T be a first-order theory. A correspondence is established between internal covers of models of T and definable groupoids within T. We also consider amalgamations of independent diagrams of algebraically closed substructures, and find strong relation between covers, uniqueness for 3-amalgamation, existence of 4-amalgamation, imaginaries of T^\si, and definable groupoids. As a corollary, we describe the imaginary elements of families of finite-dimensional vector spaces over pseudo-finite fields.
The Frobenius number of relatively prime positive integers $a_1, \ldots, a_n$ is the largest integer that is not a nononegative integer combination of the $a_i.$ Given positive integers $a_1, \ldots, …
The Frobenius number of relatively prime positive integers $a_1, \ldots, a_n$ is the largest integer that is not a nononegative integer combination of the $a_i.$ Given positive integers $a_1, \ldots, a_n$ with $n \ge 2,$ the set of multiples of $\gcd(a_1, \ldots, a_n)$ which have less than $m$ distinct representations as a nonnegative integer combination of the $a_i$ is bounded above, so we define $f_{m, \ell}(a_1, \ldots, a_n)$ to be the $\ell^{\text{th}}$ largest multiple of $\gcd(a_1, \ldots, a_n)$ with less than $m$ distinct representations (which generalizes the Frobenius number) and $g_m(a_1, \ldots, a_n)$ to be the number of positive multiples of $\gcd(a_1, \ldots, a_n)$ with less than $m$ distinct representations. In the parametric Frobenius problem, the arguments are polynomials. Let $P_1, \ldots, P_n$ be integer valued polynomials of one variable which are eventually positive. We prove that $f_{m, \ell}(P_1(t), \ldots, P_n(t))$ and $g_m(P_1(t), \ldots, P_n(t)),$ as functions of $t,$ are eventually quasi-polynomial. A function $h$ is eventually quasi-polynomial if there exist $d$ and polynomials $R_0, \ldots, R_{d-1}$ such that for such that for sufficiently large integers $t,$ $h(t)=R_{t \pmod{d}}(t).$ We do so by formulating a type of parametric problem that generalizes the parametric Frobenius Problem, which we call a parametric exclusion problem. We prove that the $\ell^{\text{th}}$ largest value of some polynomial objective function, with multiplicity, for a parametric exclusion problem and the size of its feasible set are eventually quasi-polynomial functions of $t.$
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.
Abstract We present definitions of homology groups H n ( p ), n ≥ 0, associated to a complete type p . We show that if the generalized amalgamation properties …
Abstract We present definitions of homology groups H n ( p ), n ≥ 0, associated to a complete type p . We show that if the generalized amalgamation properties hold, then the homology groups are trivial. We compute the group H 2 ( p ) for strong types in stable theories and show that any profinite abelian group can occur as the group H 2 ( p ).
A linearly ordered structure is weakly o-minimal if all of its definable sets in one variable are the union of finitely many convex sets in the structure. Weakly o-minimal structures …
A linearly ordered structure is weakly o-minimal if all of its definable sets in one variable are the union of finitely many convex sets in the structure. Weakly o-minimal structures were introduced by Dickmann, and they arise in several contexts. We here prove several fundamental results about weakly o-minimal structures. Foremost among these, we show that every weakly o-minimal ordered field is real closed. We also develop a substantial theory of definable sets in weakly o-minimal structures, patterned, as much as possible, after that for o-minimal structures.
We consider strong expansions of the theory of ordered Abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets …
We consider strong expansions of the theory of ordered Abelian groups. We show that the assumption of strength has a multitude of desirable consequences for the structure of definable sets in such theories, in particular as relates to definable infinite d
A first order theory is totally categorical if it has exactly one model in each infinite power. We prove here that every such theory admits a finite language, and is …
A first order theory is totally categorical if it has exactly one model in each infinite power. We prove here that every such theory admits a finite language, and is finitely axiomatizable in that language, modulo axioms stating that the structure is infinite. This was conjectured by Vaught. We also show that every <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ<!-- ℵ --></mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-stable, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="normal alef 0"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi mathvariant="normal">ℵ<!-- ℵ --></mml:mi> <mml:mn>0</mml:mn> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\aleph _0}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-categorical structure is a reduct of one that has finitely many models in small uncountable powers. In the case of structures of disintegrated type we nearly find an explicit structure theorem, and show that the remaining obstacle resides in certain nilpotent automorphism groups.
The integer hull of a polyhedron is the convex hull of the integer points contained in it. We show that the vertices of the integer hulls of a rational family …
The integer hull of a polyhedron is the convex hull of the integer points contained in it. We show that the vertices of the integer hulls of a rational family of polyhedra of size $O(n)$ have eventually quasipolynomial coordinates. As a corollary, we show that the stable commutator length of elements in a surgery family is eventually a ratio of quasipolynomials, and that unit balls in the scl norm eventually quasiconverge in finite-dimensional surgery families.
Under [Formula: see text]-amalgamation, we obtain the canonical hyperdefinable group from the group configuration.
Under [Formula: see text]-amalgamation, we obtain the canonical hyperdefinable group from the group configuration.
Abstract We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent theories.
Abstract We develop the theory of generically stable types, independence relation based on nonforking and stable weight in the context of dependent theories.
We 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.
We classify dp-minimal pure fields up to elementary equivalence. Most are equivalent to Hahn series fields $K((t^\Gamma))$ where $\Gamma$ satisfies some divisibility conditions and $K$ is $\mathbb{F}_p^{alg}$ or a local …
We classify dp-minimal pure fields up to elementary equivalence. Most are equivalent to Hahn series fields $K((t^\Gamma))$ where $\Gamma$ satisfies some divisibility conditions and $K$ is $\mathbb{F}_p^{alg}$ or a local field of characteristic zero. We show that dp-small fields (including VC-minimal fields) are algebraically closed or real closed.
Let ℜ be an expansion of a dense linear order ( R , <) without endpoints having the intermediate value property , that is, for all a, b ∈ R …
Let ℜ be an expansion of a dense linear order ( R , <) without endpoints having the intermediate value property , that is, for all a, b ∈ R , every continuous (parametrically) definable function f : [ a, b ] → R takes on all values in R between f ( a ) and f(b) . Every expansion of the real line (ℝ, <), as well as every o-minimal expansion of ( R , <), has the intermediate value property. Conversely, some nice properties, often associated with expansions of (ℝ, <) or with o-minimal structures, hold for sets and functions definable in ℜ. For example, images of closed bounded definable sets under continuous definable maps are closed and bounded (Proposition 1.10). Of particular interest is the case that ℜ expands an ordered group, that is, ℜ defines a binary operation * such that ( R , <, *) is an ordered group. Then ( R , *) is abelian and divisible (Proposition 2.2). Continuous nontrivial definable endo-morphisms of ( R , *) are surjective and strictly monotone, and monotone nontrivial definable endomorphisms of ( R , *) are strictly monotone, continuous and surjective (Proposition 2.4). There is a generalization of the familiar result that every proper noncyclic subgroup of (ℝ, +) is dense and codense in ℝ: If G is a proper nontrivial subgroup of ( R , *) definable in ℜ, then either G is dense and codense in R , or G contains an element u such that ( R , <, *, e, u, G ) is elementarily equivalent to (ℚ, <, +, 0, 1, ℤ), where e denotes the identity element of ( R , *) (Theorem 2.3). Here is an outline of this paper. First, we deal with some basic topological results. We then assume that ℜ expands an ordered group and establish the results mentioned in the preceding paragraph. Some examples are then given, followed by a brief discussion of analytic results and possible limitations. In an appendix, an explicit axiomatization (used in the proof of Theorem 2.3) is given for the complete theory of the structure (ℚ, <, +, 0, 1, ℤ).
by similar or dissimilar methodology now known or hereafter developed is forbidden.
by similar or dissimilar methodology now known or hereafter developed is forbidden.
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 ).
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is …
In this article, we develop tame topology over dp-minimal structures equipped with definable uniformities satisfying certain assumptions. Our assumptions are enough to ensure that definable sets are tame: there is a good notion of dimension on definable sets, definable functions are almost everywhere continuous, and definable sets are finite unions of graphs of definable continuous "multivalued functions." This generalizes known statements about weakly o-minimal, C-minimal, and P-minimal theories.
A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_m-1$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically – …
A function $g$, with domain the natural numbers, is a quasi-polynomial if there exists a period $m$ and polynomials $p_0,p_1,\ldots,p_m-1$ such that $g(t)=p_i(t)$ for $t\equiv i\bmod m$. Quasi-polynomials classically – and ``reasonably'' – appear in Ehrhart theory and in other contexts where one examines a family of polyhedra, parametrized by a variable t, and defined by linear inequalities of the form $a_1x_1+⋯+a_dx_d≤ b(t)$. Recent results of Chen, Li, Sam; Calegari, Walker; and Roune, Woods show a quasi-polynomial structure in several problems where the $a_i$ are also allowed to vary with $t$. We discuss these ``unreasonable'' results and conjecture a general class of sets that exhibit various (eventual) quasi-polynomial behaviors: sets $S_t$ that are defined with quantifiers $(\forall , ∃)$, boolean operations (and, or, not), and statements of the form $a_1(t)x_1+⋯+a_d(t)x_d ≤ b(t)$, where $a_i(t)$ and $b(t)$ are polynomials in $t$. These sets are a generalization of sets defined in the Presburger arithmetic. We prove several relationships between our conjectures, and we prove several special cases of the conjectures.
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.
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of …
We study the notion of dp-minimality, beginning by providing several essential facts about dp-minimality, establishing several equivalent definitions for dp-minimality, and comparing dp-minimality to other minimality notions. The majority of the rest of the paper is dedicated to examples. We establish via a simple proof that any weakly o-minimal theory is dp-minimal and then give an example of a weakly o-minimal group not obtained by adding traces of externally definable sets. Next we give an example of a divisible ordered Abelian group which is dp-minimal and not weakly o-minimal. Finally we establish that the field of p-adic numbers is dp-minimal.
We show that any rosy CM-trivial theory has weak canonical bases, and CM-triviality in the real sort is equivalent to CM-triviality with geometric elimination of imaginaries. We also show that …
We show that any rosy CM-trivial theory has weak canonical bases, and CM-triviality in the real sort is equivalent to CM-triviality with geometric elimination of imaginaries. We also show that CM-triviality is equivalent to the modularity in O-minimal theories with elimination of imaginaries.
Presburger's essay on the completeness and decidability of arithmetic with integer addition but without multiplication is a milestone in the history of mathematical logic and formal metatheory. The proof is …
Presburger's essay on the completeness and decidability of arithmetic with integer addition but without multiplication is a milestone in the history of mathematical logic and formal metatheory. The proof is constructive, using Tarski-style quantifier elimination and a four-part recursive comprehension principle for axiomatic consequence characterization. Presburger's proof for the completeness of first order arithmetic with identity and addition but without multiplication, in light of the restrictive formal metatheorems of Gödel, Church, and Rosser, takes the foundations of arithmetic in mathematical logic to the limits of completeness and decidability.
We prove a conjecture of Denef on parameterized $p$-adic analytic integrals using an analytic cell decomposition theorem, which we also prove in this paper. This cell decomposition theorem describes piecewise …
We prove a conjecture of Denef on parameterized $p$-adic analytic integrals using an analytic cell decomposition theorem, which we also prove in this paper. This cell decomposition theorem describes piecewise the valuation of analytic functions (and more generally of subanalytic functions), the pieces being geometrically simple sets, called cells. We also classify subanalytic sets up to subanalytic bijection.
Let S be a numerical monoid with minimal generating set 〈n 1 , …, n t 〉. For m ∈ S, if [Formula: see text], then [Formula: see text] is …
Let S be a numerical monoid with minimal generating set 〈n 1 , …, n t 〉. For m ∈ S, if [Formula: see text], then [Formula: see text] is called a factorization length of m. We denote by ℒ(m) = {m 1 , …, m k } (where m i < m i+1 for each 1 ≤ i < k) the set of all possible factorization lengths of m. The Delta set of m is defined by Δ(m) = {m i+1 - m i | 1 ≤ i < k} and the Delta set of S by Δ(S) = ⋃ m∈S Δ(m). In this paper, we expand on the study of Δ(S) begun in [C. Bowles, S. T. Chapman, N. Kaplan and D. Reiser, On delta sets of numerical monoids, J. Algebra Appl. 5 (2006) 1–24] in the following manner. Let r 1 , r 2 , …, r t be an increasing sequence of positive integers and M n = 〈n, n + r 1 , n + r 2 , …, n + r t 〉 a numerical monoid where n is some positive integer. We prove that there exists a positive integer N such that if n > N then |Δ(M n )| = 1. If t = 2 and r 1 and r 2 are relatively prime, then we determine a value for N which is sharp.
The purpose of this paper is twofold. In §1 and §2 which are largely expository we develop the known theory of ℵ 1 -categoricity in terms of strongly minimal sets. …
The purpose of this paper is twofold. In §1 and §2 which are largely expository we develop the known theory of ℵ 1 -categoricity in terms of strongly minimal sets. In §3 we settle affirmatively Vaught's conjecture that a complete ℵ 1 -categorical theory has either just one or just ℵ 0 countable models, and in §4 we present an example which serves to illustrate the ideas of §3. As far as we know the only work published on strongly minimal sets is that of Marsh [3]. The present exposition goes beyond [3] in showing that any ℵ-categorical theory has a principal extension in which some formula is strongly minimal.