WorksMathematics
Non-aware computable presentations of randomizations
Abstract
Let 2 be the two-element structure in the empty signature. We build a computable presentation Q of the Borel randomization in which neither constant random variable is a computable point. Consequently, Q is not aware. This gives a negative answer to a question of Cuervo Ovalle and Goldbring \cite{CG}. We also construct a countable structure with no computable presentation but has a computable presentation. This answers another question and establishes the necessity of the awareness condition stated in one of the main theorems in \cite{CG}.
Introduction
Cuervo Ovalle and Goldbring [2] initiate the effective metric structure theory of Keisler randomizations [5].
Informally, a Keisler randomization replaces the elements of a first-order structure by random variables taking values in that structure over a common atomless probability space. A first-order formula applied to these random variables determines the event on which it holds, whose probability measures how often it is satisfied. The randomization records both the random variables and these events, together with their probabilities. Two random variables are close when they agree with high probability, and those that agree almost surely are identified. For the Borel randomizations considered here, the underlying probability space is the unit interval with Lebesgue measure. Each element of the original structure is represented by the corresponding constant random variable, giving a natural copy of the original structure inside its randomization.
Effective metric structure theory studies how metric structures can be described and analyzed algorithmically. In a computable presentation, a countable family of points generates a dense subset on which distances and basic predicates can be evaluated algorithmically to any prescribed accuracy. For randomizations, a natural question is whether such a presentation also provides effective access to the original structure through its constant random variables.
For a countable structure , Cuervo Ovalle and Goldbring [2] call a presentation of its Borel randomization aware when the embedded copy of , viewed as the set of constant random variables, is a c.e. closed subset relative to the presentation. One of their main results relates this condition to the decidable presentability of the original structure.
Theorem 1.1 ([2 Theorem 3.5]). A countable structure has a decidable presentation if and only if has an aware computable presentation.
2020 Mathematics Subject Classification. Primary 03D45; Secondary 03C57, 03C66.
Key words and phrases. Computable presentations, randomizations, awareness, PAC trees.
Intuitively, awareness means that a computable presentation keeps effective track of the original elements of inside the space of random variables. Although its special points may be nonconstant, a single algorithm can use them to approximate each member of a list consisting of all constant random variables, to any prescribed accuracy; this is the equivalent criterion in [2 Proposition 2.6]. This explains the role of awareness in Theorem 1.1: a formula evaluated at constant random variables gives an event of probability either 0 or 1, according to its truth in . Effective access to the constants therefore allows the truth of formulas in to be recovered from the computable data of the randomization.
Their first question about the additional effectiveness condition for awareness is as follows.
Question 1.2 ([2 Question 2.11]). For a countable structure , are all computable presentations of aware?
The first purpose of this paper is to answer this question negatively. The point is that awareness is defined relative to an externally distinguished subset of the randomization, namely the constant random variables, and this subset need not be preserved by an automorphism of the randomization.
For the two-element structure in the empty signature, one may interchange the two values independently at each sample point. If is a Borel event, interchanging the values precisely on gives an automorphism of the randomization. We construct a c.e. open event such that the images of the two constant random variables under are not computable in the standard presentation. We then transport the standard presentation along . Although the transported presentation has the same computable atomic data as the standard one, the fixed external set of constant random variables is no longer computably accessible.
Theorem 1.3. Let be the empty signature and let be the -structure with universe . The Borel randomization has a computable presentation that is not aware. More precisely, there are computably isomorphic computable presentations and of such that is the standard induced presentation, is not aware, and neither nor is a -computable point.
We also give a second automorphism construction for the countably infinite pure set. There every constant remains individually computable, although the constants cannot be enumerated uniformly as a computable sequence. These two examples show that awareness, relative to the fixed set of constant random variables, is not preserved under computable isomorphisms between presentations, even when the underlying maps are automorphisms of the randomization.
There is a second, logically distinct question which is related to Theorem 1.1.
Question 1.4 ([2 Question 3.6]). Can one drop the “awareness” assumption in Theorem 1.1?
In the final section we give a construction, based on a computable tree all of whose paths are computable, which yields the following stronger separation.
Theorem 1.5. There are a computable unary language and a countable -structure such that:
(i) is decidable and has effective quantifier elimination;
(ii) has no computable presentation, and hence no decidable presentation;
(iii) has a computable presentation. Consequently, the answer to Question 1.4 is negative.
The mechanism behind Theorem 1.5 is measure-theoretic rather than automorphic. A noncomputable point of the probability space can be used to produce, pointwise, a listing that cannot be produced computably. The computable points form a null set, so modifying the random variables there makes them everywhere well-defined without changing any event in the probability algebra. Effective quantifier elimination then turns the resulting almost-everywhere listing into a computable dense presentation of the randomization.
We use standard notation from continuous logic, see [1]. For effective metric structure theory and basic concepts in computability, see [3].
The paper is organized as follows. In § 2 we recall the presentation conventions for randomizations. In § 3 we prove Theorem 1.3 by a direct diagonalization and an automorphic change of presentation. The countably infinite pure-set variant is given in § 4. Finally, § 5 proves Theorem 1.5.
Preliminaries
We recall the definitions needed for the construction. Our terminology and presentation conventions follow [2 Section 2].
Fix a countable first-order language and a countable -structure . The Borel randomization is a two-sorted continuous structure.
Definition 2.1. The random-variable sort of the randomization pre-structure consists of the Borel measurable functions , where carries the discrete sigma-algebra. The event sort is the probability algebra of , where is Lebesgue measure. For each -formula , the randomization language has a function symbol
interpreted by
where the set on the right is identified with its equivalence class modulo null sets. The pseudometrics are
One then passes to the metric quotients and completions. We continue to write , , and for the completed structure and its two sorts.
Each is identified with the corresponding constant random variable . Thus is viewed as a subset of . Distinct constant random variables have distance 1, so this embedded copy of is a closed discrete subset of .
When and is Borel, let
Changing on a null set does not change the corresponding point of , so we also write when denotes an event in the probability algebra.
Definition 2.2. Let be a separable metric structure. A presentation is a countable sequence of special points whose closure under the function symbols is dense in . Points obtained from the special points by applying the function symbols are called generated points. In the many-sorted setting, one specifies such a sequence in each sort.
There are no function symbols with codomain in the randomization language. Consequently, in the -sort, the special points and generated points coincide.
Definition 2.3. A presentation in a computable signature is computable if there is an algorithm which, given an -ary predicate symbol , a tuple of generated points, and a positive rational , returns a rational such that
In particular, the metric on generated points is uniformly computable.
Definition 2.4. Let be a presentation of .
A point is -computable if there is an algorithm which, given a positive rational , returns a generated point such that .
A sequence is an -computable sequence if the approximation algorithm in item (1) is uniform in .
If and are presentations and is an embedding, then is a computable map from to if, given a generated point of and a positive rational , one can compute a generated point of with . A bijective is a computable isomorphism if both and are computable maps.
Fix an effective enumeration of the -special points of a computable presentation .
Definition 2.5. A partial computable function is a fast name for if is total and
Lemma 2.6. A point is -computable if and only if it has a fast name.
Proof. A fast name directly gives the approximations required in Definition 2.4. Conversely, if is -computable, apply its approximation procedure with error and return the index of the resulting -generated point. Since generated and special points coincide in , this gives a total computable fast name.
Definition 2.7. Let be a presentation of . A closed set is c.e. closed in if the set of rational open balls
where is generated and is rational, that intersect is computably enumerable.
Definition 2.8. A presentation of is aware if the embedded set of constant random variables
is c.e. closed in that presentation.
Proposition 2.9 ([2 Proposition 2.6]). Let be a computable presentation of . Then is aware if and only if there is an enumeration of all constant random variables that is an -computable sequence.
Let be the two-element structure in the empty signature. Its standard presentation is decidable. Let
be the induced presentation from [2 Section 2.3]. Its K-special points are binary-valued simple functions whose level sets belong to the Boolean algebra generated by rational intervals, and its B-special points form the standard presentation of the probability algebra. In particular, and occur effectively among the K-special points.
Lemma 2.10. The presentation is computable and aware. Moreover, uniformly in a K-special point , a rational interval , and a positive rational , one can compute a rational such that
Proof. Computability is a special case of the fact that the induced randomization of a decidable presentation is computable [2 Corollary 3.4]. It can also be seen directly. Given finitely many binary simple functions, refine their finite rational partitions to a common finite partition. On each cell, every input has a fixed value in , and the truth of any formula of the empty signature in the finite structure is decidable. Hence every atomic event of the randomization is a finite Boolean combination of rational intervals with computable measure. The same argument, applied to , gives the asserted uniform computation.
For awareness, let be a binary simple function and let be rational. Since
the ball meets if and only if
Both measures are computable, and a strict inequality between a computable real and a rational is c.e. Thus the rational open balls meeting the constants can be enumerated.
The proof of Theorem 1.3
We first construct a c.e. open event such that neither nor is a -computable point.
Fix an effective enumeration of all partial computable functions from to . The requirement is
For , let
These are pairwise disjoint rational intervals. Assign to the two private intervals
and set
Effectively choose so large that, with ,
Construction 3.1. At stage , for every that has not yet acted, simulate for steps. If
use Lemma 2.10 to compute rationals such that
Then make the following permanent decisions.
On , define to have the value opposite to the approximate majority value of :
On , define to have the same value as the approximate majority value of :
Finally, declare that has acted. Whenever an interval is to be included in , enumerate that interval at this stage. If never acts, neither of its private intervals is included in .
Since each private interval is controlled by a unique requirement, the decisions are compatible. The resulting set is a c.e. union of rational open intervals and hence is a c.e. open, in particular Borel, subset of .
Proposition 3.2. For the event constructed above, neither nor is a -computable point.
Proof. Fix and suppose that is a fast name for some . Then converges, so acts. Write
and, for , set
Because is a fast name,
For binary-valued random variables, the map is 1-Lipschitz from to . Consequently,
Combining this with Equation (2), we obtain
We first diagonalize against on . If , then by Equation (3), and hence
If , then , and hence
The final inequalities in both cases use Equation (1). Therefore
On , the definition of makes have the value opposite to the approximate majority value of . If , then , so
If , then , so
Consequently,
This verifies .
By Lemma 2.6, every -computable point has a fast name for some . Equations (6) and (7) therefore show that neither nor is -computable. □
Remark 3.3. For the counterexample alone, it would suffice to choose a Borel event for which is not -computable. Indeed, the global interchange of 0 and 1 is a computable automorphism of the standard presentation and sends to , so one of these points is computable exactly when the other is. The construction above is retained because it gives a direct diagonalization against all computable random variables and makes both noncomputability statements explicit.
Let be the nontrivial automorphism of , so that and . For , define
For a Borel random variable in the randomization pre-structure, set
and let act as the identity on .
Lemma 3.4. The map descends to an involutive automorphism of . For every -formula and every ,
Furthermore,
Proof. Since is Borel, is Borel whenever is Borel. For every , the map is an automorphism of the empty-signature structure . Hence, for Borel random variables and pointwise in ,
if and only if
This proves Equation (9) on the pre-structure. It also gives
so preserves the K-pseudometric. It is the identity on , preserves every distinguished formula-event function, and satisfies . It therefore descends to the metric quotient and extends uniquely to an involutive automorphism of the completion. Equality (9) on the completion follows by continuity. Finally, Equation (10) is immediate from the definition. □
Let be the -special points of , and let be its -special points. Define a new presentation by taking
as its -special points and retaining as its -special points. Since is an automorphism, is dense in , so is a presentation of the same randomization.
Lemma 3.5. The presentation is computable. Moreover, is a computable isomorphism.
Proof. For all ,
For every -formula and every tuple of indices , Equation (9) gives
The -special points are unchanged, and is the identity on . By induction on terms, every generated -term in denotes the same event as the term with the same syntactic code in . Thus there is an effective code-preserving translation from generated points of to generated points of under which all metric and predicate values agree. The algorithms computing the atomic data of therefore compute the atomic data of .
On the , sends the special point to the special point with the same index and error . On the , it sends every generated term to the term with the same syntactic code. Hence is a computable map from to . Since is an involution, the same index-preserving procedures compute its inverse. Therefore is a computable isomorphism. □
Remark 3.6. The event is deliberately noncomputable as a point of the standard presentation, but this does not prevent from being a legitimate computable presentation. A presentation is an indexed dense family of actual elements of the metric structure; its special points are not required to be computable in a previously fixed presentation. Computability is determined by the metric and predicate values on the newly indexed generated points, and those values are computable here because preserves them exactly. The map is computable from to , but not from to itself: it sends the -computable point to the noncomputable point .
Proof. The presentation is computable by Lemma 3.5. Suppose, toward a contradiction, that is aware. By Proposition 2.9, there is a -computable sequence whose range is exactly . Since is a computable isometry, the sequence
is -computable, and its range is by Equation (10). In particular, is a -computable point belonging to , contrary to Proposition 3.2. Hence is not aware.
Finally, if were a -computable point, then applying the computable inverse would make a -computable point. Similarly, computability of in would imply computability of in . Thus neither constant is -computable. □
Corollary 3.7. Awareness, relative to the fixed embedded copy of the original structure, is not preserved under computable isomorphisms between presentations of the same randomization.
Proof. The standard presentation is aware by Lemma 2.10, while is not aware, and Lemma 3.5 gives a computable isomorphism whose underlying map is an automorphism of the randomization. □
A second construction: the infinite pure set
The preceding construction has the stronger feature that neither constant random variable is computable in the new presentation. We now give a shorter counterexample using a different underlying structure. In this example every constant remains individually computable, but the constants cannot be enumerated uniformly as a computable sequence.
Let be the structure with universe in the empty signature. Thus every permutation of is an automorphism of .
Lemma 4.1. There is an involution such that its fixed-point set
is not c.e.
Proof. Fix a c.e. noncomputable set . On each pair , let interchange the two elements if and fix both elements if . Explicitly,
Then and
If were c.e., then would be c.e. Since is c.e., this would make computable, a contradiction. □
Put
For a Borel random variable , define
and let act as the identity on .
Lemma 4.2. The map descends to an involutive automorphism of . Moreover, for every formula in the empty signature and all ,
Proof. The function is Borel because has the discrete sigma-algebra. At each , the fiber map used in Equation (11) is either or , hence an automorphism of . Formula satisfaction is therefore preserved pointwise, which gives Equation (12). Applying this to equality shows that preserves the -pseudometric. It is the identity on and satisfies , so it descends to the metric quotient and extends uniquely to an involutive automorphism of the completion.
Let
be the standard induced presentation. The standard presentation of is decidable, so is computable by [2 Corollary 3.4]. Let be its -special points and its -special points. Since the induced presentation effectively lists all rational simple random variables, there is a computable function such that
Define a presentation by taking
as its -special points and retaining as its -special points.
Lemma 4.3. The presentation is computable, and is a computable isomorphism.
Proof. By Lemma 4.2, is dense in . Equation (12) shows that every formula-event evaluated on a tuple of the is exactly the same event as the corresponding formula-event evaluated on the tuple of the . The -special points are unchanged. Consequently, generated points with the same syntactic codes in and have the same metric and predicate values. The algorithms for therefore compute the atomic data of .
The map sends each to with the same index and fixes the . Hence the same-code map computes . Since is an involution, the same procedure computes its inverse.
Theorem 4.4. The computable presentation of is not aware. Nevertheless, every constant random variable is a -computable point.
Proof. For each , consider the rational open ball
Then is an effective sequence of rational open balls in . If , then , so and meets the constant random variables. Suppose that . Then equals on and on . Hence, for every ,
Thus is disjoint from the constant random variables. We have proved
If were aware, then by Definitions 2.7 and 2.8 the rational open balls meeting would form a c.e. set. Applying this enumeration to the effective sequence and using Equation (13) would make c.e., contradicting Lemma 4.1. Therefore is not aware.
It remains to verify the final assertion. For a fixed , the random variable
is a rational simple random variable and hence occurs among the K-special points of . Since is an involution, . Therefore occurs among the K-special points of and is -computable. For each fixed , the two natural numbers and can be built into a code for ; this argument does not give a uniform procedure for obtaining such a code from .
In fact, there is no uniform procedure producing names for these constants: otherwise would be a -computable enumeration of all constants, contrary to Proposition 2.9 and the first part of the theorem. □
The proof of Theorem 1.5
For convenience we work first over the fair-coin probability space . Binary expansion induces a computable isomorphism between its probability algebra and the standard probability algebra on , modulo the null set of ambiguous binary expansions.
Definition 5.1 (Hirschfeldt [4]). (1) A tree is a PAC tree if it is computable, has no dead ends, and every path through is computable.
(2) If , a computable listing of is a uniformly computable sequence of elements of whose range is ; repetitions are allowed.
(3) For a PAC tree , let be the set of isolated paths through .
Theorem 5.2 (Goncharov–Nurtazin; Millar; see Hirschfeldt [4, Theorem 1.9]). There is a PAC tree such that has no computable listing.
The next consequence of the PAC property will be used twice. Its proof uses the path-selection argument from [4 Theorem 2.1].
Lemma 5.3. Let be a PAC tree. Then is dense in .
Proof. Fix a noncomputable and a node . Starting at , follow the unique immediate successor whenever there is only one. At the th node having two immediate successors, take the successor selected by . This defines a path extending .
If infinitely many splitting nodes occurred along , then would be computable from : since is computable, one can locate the successive splitting nodes along and read the choices made there. But every path through a PAC tree is computable, contradicting the choice of . Hence only finitely many splits occur along . Beyond the last split, has a unique continuation in , so is isolated.
Fix a tree as in Theorem 5.2. Let
be a computable language of unary predicates, and define the -structure
and for all and ,
is countable since is countable. Equation (14) ensures that each path type is realized infinitely often.
For , let
Lemma 5.4. For every ,
Whenever is nonempty, it is infinite.
Proof. If , then , so . Conversely, if , then Lemma 5.3 gives extending . Every , for , then satisfies .
Proposition 5.5. The theory is decidable and has effective quantifier elimination.
Proof. A theory has quantifier elimination if every formula is equivalent, in all models of the theory, to a quantifier-free formula with no additional free variables; see [6 Definition 3.1.1]. We use the standard quantifier-elimination argument for a unary structure in which every nonempty finite Boolean cell is infinite. To eliminate from a quantifier-free formula, first put the formula into disjunctive normal form. In any conjunct in which is required to equal another variable, substitute that variable for . Otherwise, is required to avoid only finitely many other variables and to satisfy a finite Boolean pattern in the predicates .
Choose larger than every predicate index appearing in the formula and consider the finitely many strings extending this partial pattern. By Lemma 5.4, the pattern is realizable if and only if at least one such belongs to ; whenever it is realizable, it has infinitely many realizations and hence one outside the finite prohibited set. Membership in is decidable, so this elimination step is effective. Iteration gives effective quantifier elimination. In particular, sentences can be reduced effectively to quantifier-free sentences and decided.
Proposition 5.6. The structure has no computable presentation.
Proof. Suppose that were a computable presentation of . For each , define by
The computable atomic diagram makes a uniformly computable sequence. Every lies in , and every occurs because the presentation contains an element corresponding to . Thus is a computable listing of , contrary to Theorem 5.2.
Using the same path-selection procedure, we next construct an almost-everywhere enumeration of on the probability space . Let be an effective enumeration of the nodes of in which every node occurs infinitely often. Given , let be the path obtained by starting at , following the unique successor at a nonsplitting node, and using the bits of in order to choose successors at splitting nodes.
Lemma 5.7. If is noncomputable, then for every , and every member of occurs infinitely often in .
Proof. The proof of Lemma 5.3, applied above , shows that is isolated: if it passed through infinitely many splitting nodes, then the choices along the computable path would compute .
If , choose a node whose unique extension in is . Every guided path starting at equals . Since occurs infinitely often among the , the path occurs infinitely often among the .
For and , define the occurrence rank
Let be the set of computable reals. This set is countable and hence Borel and null. Fix any and define
Lemma 5.8. Each is a Borel -valued random variable. For every , the map is a bijection from onto .
Proof. The map is continuous: a finite initial segment of its output is determined by a finite initial segment of . It follows that and , for fixed , are closed. Thus is Borel, and every fiber of the function in (15) is Borel. Since is countable and discrete, this proves that is Borel measurable.
For noncomputable , Lemma 5.7 says that every appears infinitely often among the . Its successive occurrences have ranks . Hence every pair appears exactly once among the .
The modification on makes every genuinely -valued at every point; no effective recognition of will be needed. For , put
The set is effectively clopen, uniformly in and . Indeed, to determine , one extends by at most bits and uses at most one bit of per extension. All immediate-successor questions in are decidable. Simulating this finite computation on every binary word of that length therefore produces a finite union of basic cylinders coding . In the probability algebra we have
The first equality ignores only the null set Comp. For the second, the definition on Comp also keeps the pairwise distinct there. Thus equality events are computed by comparing indices; no computation of the occurrence ranks is required.
Let be the effective Boolean algebra of clopen subsets of , represented by finite unions of basic cylinders. Let be the countable family of all finite clopen pastings of the : its members have the form
where is a finite partition of by members of and . The family has an effective enumeration by the finite codes for these partitions and indices.
Lemma 5.9. The family is dense in the K-sort of the Borel randomization of over .
Proof. Let be a Borel random variable. Outside Comp, the sequence enumerates without repetition. Define pairwise disjoint Borel sets
Their union contains .
Given , choose such that . Finite measurable partitions can be approximated in measure by clopen partitions, so there is a clopen partition such that
Let equal on for and equal on . Then
and hence . Thus is dense. This argument only establishes density; an effective choice of or of the approximating clopen partition is not needed. □
Proposition 5.10. Taking as the special points of the K-sort and as the special points of the B-sort yields a computable presentation of the Borel randomization of over .
Proof. We show uniformly how to compute all formula events on tuples from . Given an -formula , use Proposition 5.5 to compute a quantifier-free formula equivalent to in . Given a tuple of clopen pastings, refine the finitely many partitions defining its components to a common clopen partition. On each cell, every component is equal to some .
An equality between two such components is decided by comparing their indices, using (17). An atomic predicate is represented by the uniformly effective clopen set , using (16). Performing the Boolean operations in therefore produces effectively a clopen set satisfying
in the probability algebra.
The measure of a clopen subset of is a computable dyadic rational. Consequently, all formula-event function symbols and their measures are computable on the named points. In particular,
is computable for . Boolean operations, measure, and are computable on clopen event codes, and every event generated from the named points again has an effective clopen code. Finally, Lemma 5.9 gives density in the -sort, while the clopens are dense in the probability algebra. Thus the two families satisfy Definition 2.3. □
Proof of Theorem 1.5. By Proposition 5.5, the theory of is decidable and has effective quantifier elimination. By Proposition 5.6, has no computable, and hence no decidable, presentation. By Proposition 5.10 and the computable identification of the fair-coin probability algebra with the standard probability algebra on , the randomization has a computable presentation. □
acknowledgments
The author was supported by Focused Research Grants of Natural Science Foundation of Jiangsu Province No. BK20243060. The author used OpenAI’s ChatGPT 5.6, to assist with developing the proofs. All proofs in this paper have been independently verified by the author without the use of AI tools. The author takes full responsibility for the mathematical correctness, attribution of ideas, and final content of the paper.
References
School of Mathematics, Nanjing University, Nanjing, Jiangsu 210093, People’s Republic of China
Email address: [email protected]
References
- [1]I. Ben-Yaacov, A. Berenstein, C. W. Henson and A. Usvyatsov, Model theory for metric structures, in Model theory with applications to algebra and analysis, Vol. 2, 315–427, London Math. Soc. Lecture Note Ser., 350, Cambridge Univ. Press, Cambridge, 2008.DOI
- [2]N. Cuervo Ovalle and I. Goldbring, Computable presentations of randomizations, The Journal of Symbolic Logic (2026), 1–21. doi:10.1017/jsl.2026.10233.DOI
- [3]J. N. Y. Franklin, I. Goldbring and T. H. McNicholl, Effective metric structure theory, Springer Monographs in Mathematics, Springer, Cham, 2026.DOI
- [4]D. R. Hirschfeldt, Computable trees, prime models, and relative decidability, Proceedings of the American Mathematical Society 134 (2006), 1495–1498. doi:10.1090/S0002-9939-05-08097-4.DOI
- [5]H. J. Keisler, Randomizing a model, Adv. Math. 143 (1999), no. 1, 124–158.DOI
- [6]D. Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. doi:10.1007/b98860.DOI