A proof of the Borel completeness of torsion free abelian groups
A proof of the Borel completeness of torsion free abelian groups is presented. This proof differs considerably from the approach of Paolini-Shelah.
Source author record
Michael C. Laskowski
Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.
ResearcherUnclaimed source record
Catalog footprint
Research overview
19works
4topics
4close collaborators
Published work
19 publications
preprint2022arXiv
Borel complexity of modules
We prove that for a countable, commutative ring R, the class of countable R-modules either has only countably many isomorphism types, or else it is Borel complete. The machinery gives a succinct proof of the Borel completeness of TFAB, the class of torsion-free abelian groups. We also prove that for any countable ring R, both the class of left R-modules endowed with an endomorphism and the class of left R-modules with four named submodules are Borel complete.
Open access
preprint2022arXiv
Jumps in speeds of hereditary properties in finite relational languages
Given a finite relational language L, a hereditary L-property is a class of finite L-structures closed under isomorphism and substructure. The speed of H is the function which sends an integer n≥1 to the number of distinct elements in H with underlying set {1,...,n}. In this paper we give a description of many new jumps in the possible speeds of a hereditary L-property, where L is any finite relational language. In particular, we characterize the jumps in the polynomial and factorial ranges, and show they are essentially the same as in the case of graphs. The results in the factorial range are new for all examples requiring a language of arity greater than two, including the setting of hereditary properties of k-uniform hypergraphs for k>2. Further, adapting an example of Balogh, Bollobás, and Weinreich, we show that for all k≥2, there are hereditary properties of k-uniform hypergraphs whose speeds oscillate between functions near the upper and lower bounds of the penultimate range, ruling out many natural functions as jumps in that range. Our theorems about the factorial range use model theoretic tools related to the notion of mutual algebricity.
Open access
preprint2022arXiv
Worst case expansions of complete theories
Given a complete theory T and a subset Y⊆Xk, we precisely determine the {\em worst case complexity}, with respect to further monadic expansions, of an expansion (M,Y) by Y of a model M of T with universe X. In particular, although by definition monadically stable/NIP theories are robust under arbitrary monadic expansions, we show that monadically NFCP (equivalently, mutually algebraic) theories are the largest class that is robust under anything beyond monadic expansions. We also exhibit a paradigmatic structure for the failure of each of monadic NFCP/stable/NIP and prove each of these paradigms definably embeds into a monadic expansion of a sufficiently saturated model of any theory without the corresponding property.
Open access
preprint2021arXiv
Counting siblings in universal theories
We show that if a countable structure M in a finite relational language is not cellular, then there is an age-preserving N⊇M such that 2ℵ0 many structures are bi-embeddable with N. The proof proceeds by a case division based on mutual algebraicity.
Open access
preprint2021arXiv
Mutual algebraicity and cellularity
We prove two results intended to streamline proofs about cellularity that pass through mutual algebraicity. First, we show that a countable structure M is cellular if and only if M is ω-categorical and mutually algebraic. Second, if a countable structure M in a finite relational language is mutually algebraic non-cellular, we show it admits an elementary extension adding infinitely many infinite MA-connected components. Towards these results, we introduce MA-presentations of a mutually algebraic structure, in which every atomic formula is mutually algebraic. This allows for an improved quantifier elimination and a decomposition of the structure into independent pieces. We also show this decomposition is largely independent of the MA-presentation chosen.
Open access
preprint2019arXiv
Weakly minimal groups with a new predicate
Fix a weakly minimal (i.e., superstable U-rank 1) structure M. Let M∗ be an expansion by constants for an elementary substructure, and let A be an arbitrary subset of the universe M. We show that all formulas in the expansion (M∗,A) are equivalent to bounded formulas, and so (M,A) is stable (or NIP) if and only if the M-induced structure AM on A is stable (or NIP). We then restrict to the case that M is a pure abelian group with a weakly minimal theory, and AM is mutually algebraic (equivalently, weakly minimal with trivial forking). This setting encompasses most of the recent research on stable expansions of (Z,+). Using various characterizations of mutual algebraicity, we give new examples of stable structures of the form (M,A). Most notably, we show that if (G,+) is a weakly minimal additive subgroup of the algebraic numbers, A⊆G is enumerated by a homogeneous linear recurrence relation with algebraic coefficients, and no repeated root of the characteristic polynomial of A is a root of unity, then (G,+,B) is superstable for any B⊆A.
Open access
preprint2016arXiv
Borel Complexity and Potential Canonical Scott Sentences
We define and investigate HC-forcing invariant formulas of set theory, whose interpretations in the hereditarily countable sets are well behaved under forcing extensions. This leads naturally to a notion of cardinality ||Phi|| for sentences Phi of Lω1,ω, which counts the number of sentences of L∞,ω that, in some forcing extension, become a canonical Scott sentence of a model of Phi. We show this cardinal bounds the complexity of (Mod(Phi), iso), the class of models of Phi with universe omega, by proving that (Mod(Phi),iso) is not Borel reducible to (Mod(Psi),iso) whenever ||Psi|| < ||Phi||. Using these tools, we analyze the complexity of the class of countable models of four complete, first-order theories T for which (Mod(T),iso) is properly analytic, yet admit very different behavior. We prove that both `Binary splitting, refining equivalence relations' and Koerwien's example of an eni-depth 2, omega-stable theory have (Mod(T),iso) non-Borel, yet neither is Borel complete. We give a slight modification of Koerwien's example that also is omega-stable, eni-depth 2, but is Borel complete. Additionally, we prove that I_{\infty,ω}(Phi)<\beth_{ω_1} whenever (Mod(Phi),iso) is Borel.
Open access
preprint2016arXiv
Definable choice for a class of weakly o-minimal theories
Given an o-minimal structure M with a group operation, we show that for a properly convex subset U, the theory of the expanded structure M′=(M,U) has definable Skolem functions precisely when M′ is valuational. As a corollary, we get an elementary proof that the theory of any such M′ does not satisfy definable choice.
Open access
preprint2015arXiv
Constructing many atomic models in ℵ1
We introduce the notion of pseudo-algebraicity to study atomic models of first order theories (equivalently models of a complete sentence of Lω1,ω. Theorem: Let T be any complete first-order theory in a countable language with an atomic model. If the pseudo-minimal types are not dense, then there are 2ℵ1 pairwise non-isomorphic atomic models of T, each of size ℵ1.
Open access
preprint2014arXiv
Borel completeness of some aleph_0 stable theories
We study aleph_0-stable theories, and prove that if T either has eni-DOP or is eni-deep, then its class of countable models is Borel complete. We introduce the notion of lambda-Borel completeness and prove that such theories are lambda-Borel complete. Using this, we conclude that an aleph_0-stable theory has 2^lambda pairwise non-L(infinity,aleph_0) equivalent models of size lambda for all infinite cardinals lambda if and only if T either has eni-DOP or is eni-deep.
Open access
preprint2014arXiv
P-NDOP and P-decompositions of aleph_epsilon-saturated models of superstable theories
Assume a complete superstable theory is superstable, and let P be a class of regular types, typically closed under automorphisms of the monster and non-orthogonality. We define the notion of P-NDOP and prove the existence of P-decompositions and derive an analog of Sh401 for superstable theories with P-NDOP. In this context, we also find a sufficient condition on P-decompositions that imply non-isomorphic models. For this, we investigate natural structures on the types in P\intersect S(M) modulo non-orthogonality.
Open access
preprint2013arXiv
Characterizing model completeness among mutually algebraic structures
We characterize when the elementary diagram of a mutually algebraic structure has a model complete theory, and give an explicit description of a set of existential formulas to which every formula is equivalent. This characterization yields a new, more constructive proof that the elementary diagram of any model of a strongly minimal, trivial theory is model complete.
Open access
preprint2013arXiv
Model companion of ordered theories with an automorphism
Kikyo and Shelah showed that if T is a theory with the Strict Order Property in some first-order language L, then in the expanded language Lσ:=L∪{σ} with a new unary function symbol σ, the bigger theory $T_σ:= T\cup\{``σ\mbox{is an} \mathcal{L}\mbox{-automorphism''}\}$ does not have a model companion. We show in this paper that if, however, we restrict the automorphism and consider the theory Tσ as the base theory T together with a ``restricted'' class of automorphisms, then Tσ can have a model companion in Lσ. We show this in the context of linear orders and ordered abelian groups.
Open access
preprint2012arXiv
Mutually algebraic structures and expansions by predicates
We introduce the notions of a mutually algebraic structures and theories and prove many equivalents. A theory T is mutually algebraic if and only if it is weakly minimal and trivial if and only if no model M of T has an expansion (M,A) by a unary predicate with the finite cover property. We show that every structure has a maximal mutually algebraic reduct, and give a strong structure theorem for the class of elementary extensions of a fixed mutually algebraic structure.
Open access
preprint2012arXiv
The Schroder-Bernstein property for a-saturated models
A first-order theory T has the Schröder-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.
Open access
preprint2011arXiv
On VC-minimal theories and variants
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.
Open access
preprint2000arXiv
The uncountable spectra of countable theories
Let T be a complete, first-order theory in a finite or countable language having infinite models. Let I(T,kappa) be the number of isomorphism types of models of T of cardinality κ. We denote by μ(respectively \hatμ) the number of cardinals (respectively infinite cardinals) less than or equal to κ. We prove that I(T,κ), as a function of κ> \aleph_0, is the minimum of 2^κ and one of the following functions: 1. 2^κ; 2. the constant function 1; 3. |\hatμ^n/{\sim_G}|-|(\hatμ- 1)^n/{\sim_G}| if \hatμ<ωfor some 1<n<ωand \hatμif \hatμ>= ωsome group G <= Sym(n); 4. the constant function \beth_2; 5. \beth_{d+1}(μ) for some infinite, countable ordinal d; 6. \sum_{i=1}^d Γ(i) where d is an integer greater than 0 (the depth of T) and Γ(i) is either \beth_{d-i-1}(μ^{\hatμ}) or \beth_{d-i}(μ^{σ(i)} + α(i)), where σ(i) is either 1, \aleph_0 or \beth_1, and α(i) is 0 or \beth_2; the first possibility for Γ(i) can occur only when d-i > 0.
Open access
preprint1993arXiv
Forcing isomorphism
A forcing extension may create new isomorphisms between two models of a first order theory. Certain model theoretic constraints on the theory and other constraints on the forcing can prevent this pathology. A countable first order theory is classifiable if it is superstable and does not have either the dimensional order property or the omitting types order property. Shelah [Sh:c] showed that if a theory T is classifiable then each model of cardinality lambda is described by a sentence of L_{infty, lambda}. In fact this sentence can be chosen in the L^*_{lambda}. (L^*_{lambda} is the result of enriching the language L_{infty, beth^+} by adding for each mu < lambda a quantifier saying the dimension of a dependence structure is greater than mu .) The truth of such sentences will be preserved by any forcing that does not collapse cardinals <= lambda and that adds no new countable subsets of lambda. Hence, if two models of a classifiable theory of power lambda are non-isomorphic, they are non-isomorphic after a lambda-complete forcing. Here we show that the hypothesis of the forcing adding no new countable subsets of lambda cannot be eliminated. In particular, we show that non-isomorphism of models of a classifiable theory need not be preserved by ccc forcings.
Open access
Research graph
See the researcher in context
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
Building this map preview
BZPEER is loading the nearby papers, people, topics and institutions for this page.