Simple Models of Randomization and Preservation Theorems
math.LO, math.CO
Submitted: 2024-08-27
Updated: 2026-10-29
Comments: 34 pages. In this version, the section on stability has been completed, and further supplementary explanations have been provided in the NIP section. Comments welcome. k.khanaki @ gmail.com
License: http://creativecommons.org/licenses/by/4.0/
The gist: The main purpose of this paper is to provide new, more uniform model-theoretic and combinatorial proofs of the preservation theorems established in [5] and [8].
Terminology
Abstract
The main purpose of this paper is to provide new, more uniform model-theoretic and combinatorial proofs of the preservation theorems established in [5] and [8]. More precisely, we show that randomization preserves both NIP and stability: if a first-order theory T has NIP, then so does T R, and if T is stable, then so is T R. Our proofs rely on the systematic use of simple models of T R and quantitative combinatorial methods. In the NIP case, we use indiscernible arrays and Rademacher mean width, whereas in the stable case, we use a Ramsey lemma for cross-blocks and sequential Rademacher mean width. Using simple models of T R has the advantage of allowing us to re-prove these theorems in a simpler and quantitative manner. We finally turn our attention to NSOP in randomization. We show that based on the definition of NSOP given in [14], T R is stable if and only if it is NIP and NSOP.
Sources
- Generically Stable Measures and Distal Regularity in Continuous Logic
- Hypergraph regularity and higher arity VC-dimension
- Continuous logic and the strict order property
- On classification of continuous first order theories
Related papers
- The consistency strength of the failure of amenable C-sequences
- Classification of bipartite observables III: simplicity, mixtures and quantum error correction
- Indiscernible Extraction in Theories with Bounded k-splitting
- Measuring the Complexity of Countable Presburger Models
- A non-trivially non-trivial automorphism at an inaccessible cardinal
- The Ordering Principle and Higher Dependent Choice