More Like this

1. Model theory and agnostic online learning via excellent sets

   https://doi.org/10.1090/tran/9235  

   Malliaris, M; Moran, S (November 2024, Transactions of the American Mathematical Society)

   We use algorithmic methods from online learning to explore some important objects at the intersection of model theory and combinatorics, and find natural ways that algorithmic methods can detect and explain (and improve our understanding of) stable structure in the sense of model theory. The main theorem deals with existence of $\mathrm{ϵ<\#comment/>}$-excellent sets (which are key to the Stable Regularity Lemma, a theorem characterizing the appearance of irregular pairs in Szemerédi’s celebrated Regularity Lemma). We prove that $\mathrm{ϵ<\#comment/>}$-excellent sets exist for any $\mathrm{ϵ<\#comment/>}>\frac{1}{2}$in $k$-edge stable graphs in the sense of model theory (equivalently, Littlestone classes); earlier proofs had given this only for $\mathrm{ϵ<\#comment/>}>1/2^{2^k}$or so. We give two proofs: the first uses regret bounds from online learning, the second uses Boolean closure properties of Littlestone classes and sampling. We also give a version of the dynamic Sauer-Shelah-Perles lemma appropriate to this setting, related to definability of types. We conclude by characterizing stable/Littlestone classes as those supporting a certain abstract notion of majority: the proof shows that the two distinct, natural notions of majority, arising from measure and from dimension, densely often coincide. 

   more » « less
2. Abraham–Rubin–Shelah open colorings and a large continuum

   https://doi.org/10.1142/s0219061321500276  

   Gilton, Thomas; Neeman, Itay (April 2022, Journal of Mathematical Logic)

   We show that the Abraham–Rubin–Shelah Open Coloring Axiom is consistent with a large continuum, in particular, consistent with [Formula: see text]. This answers one of the main open questions from [U. Abraham, M. Rubin and S. Shelah, On the consistency of some partition theorems for continuous colorings, and the structure of [Formula: see text]-dense real order types, Ann. Pure Appl. Logic 325(29) (1985) 123–206]. As in [U. Abraham, M. Rubin and S. Shelah, On the consistency of some partition theorems for continuous colorings, and the structure of [Formula: see text]-dense real order types, Ann. Pure Appl. Logic 325(29) (1985) 123–206], we need to construct names for the so-called preassignments of colors in order to add the necessary homogeneous sets. However, the known constructions of preassignments (ours in particular) only work assuming the [Formula: see text]. In order to address this difficulty, we show how to construct such names with very strong symmetry conditions. This symmetry allows us to combine them in many different ways, using a new type of poset called a partition product. Partition products may be thought of as a restricted memory iteration with stringent isomorphism and coherent-overlap conditions on the memories. We finally construct, in [Formula: see text], the partition product which gives us a model of [Formula: see text] in which [Formula: see text]. 

   more » « less
3. TRANSITIVITY, LOWNESS, AND RANKS IN NSOP THEORIES

   https://doi.org/10.1017/jsl.2023.36  

   CHERNIKOV, ARTEM; KIM, BYUNGHAN; RAMSEY, NICHOLAS (June 2023, The Journal of Symbolic Logic)

   Abstract We develop the theory of Kim-independence in the context of NSOP $$_{1}$$ theories satisfying the existence axiom. We show that, in such theories, Kim-independence is transitive and that -Morley sequences witness Kim-dividing. As applications, we show that, under the assumption of existence, in a low NSOP $$_{1}$$ theory, Shelah strong types and Lascar strong types coincide and, additionally, we introduce a notion of rank for NSOP $$_{1}$$ theories. 

   more » « less
4. Continuous stable regularity

   https://doi.org/10.1112/jlms.12822  

   Chavarria, Nicolas; Conant, Gabriel; Pillay, Anand (October 2023, Journal of the London Mathematical Society)

   Abstract We prove an analytic version of the stable graph regularity lemma by Malliaris and Shelah (Trans. Amer. Math. Soc.366(2014), no. 3, 1551–1585), which applies to stable functions . Our methods involve continuous model theory and, in particular, results on the structure of local Keisler measures for stable continuous formulas. Along the way, we develop some basic tools around ultraproducts of metric structures and linear functionals on continuous formulas, and we also describe several concrete families of examples of stable functions. 

   more » « less
5. COFINALITY QUANTIFIERS IN ABSTRACT ELEMENTARY CLASSES AND BEYOND

   https://doi.org/10.1017/jsl.2023.34  

   BONEY, WILL (May 2023, The Journal of Symbolic Logic)

   The cofinality quantifiers were introduced by Shelah as an example of a compact logic stronger than first-order logic. We show that the classes of models axiomatized by these quantifiers can be turned into an Abstract Elementary Class by restricting to positive and deliberate uses. Rather than using an ad hoc proof, we give a general framework of abstract Skolemizations. This method gives a uniform proof that a wide range of classes are Abstract Elementary Classes. 

   more » « less