Computable presentations of randomizations
Nicolás Cuervo Ovalle and Isaac Goldbring · 2025
Read Computable presentations of randomizations by Nicolás Cuervo Ovalle and Isaac Goldbring (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-06187.txt.
Introduction
Nicolás Cuervo Ovalle and Isaac Goldbring ask when a randomized structure can be pinned down by a program, in a 2025 paper. A randomization, in Keisler's sense, rebuilds a plain structure so that its elements act like random quantities. The pair opens the study of which of these rebuilt worlds a computer can describe.
They prove that a plain structure can be listed by an algorithm exactly when its rebuilt twin can, so long as the constant elements behave well. When the base structure falls in a tame class, the rebuilt form is the only one of its kind up to computable match. All such worlds also admit a clean way to drop quantifiers. Chance, logic, and computing end up in one frame.
Catalog record
| CREATOR | Nicolás Cuervo Ovalle and Isaac Goldbring |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 66 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-06187
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Computable presentations of randomizations Thanks: The first named author was partially supported by NSF grant DMS-2054477. He would also like to thank the UC Irvine Department of Mathematics for their hospitality. Thanks: The second-named author was partially supported by NSF grant DMS-2054477. Nicolás Cuervo Ovalle and Isaac Goldbring Abstract . We initiate the effective metric structure theory of Keisler randomizations. We show that a classical countable structure ℳ \mathcal{M} has a decidable presentation if and only if its Borel randomization ℳ [ 0 , 1 ) \mathcal{M}^{[0,1)} has a computable presentation for which the constant functions are uniformly computable points. We determine a sufficient condition for which the uniform computability of the constant functions can be dropped. We show that when ℳ \mathcal{M} is effectively ω \omega -categorical, then ℳ [ 0 , 1 ) \mathcal{M}^{[0,1)} is computably categorical, that is, has a unique computable presentation up to computable isomorphism. A special case of this result is that the unique separable atomless probability algebra is computably categorical. Finally, we show that all randomizations admit effective quantifier elimination. 1. Introduction In [ 9 ] , Keisler introduced the notion of randomizing a (classical) structure \mathcal{M} , which is a structure whose elements are viewed as \mathcal{M} -valued random variables. Keisler’s initial construction was presented in classical logic; the construction was later transported by Ben Yaacov and Keisler [ 4 ] into the context of continuous logic. In [ 1 ] , Ben Yaacov showed how to further generalize the construction to allow for randomizations of continuous theories as well. Randomizations are known to preserve many important model-theoretic phenomena, such as countable categoricity, stability (but not simplicity), \omega -stability, NIP, etc… (see [ 2 ] for the last statement). In this article, we investigate to what extent the randomization construction interacts nicely with ideas from computable structure theory . More precisely, we investigate the question as to whether or not there is a connection between a (countable, classical) structure \mathcal{M} having a computable presentation and its Borel randomization \mathcal{M}^{[0,1)} having a computable presentation. We now roughly define the italicized terms in the previous sentence; precise definitions will be given in the next section. Given a countable (classical) structure \mathcal{M} , a presentation of \mathcal{M} is a function \nu:\mathbb{N}\to\mathcal{M} , which we think of as a labeling of the elements of \mathcal{M} (perhaps with repetitions). The presentation is computable if, roughly speaking, the operations and predicates on \mathcal{M} lift to computable functions and subsets of \mathbb{N} . An analogous definition of presentation can be given to a separable metric structure, with the difference being that the presentation labels a countable set that generates a dense subset of the structure; such points are said to be the special points of the presentation while the points in the pre-substructure that they generate are said to be generated points . To say that this presentation is computable amounts to the fact that (again, roughly speaking) one can compute generated points that approximate operations applied to generated points (and a similar statement for predicates). Given a classical countable structure \mathcal{M} , its Borel randomization \mathcal{M}^{[0,1)} is the set of function f:[0,1)\to\mathcal{M} such that, for each a\in\mathcal{M} , we have that f^{-1}(a) is a Borel subset of [0,1) . We consider the Borel randomization as a structure (technically speaking, pre-structure) in a two-sorted continuous language, with one sort for the \mathcal{M} -valued random variables in the previous sentence and another for the probability algebra of [0,1) ; for each first-order formula \varphi(\vec{x}) with \vec{x}=(x_{1},\ldots,x_{n}) , there is a function symbol \llbracket\varphi(\cdot)\rrbracket which maps a tuple \vec{f} of random variables to the event \llbracket\varphi(\vec{f})\rrbracket:=\{\omega\in[0,1)\ :\ \mathcal{M}\models\varphi(\vec{f}(\omega))\} . The pseudometric on the random variable sorts is given by d(f,g):=\mu\llbracket f\not=g\rrbracket and the pseudometric on the probability algebra is the usual one given by d(A,B):=\mu(A\triangle B) . The completion of this pre-structure is then a metric structure, which we also refer to as \mathcal{M}^{[0,1)} . The naïve guess might be that \mathcal{M} has a computable presentation if and only if \mathcal{M}^{[0,1)} has a computable presentation. 1 1 1 Throughout this introduction, we assume that \mathcal{M} is a structure in a computable language; this assumption will be stated explicitly in the next section as well. However, such a naïve statement presents two issues. First of all, since a computable presentation of \mathcal{M}^{[0,1)} can approximate the measure of the event \llbracket\varphi(\vec{f})\rrbracket , where \varphi(\vec{x}) is any formula (which may have quantifiers), it seems likely that any conclusion drawn about a presentation of \mathcal{M} would show that it is not only computable, but rather decidable , which means that one can effectively determine the truth of any formula with parameters in \mathcal{M} (and not just the quantifier-free ones, whose truth can be verified relative to a computable presentation). Since there are classical structures that admit a computable presentation but no decidable presentation, it seems more sensible to ask if \mathcal{M} has a decidable presentation if and only if \mathcal{M}^{[0,1)} has a computable presentation. Another (but related) reason for changing the question is that any computable presentation of a randomization is automatically decidable. The reason for this is that randomizations have effective quantifier elimination (see Section 5 ), which essentially follows from the atomic formulae in the randomization language having classifical quantifiers embedded in them. Considering the modified question, in one direction, given a decidable presentation of \mathcal{M} , we show how to construct a natural “induced” presentation on \mathcal{M}^{[0,1)} , which we then show is computable. However, in the converse direction, it is not clear to us how to extract a presentation (decidable or otherwise) of \mathcal{M} from an arbitrary presentation of \mathcal{M}^{[0,1)} . That being said, if we somehow have “computable access” to the constant functions in \mathcal{M}^{[0,1)} , then we can indeed recover a decidable presentation of \mathcal{M} . Our main result can thus roughly be stated as follows: Theorem . For any classical, countable structure \mathcal{M} , we have that \mathcal{M} has a decidable presentation if and only if \mathcal{M}^{[0,1)} has a computable presentation for which the constant functions are uniformly computable points. In general, we do not know if the previous theorem is valid without the assumption that the constant functions are uniformly computable points. However, we will present a condition on a structure \mathcal{M} , called being effectively recognizable , for which we can remove this assumption. Corollary . Suppose that \mathcal{M} is an effectively recognizable structure. Then \mathcal{M} has a decidable presentation if and only if \mathcal{M}^{[0,1)} has a computable presentation. For any structure \mathcal{M} , its expansion \mathcal{M}_{M} obtained by naming the elements of \mathcal{M} is automatically effectively recognizable. Since \mathcal{M} has a decidable presentation if and only if \mathcal{M}_{M} has a decidable presentation, we have: Corollary . For any classical, countable structure \mathcal{M} , we have that \mathcal{M} has a decidable presentation if and only if \mathcal{M}_{M}^{[0,1)} has a computable presentation. As mentioned above, the notions of “computable presentation” and “decidable presenation” coincide for \mathcal{M}^{[0,1)} , whence one may obtain more symmetric statements in the previous two results by replacing “computable” by “decidable.” We also consider the question as to when \mathcal{M}^{[0,1)} is computably categorical , that is, when \mathcal{M}^{[0,1)} has a unique computable presentation (up