Simple Models of Randomization and Preservation Theorems

arXiv:2408.15014 · math.LO, math.CO · Submitted 2024-08-27 · Read on arXiv

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

Related papers