betaFeedback

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 2[0,1)2^{[0,1)} 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 MM with no computable presentation but M[0,1)M^{[0,1)} 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 MM, Cuervo Ovalle and Goldbring [2] call a presentation of its Borel randomization M[0,1)M^{[0,1)} aware when the embedded copy of MM, 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 MM has a decidable presentation if and only if M[0,1)M^{[0,1)} 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 MM 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 MM. Effective access to the constants therefore allows the truth of formulas in MM 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 MM, are all computable presentations of M[0,1)M^{[0,1)} 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 A⊆[0,1)A \subseteq[0,1) is a Borel event, interchanging the values precisely on AA gives an automorphism TAT_A of the randomization. We construct a c.e. open event AA such that the images of the two constant random variables under TAT_A are not computable in the standard presentation. We then transport the standard presentation along TAT_A. 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 LL be the empty signature and let 2\mathbf{2} be the LL-structure with universe {0,1}\{0,1\}. The Borel randomization 2[0,1)\mathbf{2}^{[0,1)} has a computable presentation that is not aware. More precisely, there are computably isomorphic computable presentations P\mathcal{P} and Q\mathcal{Q} of 2[0,1)\mathbf{2}^{[0,1)} such that P\mathcal{P} is the standard induced presentation, Q\mathcal{Q} is not aware, and neither 0ˉ\bar{0} nor 1ˉ\bar{1} is a Q\mathcal{Q}-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 LTL_T and a countable LTL_T-structure MTM_T such that:

(i) Th⁡(MT)\operatorname{Th}(M_T) is decidable and has effective quantifier elimination;

(ii) MTM_T has no computable presentation, and hence no decidable presentation;

(iii) MT[0,1)M_T^{[0,1)} 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 LL and a countable LL-structure MM. The Borel randomization M[0,1)M^{[0,1)} is a two-sorted continuous structure.

Definition 2.1. The random-variable sort K\mathbb{K} of the randomization pre-structure consists of the Borel measurable functions f:[0,1)→Mf : [0,1) \to M, where MM carries the discrete sigma-algebra. The event sort B\mathbb{B} is the probability algebra of ([0,1),μ)([0,1),\mu), where μ\mu is Lebesgue measure. For each LL-formula φ(x1,…,xn)\varphi(x_1,\ldots,x_n), the randomization language has a function symbol

⟦φ⟧:Kn⟶B\llbracket\varphi\rrbracket: \mathbb{K}^{n} \longrightarrow\mathbb{B}

interpreted by

⟦φ(f1,…,fn)⟧={ω∈[0,1):M⊨φ(f1(ω),…,fn(ω))},\llbracket\varphi(f_1,\ldots,f_n)\rrbracket= \{\omega\in[0,1) : M \models\varphi(f_1(\omega),\ldots,f_n(\omega))\},

where the set on the right is identified with its equivalence class modulo null sets. The pseudometrics are

dK(f,g)=μ⟦f≠g⟧anddB(E,F)=μ(E△F).d_{\mathbb{K}}(f,g) = \mu\llbracket f \ne g\rrbracket\qquad\text{and}\qquad d_{\mathbb{B}}(E,F) = \mu(E \mathbin{\triangle} F).

One then passes to the metric quotients and completions. We continue to write M[0,1)M^{[0,1)}, K\mathbb{K}, and B\mathbb{B} for the completed structure and its two sorts.

Each a∈Ma \in M is identified with the corresponding constant random variable aˉ(ω)=a\bar{a}(\omega)=a. Thus MM is viewed as a subset of K\mathbb{K}. Distinct constant random variables have distance 1, so this embedded copy of MM is a closed discrete subset of K\mathbb{K}.

When M=2M=2 and A⊆[0,1)A\subseteq[0,1) is Borel, let

χA(ω)={1,ω∈A,0,ω∉A.\chi_A(\omega)= \begin{cases} 1, & \omega\in A,\\ 0, & \omega\notin A. \end{cases}

Changing AA on a null set does not change the corresponding point of K\mathbb{K}, so we also write χA\chi_A when AA denotes an event in the probability algebra.

Definition 2.2. Let NN be a separable metric structure. A presentation N#=(N,(ai)i∈N)N^{\#}=(N,(a_i)_{i\in\mathbb{N}}) is a countable sequence of special points whose closure under the function symbols is dense in NN. 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 K\mathbb{K} in the randomization language. Consequently, in the K\mathbb{K}-sort, the special points and generated points coincide.

Definition 2.3. A presentation N#N^{\#} in a computable signature is computable if there is an algorithm which, given an nn-ary predicate symbol PP, a tuple aˉ\bar{a} of generated points, and a positive rational ε\varepsilon, returns a rational rr such that

∣PN(aˉ)−r∣<ε.\left|P^{N}(\bar{a})-r\right|<\varepsilon.

In particular, the metric on generated points is uniformly computable.

Definition 2.4. Let N#N^{\#} be a presentation of NN.

  1. A point x∈Nx\in N is N#N^{\#}-computable if there is an algorithm which, given a positive rational ε\varepsilon, returns a generated point qq such that d(x,q)<εd(x,q)<\varepsilon.

  2. A sequence (xn)n∈N(x_n)_{n\in\mathbb{N}} is an N#N^{\#}-computable sequence if the approximation algorithm in item (1) is uniform in nn.

  3. If N0#N^{\#}_0 and N1#N^{\#}_1 are presentations and F:N0→N1F:N_0\to N_1 is an embedding, then FF is a computable map from N0#N^{\#}_0 to N1#N^{\#}_1 if, given a generated point pp of N0#N^{\#}_0 and a positive rational ε\varepsilon, one can compute a generated point qq of N1#N^{\#}_1 with d(F(p),q)<εd(F(p),q)<\varepsilon. A bijective FF is a computable isomorphism if both FF and F−1F^{-1} are computable maps.

Fix an effective enumeration (pi)i∈N(p_i)_{i\in\mathbb{N}} of the K\mathbb{K}-special points of a computable presentation P\mathcal{P}.

Definition 2.5. A partial computable function Φ:N⇀N\Phi:\mathbb{N}\rightharpoonup\mathbb{N} is a fast name for f∈Kf\in\mathbb{K} if Φ\Phi is total and

dK(pΦ(n),f)<2−nfor every n∈N.d_{\mathbb{K}}(p_{\Phi(n)},f)<2^{-n}\qquad\text{for every }n\in\mathbb{N}.

Lemma 2.6. A point f∈Kf\in\mathbb{K} is P\mathcal{P}-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 ff is P\mathcal{P}-computable, apply its approximation procedure with error 2−n2^{-n} and return the index of the resulting K\mathbb{K}-generated point. Since generated and special points coincide in K\mathbb{K}, this gives a total computable fast name. □\square

Definition 2.7. Let N#N^{\#} be a presentation of NN. A closed set X⊆NX\subseteq N is c.e. closed in N#N^{\#} if the set of rational open balls

B(p;r)={x∈N:d(x,p)<r},B(p;r)=\{x\in N:d(x,p)<r\},

where pp is generated and r>0r>0 is rational, that intersect XX is computably enumerable.

Definition 2.8. A presentation of M[0,1)M^{[0,1)} is aware if the embedded set of constant random variables

{aˉ:a∈M}⊆K\{\bar{a}:a\in M\}\subseteq\mathbb{K}

is c.e. closed in that presentation.

Proposition 2.9 ([2 Proposition 2.6]). Let SS be a computable presentation of M[0,1)M^{[0,1)}. Then SS is aware if and only if there is an enumeration (an)n∈N(a_n)_{n\in\mathbb{N}} of all constant random variables that is an SS-computable sequence.

Let 2\mathbf{2} be the two-element structure in the empty signature. Its standard presentation is decidable. Let

P=(2[0,1))#\mathcal{P} = (\mathbf{2}^{[0,1)})^{\#}

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, 0ˉ\bar{0} and 1ˉ\bar{1} occur effectively among the K-special points.

Lemma 2.10. The presentation P\mathcal{P} is computable and aware. Moreover, uniformly in a K-special point pp, a rational interval JJ, and a positive rational ε\varepsilon, one can compute a rational rr such that

∣r−μ(J∩[p=1ˉ])∣<ε.\left|r-\mu\left(J\cap[p=\bar{1}]\right)\right|<\varepsilon.

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 {0,1}\{0,1\}, and the truth of any formula of the empty signature in the finite structure 2\mathbf{2} 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 J∩[p=1ˉ]J\cap[p=\bar{1}], gives the asserted uniform computation.

For awareness, let pp be a binary simple function and let r>0r>0 be rational. Since

dK(p,0ˉ)=μ[p=1ˉ]anddK(p,1ˉ)=μ[p=0ˉ],d_{\mathrm{K}}(p,\bar{0})=\mu[p=\bar{1}] \quad\text{and}\quad d_{\mathrm{K}}(p,\bar{1})=\mu[p=\bar{0}],

the ball B(p;r)B(p;r) meets {0ˉ,1ˉ}\{\bar{0},\bar{1}\} if and only if

μ[p=0ˉ]>1−rorμ[p=1ˉ]>1−r.\mu[p=\bar{0}]>1-r \quad\text{or}\quad \mu[p=\bar{1}]>1-r.

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. □\square

The proof of Theorem 1.3

We first construct a c.e. open event AA such that neither χA\chi_A nor χAc\chi_{A^c} is a P\mathcal{P}-computable point.

Fix an effective enumeration (Φe)e∈N(\Phi_e)_{e\in\mathbb{N}} of all partial computable functions from N\mathbb{N} to N\mathbb{N}. The requirement ReR_e is

Re:if Φe is a fast name for some fe, then fe≠χA and fe≠χAc.R_e:\quad\text{if }\Phi_e\text{ is a fast name for some }f_e,\text{ then }f_e\ne\chi_A\text{ and }f_e\ne\chi_{A^c}.

For m∈Nm\in\mathbb{N}, let

Im=(2−(m+1),2−m).I_m=(2^{-(m+1)},2^{-m}).

These are pairwise disjoint rational intervals. Assign to ReR_e the two private intervals

Je0=I2e,Je1=I2e+1,J_e^0=I_{2e},\qquad J_e^1=I_{2e+1},

and set

δek=μ(Jek)>0.\delta_e^k=\mu(J_e^k)>0.

Effectively choose NeN_e so large that, with εe=2−Ne\varepsilon_e=2^{-N_e},

2εe<14min⁡{δe0,δe1}.(1)2\varepsilon_e<\frac{1}{4}\min\{\delta_e^0,\delta_e^1\}. \tag*{(1)}

Construction 3.1. At stage ss, for every e≤se\leq s that has not yet acted, simulate Φe(Ne)\Phi_e(N_e) for ss steps. If

Φe(Ne)↓=i,\Phi_e(N_e)\mathord{\downarrow}=i,

use Lemma 2.10 to compute rationals re0,re1r_e^0,r_e^1 such that

∣rek−μ(Jek∩[pi=1‾])∣<εe(k=0,1).(2)\left|r_e^k-\mu\left(J_e^k\cap[p_i=\overline{1}]\right)\right|<\varepsilon_e \qquad(k=0,1). \tag*{(2)}

Then make the following permanent decisions.

On Je0J_e^0, define AA to have the value opposite to the approximate majority value of pip_i:

A∩Je0={∅,re0≥δe0/2,Je0,re0<δe0/2.(3)A\cap J_e^0= \begin{cases} \varnothing, & r_e^0\geq\delta_e^0/2,\\ J_e^0, & r_e^0<\delta_e^0/2. \end{cases} \tag*{(3)}

On Je1J_e^1, define AA to have the same value as the approximate majority value of pip_i:

A∩Je1={Je1,re1≥δe1/2,∅,re1<δe1/2.(4)A\cap J_e^1= \begin{cases} J_e^1, & r_e^1\geq\delta_e^1/2,\\ \varnothing, & r_e^1<\delta_e^1/2. \end{cases} \tag*{(4)}

Finally, declare that ReR_e has acted. Whenever an interval is to be included in AA, enumerate that interval at this stage. If ReR_e never acts, neither of its private intervals is included in AA.

Since each private interval is controlled by a unique requirement, the decisions are compatible. The resulting set AA is a c.e. union of rational open intervals and hence is a c.e. open, in particular Borel, subset of [0,1)[0,1).

Proposition 3.2. For the event AA constructed above, neither χA\chi_A nor χAc\chi_{A^c} is a P\mathcal{P}-computable point.

Proof. Fix ee and suppose that Φe\Phi_e is a fast name for some fe∈Kf_e\in\mathsf{K}. Then Φe(Ne)\Phi_e(N_e) converges, so ReR_e acts. Write

i=Φe(Ne),p=pi,i=\Phi_e(N_e),\qquad p=p_i,

and, for k=0,1k=0,1, set

αek=μ(Jek∩[fe=1‾]).\alpha_e^k=\mu\left(J_e^k\cap[f_e=\overline{1}]\right).

Because Φe\Phi_e is a fast name,

dK(p,fe)<εe.d_{\mathsf{K}}(p,f_e)<\varepsilon_e.

For binary-valued random variables, the map f↦[f=1‾]f\mapsto[f=\overline{1}] is 1-Lipschitz from K\mathsf{K} to B\mathsf{B}. Consequently,

∣μ(Jek∩[p=1‾])−μ(Jek∩[fe=1‾])∣≤dB([p=1‾],[fe=1‾])≤dK(p,fe)<εe.\left|\mu\left(J_e^k\cap[p=\overline{1}]\right)-\mu\left(J_e^k\cap[f_e=\overline{1}]\right)\right| \leq d_{\mathsf{B}}\left([p=\overline{1}],[f_e=\overline{1}]\right)\leq d_{\mathsf{K}}(p,f_e)<\varepsilon_e.

Combining this with Equation (2), we obtain

∣αek−rek∣<2εe(k=0,1).(5)|\alpha_e^k-r_e^k|<2\varepsilon_e \qquad(k=0,1). \tag*{(5)}

We first diagonalize against χA\chi_A on Je0J_e^0. If re0≥δe0/2r_e^0\geq\delta_e^0/2, then A∩Je0=∅A\cap J_e^0=\varnothing by Equation (3), and hence

μ(Je0∩[fe≠χA])=αe0>δe02−2εe>δe04.\mu\left(J_e^0\cap[f_e\neq\chi_A]\right)=\alpha_e^0>\frac{\delta_e^0}{2}-2\varepsilon_e>\frac{\delta_e^0}{4}.

If re0<δe0/2r_e^0 < \delta_e^0/2, then A∩Je0=Je0A \cap J_e^0 = J_e^0, and hence

μ(Je0∩⟦fe≠χA⟧)=δe0−αe0>δe0−re0−2εe>δe04.\mu\left(J_e^0 \cap\llbracket f_e \ne\chi_A\rrbracket\right) = \delta_e^0 - \alpha_e^0 > \delta_e^0 - r_e^0 - 2\varepsilon_e > \frac{\delta_e^0}{4}.

The final inequalities in both cases use Equation (1). Therefore

dK(fe,χA)>δe04>0.(6)d_K(f_e,\chi_A) > \frac{\delta_e^0}{4} > 0. \tag*{(6)}

On Je1J_e^1, the definition of AA makes AcA^c have the value opposite to the approximate majority value of pp. If re1≥δe1/2r_e^1 \ge\delta_e^1/2, then Ac∩Je1=∅A^c \cap J_e^1 = \varnothing, so

μ(Je1∩⟦fe≠χAc⟧)=αe1>δe14.\mu\left(J_e^1 \cap\llbracket f_e \ne\chi_{A^c}\rrbracket\right) = \alpha_e^1 > \frac{\delta_e^1}{4}.

If re1<δe1/2r_e^1 < \delta_e^1/2, then Ac∩Je1=Je1A^c \cap J_e^1 = J_e^1, so

μ(Je1∩⟦fe≠χAc⟧)=δe1−αe1>δe14.\mu\left(J_e^1 \cap\llbracket f_e \ne\chi_{A^c}\rrbracket\right) = \delta_e^1 - \alpha_e^1 > \frac{\delta_e^1}{4}.

Consequently,

dK(fe,χAc)>δe14>0.(7)d_K(f_e,\chi_{A^c}) > \frac{\delta_e^1}{4} > 0. \tag*{(7)}

This verifies Re\mathcal{R}_e.

By Lemma 2.6, every P\mathcal{P}-computable point has a fast name Φe\Phi_e for some ee. Equations (6) and (7) therefore show that neither χA\chi_A nor χAc\chi_{A^c} is P\mathcal{P}-computable. □

Remark 3.3. For the counterexample alone, it would suffice to choose a Borel event AA for which χA\chi_A is not P\mathcal{P}-computable. Indeed, the global interchange of 0 and 1 is a computable automorphism of the standard presentation and sends χA\chi_A to χAc\chi_{A^c}, 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 τ\tau be the nontrivial automorphism of 2\mathbb{2}, so that τ(0)=1\tau(0)=1 and τ(1)=0\tau(1)=0. For ω∈[0,1)\omega\in[0,1), define

τω={τ,ω∈A,id⁡2,ω∉A.\tau_\omega= \begin{cases} \tau, & \omega\in A,\\ \operatorname{id}_{2}, & \omega\notin A. \end{cases}

For a Borel random variable ff in the randomization pre-structure, set

TA(f)(ω)=τω(f(ω)),(8)T_A(f)(\omega) = \tau_\omega(f(\omega)), \tag*{(8)}

and let TAT_A act as the identity on B\mathbb{B}.

Lemma 3.4. The map TAT_A descends to an involutive automorphism of 2[0,1)\mathbb{2}^{[0,1)}. For every LL-formula φ(x1,…,xn)\varphi(x_1,\ldots,x_n) and every f1,…,fn∈Kf_1,\ldots,f_n \in K,

⟦φ(TAf1,…,TAfn)⟧=⟦φ(f1,…,fn)⟧.(9)\llbracket\varphi(T_Af_1,\ldots,T_Af_n)\rrbracket= \llbracket\varphi(f_1,\ldots,f_n)\rrbracket. \tag*{(9)}

Furthermore,

TA(0ˉ)=χA,TA(1ˉ)=χAc.(10)T_A(\bar{0}) = \chi_A,\qquad T_A(\bar{1}) = \chi_{A^c}. \tag*{(10)}

Proof. Since AA is Borel, TA(f)T_A(f) is Borel whenever ff is Borel. For every ω\omega, the map τω\tau_\omega is an automorphism of the empty-signature structure 2\mathbf{2}. Hence, for Borel random variables and pointwise in ω\omega,

2⊨φ(f1(ω),…,fn(ω))\mathbf{2}\models\varphi(f_1(\omega),\ldots,f_n(\omega))

if and only if

2⊨φ(τωf1(ω),…,τωfn(ω)).\mathbf{2}\models\varphi(\tau_\omega f_1(\omega),\ldots,\tau_\omega f_n(\omega)).

This proves Equation (9) on the pre-structure. It also gives

f(ω)=g(ω)⟺TAf(ω)=TAg(ω),f(\omega)=g(\omega)\quad\Longleftrightarrow\quad T_Af(\omega)=T_Ag(\omega),

so TAT_A preserves the K-pseudometric. It is the identity on B\mathbb{B}, preserves every distinguished formula-event function, and satisfies TA2=id⁡T_A^2=\operatorname{id}. 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 (pi)i∈N(p_i)_{i\in\mathbb{N}} be the K\mathbb{K}-special points of P\mathcal{P}, and let (bj)j∈N(b_j)_{j\in\mathbb{N}} be its B\mathbb{B}-special points. Define a new presentation Q\mathcal{Q} by taking

qi=TA(pi)(i∈N)q_i=T_A(p_i)\qquad(i\in\mathbb{N})

as its K\mathbb{K}-special points and retaining (bj)j∈N(b_j)_{j\in\mathbb{N}} as its B\mathbb{B}-special points. Since TAT_A is an automorphism, (qi)(q_i) is dense in K\mathbb{K}, so Q\mathcal{Q} is a presentation of the same randomization.

Lemma 3.5. The presentation Q\mathcal{Q} is computable. Moreover, TA:P→QT_A:\mathcal{P}\to\mathcal{Q} is a computable isomorphism.

Proof. For all i,ji,j,

dK(qi,qj)=dK(TApi,TApj)=dK(pi,pj).d_{\mathbb{K}}(q_i,q_j)=d_{\mathbb{K}}(T_Ap_i,T_Ap_j)=d_{\mathbb{K}}(p_i,p_j).

For every LL-formula φ\varphi and every tuple of indices iˉ\bar{i}, Equation (9) gives

⟦φ(qiˉ)⟧=⟦φ(piˉ)⟧.\llbracket\varphi(q_{\bar{i}})\rrbracket=\llbracket\varphi(p_{\bar{i}})\rrbracket.

The B\mathbb{B}-special points are unchanged, and TAT_A is the identity on B\mathbb{B}. By induction on terms, every generated B\mathbb{B}-term in Q\mathcal{Q} denotes the same event as the term with the same syntactic code in P\mathcal{P}. Thus there is an effective code-preserving translation from generated points of Q\mathcal{Q} to generated points of P\mathcal{P} under which all metric and predicate values agree. The algorithms computing the atomic data of P\mathcal{P} therefore compute the atomic data of Q\mathcal{Q}.

On the K\mathbb{K}, TAT_A sends the special point pip_i to the special point qiq_i with the same index and error 00. On the B\mathbb{B}, it sends every generated term to the term with the same syntactic code. Hence TAT_A is a computable map from P\mathcal{P} to Q\mathcal{Q}. Since TAT_A is an involution, the same index-preserving procedures compute its inverse. Therefore TAT_A is a computable isomorphism. □

Remark 3.6. The event AA is deliberately noncomputable as a point of the standard presentation, but this does not prevent Q\mathcal{Q} 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 TAT_A preserves them exactly. The map TAT_A is computable from P\mathcal{P} to Q\mathcal{Q}, but not from P\mathcal{P} to itself: it sends the P\mathcal{P}-computable point 0ˉ\bar{0} to the noncomputable point xAx_A.

Proof. The presentation QQ is computable by Lemma 3.5. Suppose, toward a contradiction, that QQ is aware. By Proposition 2.9, there is a QQ-computable sequence (cn)n∈N(c_n)_{n\in\mathbb{N}} whose range is exactly {0ˉ,1ˉ}\{\bar{0},\bar{1}\}. Since TA−1:Q→PT_A^{-1}: Q \to P is a computable isometry, the sequence

fn=TA−1(cn)f_n=T_A^{-1}(c_n)

is PP-computable, and its range is {χA,χAc}\{\chi_A,\chi_{A^c}\} by Equation (10). In particular, f0f_0 is a PP-computable point belonging to {χA,χAc}\{\chi_A,\chi_{A^c}\}, contrary to Proposition 3.2. Hence QQ is not aware.

Finally, if 0ˉ\bar{0} were a QQ-computable point, then applying the computable inverse TA−1T_A^{-1} would make χA\chi_A a PP-computable point. Similarly, computability of 1ˉ\bar{1} in QQ would imply computability of χAc\chi_{A^c} in PP. Thus neither constant is QQ-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 PP is aware by Lemma 2.10, while QQ is not aware, and Lemma 3.5 gives a computable isomorphism TA:P→QT_A:P\to Q 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 M∞M_\infty be the structure with universe N\mathbb{N} in the empty signature. Thus every permutation of N\mathbb{N} is an automorphism of M∞M_\infty.

Lemma 4.1. There is an involution q:N→Nq:\mathbb{N}\to\mathbb{N} such that its fixed-point set

F={n∈N:q(n)=n}F=\{n\in\mathbb{N}:q(n)=n\}

is not c.e.

Proof. Fix a c.e. noncomputable set K⊆NK\subseteq\mathbb{N}. On each pair {2e,2e+1}\{2e,2e+1\}, let qq interchange the two elements if e∈Ke\in K and fix both elements if e∉Ke\notin K. Explicitly,

q(2e)={2e+1,e∈K,2e,e∉K,q(2e+1)={2e,e∈K,2e+1,e∉K.q(2e)= \begin{cases} 2e+1, & e\in K,\\ 2e, & e\notin K, \end{cases} \qquad q(2e+1)= \begin{cases} 2e, & e\in K,\\ 2e+1, & e\notin K. \end{cases}

Then q2=id⁡Nq^2=\operatorname{id}_{\mathbb{N}} and

F={2e,2e+1:e∉K}.F=\{2e,2e+1:e\notin K\}.

If FF were c.e., then N∖K={e:2e∈F}\mathbb{N}\setminus K=\{e:2e\in F\} would be c.e. Since KK is c.e., this would make KK computable, a contradiction. □

Put

I0=[0,12),I1=[12,1).I_0=[0,\tfrac{1}{2}),\qquad I_1=[\tfrac{1}{2},1).

For a Borel random variable f:[0,1)→Nf:[0,1)\to\mathbb{N}, define

Θ(f)(ω)={f(ω),ω∈I0,q(f(ω)),ω∈I1,(11)\Theta(f)(\omega)= \begin{cases} f(\omega), & \omega\in I_0,\\ q(f(\omega)), & \omega\in I_1, \end{cases} \tag*{(11)}

and let Θ\Theta act as the identity on B\mathbb{B}.

Lemma 4.2. The map Θ\Theta descends to an involutive automorphism of M∞[0,1)M_{\infty}^{[0,1)}. Moreover, for every formula φ(x1,…,xn)\varphi(x_1,\ldots,x_n) in the empty signature and all f1,…,fn∈Kf_1,\ldots,f_n\in\mathbb{K},

⟦φ(Θf1,…,Θfn)⟧=⟦φ(f1,…,fn)⟧.(12)\llbracket\varphi(\Theta f_1,\ldots,\Theta f_n)\rrbracket=\llbracket\varphi(f_1,\ldots,f_n)\rrbracket. \tag*{(12)}

Proof. The function Θ(f)\Theta(f) is Borel because N\mathbb{N} has the discrete sigma-algebra. At each ω\omega, the fiber map used in Equation (11) is either id⁡N\operatorname{id}_{\mathbb{N}} or qq, hence an automorphism of M∞M_\infty. Formula satisfaction is therefore preserved pointwise, which gives Equation (12). Applying this to equality shows that Θ\Theta preserves the K\mathbb{K}-pseudometric. It is the identity on B\mathbb{B} and satisfies Θ2=id⁡\Theta^2=\operatorname{id}, so it descends to the metric quotient and extends uniquely to an involutive automorphism of the completion. □\square

Let

P∞=(M∞[0,1))#\mathcal{P}_\infty=(M_{\infty}^{[0,1)})^\#

be the standard induced presentation. The standard presentation of M∞M_\infty is decidable, so P∞\mathcal{P}_\infty is computable by [2 Corollary 3.4]. Let (ri)i∈N(r_i)_{i\in\mathbb{N}} be its K\mathbb{K}-special points and (sj)j∈N(s_j)_{j\in\mathbb{N}} its B\mathbb{B}-special points. Since the induced presentation effectively lists all rational simple random variables, there is a computable function c:N→Nc:\mathbb{N}\to\mathbb{N} such that

rc(n)=nˉ(n∈N).r_{c(n)}=\bar n\qquad(n\in\mathbb{N}).

Define a presentation Q∞\mathcal{Q}_\infty by taking

ui=Θ(ri)(i∈N)u_i=\Theta(r_i)\qquad(i\in\mathbb{N})

as its K\mathbb{K}-special points and retaining (sj)j∈N(s_j)_{j\in\mathbb{N}} as its B\mathbb{B}-special points.

Lemma 4.3. The presentation Q∞\mathcal{Q}_\infty is computable, and Θ:P∞→Q∞\Theta:\mathcal{P}_\infty\to\mathcal{Q}_\infty is a computable isomorphism.

Proof. By Lemma 4.2, (ui)i∈N(u_i)_{i\in\mathbb{N}} is dense in K\mathbb{K}. Equation (12) shows that every formula-event evaluated on a tuple of the uiu_i is exactly the same event as the corresponding formula-event evaluated on the tuple of the rir_i. The B\mathbb{B}-special points are unchanged. Consequently, generated points with the same syntactic codes in P∞\mathcal{P}_\infty and Q∞\mathcal{Q}_\infty have the same metric and predicate values. The algorithms for P∞\mathcal{P}_\infty therefore compute the atomic data of Q∞\mathcal{Q}_\infty.

The map Θ\Theta sends each rir_i to uiu_i with the same index and fixes the B\mathbb{B}. Hence the same-code map computes Θ\Theta. Since Θ\Theta is an involution, the same procedure computes its inverse. □\square

Theorem 4.4. The computable presentation Q∞\mathcal{Q}_\infty of M∞[0,1)M_{\infty}^{[0,1)} is not aware. Nevertheless, every constant random variable nˉ\bar n is a Q∞\mathcal{Q}_\infty-computable point.

Proof. For each n∈Nn\in\mathbb{N}, consider the rational open ball

Un=B(uc(n);13)=B(Θ(nˉ);13).U_n=B\left(u_{c(n)};\frac{1}{3}\right)=B\left(\Theta(\bar n);\frac{1}{3}\right).

Then (Un)n∈N(U_n)_{n\in\mathbb{N}} is an effective sequence of rational open balls in Q∞\mathcal{Q}_\infty. If n∈Fn\in F, then q(n)=nq(n)=n, so Θ(nˉ)=nˉ\Theta(\bar n)=\bar n and UnU_n meets the constant random variables. Suppose that n∉Fn\notin F. Then Θ(nˉ)\Theta(\bar n) equals nn on I0I_0 and q(n)≠nq(n)\ne n on I1I_1. Hence, for every m∈Nm\in\mathbb{N},

dK(Θ(nˉ),mˉ)={12,m∈{n,q(n)},1,m∉{n,q(n)}.d_{\mathbb{K}}(\Theta(\bar n),\bar m)= \begin{cases} \frac{1}{2}, & m\in\{n,q(n)\},\\ 1, & m\notin\{n,q(n)\}. \end{cases}

Thus UnU_n is disjoint from the constant random variables. We have proved

Un∩{m‾:m∈N}≠∅⟺n∈F.(13)U_n \cap\{\overline{m}:m\in\mathbb{N}\}\ne\varnothing\quad\Longleftrightarrow\quad n\in F. \tag*{(13)}

If Q∞Q_\infty were aware, then by Definitions 2.7 and 2.8 the rational open balls meeting {m‾:m∈N}\{\overline{m}:m\in\mathbb{N}\} would form a c.e. set. Applying this enumeration to the effective sequence (Un)(U_n) and using Equation (13) would make FF c.e., contradicting Lemma 4.1. Therefore Q∞Q_\infty is not aware.

It remains to verify the final assertion. For a fixed nn, the random variable

vn(ω)=Θ(n‾)(ω)={n,ω∈I0,q(n),ω∈I1.v_n(\omega)=\Theta(\overline{n})(\omega)= \begin{cases} n, & \omega\in I_0,\\ q(n), & \omega\in I_1. \end{cases}

is a rational simple random variable and hence occurs among the K-special points of P∞P_\infty. Since Θ\Theta is an involution, Θ(vn)=n‾\Theta(v_n)=\overline{n}. Therefore n‾\overline{n} occurs among the K-special points of Q∞Q_\infty and is Q∞Q_\infty-computable. For each fixed nn, the two natural numbers nn and q(n)q(n) can be built into a code for vnv_n; this argument does not give a uniform procedure for obtaining such a code from nn.

In fact, there is no uniform procedure producing names for these constants: otherwise (n‾)n∈N(\overline{n})_{n\in\mathbb{N}} would be a Q∞Q_\infty-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 (2ω,μ)(2^\omega,\mu). Binary expansion induces a computable isomorphism between its probability algebra and the standard probability algebra on [0,1)[0,1), modulo the null set of ambiguous binary expansions.

Definition 5.1 (Hirschfeldt [4]). (1) A tree T⊆2<ωT\subseteq2^{<\omega} is a PAC tree if it is computable, has no dead ends, and every path through TT is computable.

(2) If S⊆2ωS\subseteq2^\omega, a computable listing of SS is a uniformly computable sequence of elements of 2ω2^\omega whose range is SS; repetitions are allowed.

(3) For a PAC tree TT, let STS_T be the set of isolated paths through TT.

Theorem 5.2 (Goncharov–Nurtazin; Millar; see Hirschfeldt [4, Theorem 1.9]). There is a PAC tree T⊆2<ωT\subseteq2^{<\omega} such that STS_T 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 TT be a PAC tree. Then STS_T is dense in [T][T].

Proof. Fix a noncomputable X∈2ωX\in2^\omega and a node σ∈T\sigma\in T. Starting at σ\sigma, follow the unique immediate successor whenever there is only one. At the kkth node having two immediate successors, take the successor selected by X(k)X(k). This defines a path p∈[T]p\in[T] extending σ\sigma.

If infinitely many splitting nodes occurred along pp, then XX would be computable from pp: since TT is computable, one can locate the successive splitting nodes along pp and read the choices made there. But every path through a PAC tree is computable, contradicting the choice of XX. Hence only finitely many splits occur along pp. Beyond the last split, pp has a unique continuation in TT, so pp is isolated.

Fix a tree TT as in Theorem 5.2. Let

LT={Pn:n∈N}L_T = \{P_n : n \in\mathbb{N}\}

be a computable language of unary predicates, and define the LTL_T-structure

MT=ST×N,M_T = S_T \times\mathbb{N},

and for all kk and nn,

MT⊨Pn(p,k)⟺p(n)=1.(14)M_T \models P_n(p,k) \Longleftrightarrow p(n)=1. \tag*{(14)}

MTM_T is countable since STS_T is countable. Equation (14) ensures that each path type is realized infinitely often.

For σ∈2m\sigma\in2^m, let

ϑσ(x)=⋀j<mσ(j)=1Pj(x)∧⋀j<mσ(j)=0¬Pj(x).\vartheta_\sigma(x) = \bigwedge_{\substack{j<m\\ \sigma(j)=1}} P_j(x) \land\bigwedge_{\substack{j<m\\ \sigma(j)=0}} \neg P_j(x).

Lemma 5.4. For every σ∈2ω\sigma\in2^\omega,

ϑσ(MT)≠∅⟺σ∈T.\vartheta_\sigma(M_T) \ne\varnothing\Longleftrightarrow\sigma\in T.

Whenever ϑσ(MT)\vartheta_\sigma(M_T) is nonempty, it is infinite.

Proof. If MT⊨ϑσ(p,k)M_T \models\vartheta_\sigma(p,k), then σ≺p∈[T]\sigma\prec p \in[T], so σ∈T\sigma\in T. Conversely, if σ∈T\sigma\in T, then Lemma 5.3 gives p∈STp \in S_T extending σ\sigma. Every (p,k)(p,k), for k∈Nk \in\mathbb{N}, then satisfies ϑσ\vartheta_\sigma. □\square

Proposition 5.5. The theory Th⁡(MT)\operatorname{Th}(M_T) 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 ∃x\exists x from a quantifier-free formula, first put the formula into disjunctive normal form. In any conjunct in which xx is required to equal another variable, substitute that variable for xx. Otherwise, xx is required to avoid only finitely many other variables and to satisfy a finite Boolean pattern in the predicates PnP_n.

Choose mm larger than every predicate index appearing in the formula and consider the finitely many strings σ∈2m\sigma\in2^m extending this partial pattern. By Lemma 5.4, the pattern is realizable if and only if at least one such σ\sigma belongs to TT; whenever it is realizable, it has infinitely many realizations and hence one outside the finite prohibited set. Membership in TT 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. □\square

Proposition 5.6. The structure MTM_T has no computable presentation.

Proof. Suppose that (ai)i∈N(a_i)_{i\in\mathbb{N}} were a computable presentation of MTM_T. For each ii, define pi∈2ωp_i \in2^\omega by

pi(n)=1⟺MT⊨Pn(ai).p_i(n)=1 \Longleftrightarrow M_T \models P_n(a_i).

The computable atomic diagram makes (pi)i∈N(p_i)_{i\in\mathbb{N}} a uniformly computable sequence. Every pip_i lies in STS_T, and every p∈STp \in S_T occurs because the presentation contains an element corresponding to (p,0)(p,0). Thus (pi)(p_i) is a computable listing of STS_T, contrary to Theorem 5.2. □\square

Using the same path-selection procedure, we next construct an almost-everywhere enumeration of MTM_T on the probability space 2ω2^\omega. Let (σi)i∈N(\sigma_i)_{i\in\mathbb{N}} be an effective enumeration of the nodes of TT in which every node occurs infinitely often. Given X∈2ωX\in2^\omega, let πiX∈[T]\pi_i^X\in[T] be the path obtained by starting at σi\sigma_i, following the unique successor at a nonsplitting node, and using the bits of XX in order to choose successors at splitting nodes.

Lemma 5.7. If XX is noncomputable, then πiX∈ST\pi_i^X\in S_T for every ii, and every member of STS_T occurs infinitely often in (πiX)i∈N(\pi_i^X)_{i\in\mathbb{N}}.

Proof. The proof of Lemma 5.3, applied above σi\sigma_i, shows that πiX\pi_i^X is isolated: if it passed through infinitely many splitting nodes, then the choices along the computable path πiX\pi_i^X would compute XX.

If p∈STp\in S_T, choose a node σ≺p\sigma\prec p whose unique extension in [T][T] is pp. Every guided path starting at σ\sigma equals pp. Since σ\sigma occurs infinitely often among the σi\sigma_i, the path pp occurs infinitely often among the πiX\pi_i^X.

For i∈Ni\in\mathbb{N} and X∈2ωX\in2^\omega, define the occurrence rank

ρi(X)=∣{j<i:πjX=πiX}∣.\rho_i(X)=\lvert\{j<i:\pi_j^X=\pi_i^X\}\rvert.

Let Comp⁡⊆2ω\operatorname{Comp}\subseteq2^\omega be the set of computable reals. This set is countable and hence Borel and null. Fix any p∗∈STp_*\in S_T and define

fi(X)={(πiX,ρi(X)),X∉Comp⁡,(p∗,i),X∈Comp⁡.(15)f_i(X)= \begin{cases} (\pi_i^X,\rho_i(X)), & X\notin\operatorname{Comp},\\ (p_*,i), & X\in\operatorname{Comp}. \end{cases} \tag*{(15)}

Lemma 5.8. Each fif_i is a Borel MTM_T-valued random variable. For every X∉Comp⁡X\notin\operatorname{Comp}, the map i↦fi(X)i\mapsto f_i(X) is a bijection from N\mathbb{N} onto MTM_T.

Proof. The map X↦πiXX\mapsto\pi_i^X is continuous: a finite initial segment of its output is determined by a finite initial segment of XX. It follows that {X:πjX=πiX}\{X:\pi_j^X=\pi_i^X\} and {X:πiX=p}\{X:\pi_i^X=p\}, for fixed pp, are closed. Thus ρi\rho_i is Borel, and every fiber of the function in (15) is Borel. Since MTM_T is countable and discrete, this proves that fif_i is Borel measurable.

For noncomputable XX, Lemma 5.7 says that every p∈STp\in S_T appears infinitely often among the πiX\pi_i^X. Its successive occurrences have ranks 0,1,2,…0,1,2,\ldots. Hence every pair (p,k)∈ST×N(p,k)\in S_T\times\mathbb{N} appears exactly once among the fi(X)f_i(X).

The modification on Comp⁡\operatorname{Comp} makes every fif_i genuinely MTM_T-valued at every point; no effective recognition of Comp⁡\operatorname{Comp} will be needed. For i,n∈Ni,n\in\mathbb{N}, put

Ei,n={X∈2ω:πiX(n)=1}.E_{i,n}=\{X\in2^\omega:\pi_i^X(n)=1\}.

The set Ei,nE_{i,n} is effectively clopen, uniformly in ii and nn. Indeed, to determine πiX(n)\pi_i^X(n), one extends σi\sigma_i by at most max⁡{0,n+1−∣σi∣}\max\{0,n+1-\lvert\sigma_i\rvert\} bits and uses at most one bit of XX per extension. All immediate-successor questions in TT are decidable. Simulating this finite computation on every binary word of that length therefore produces a finite union of basic cylinders coding Ei,nE_{i,n}. In the probability algebra we have

⟦Pn(fi)⟧=Ei,n,(16)\llbracket P_n(f_i)\rrbracket=E_{i,n}, \tag*{(16)}
⟦fi=fj⟧={2ω,i=j,∅,i≠j.(17)\llbracket f_i=f_j\rrbracket= \begin{cases} 2^\omega, & i=j,\\ \varnothing, & i\ne j. \end{cases} \tag*{(17)}

The first equality ignores only the null set Comp. For the second, the definition on Comp also keeps the fi(X)f_i(X) pairwise distinct there. Thus equality events are computed by comparing indices; no computation of the occurrence ranks ρi(X)\rho_i(X) is required.

Let C\mathcal{C} be the effective Boolean algebra of clopen subsets of 2ω2^\omega, represented by finite unions of basic cylinders. Let D\mathcal{D} be the countable family of all finite clopen pastings of the fif_i: its members have the form

h(X)=fia(X)when X∈Ca,(18)h(X)=f_{i_a}(X)\quad\text{when }X\in C_a, \tag*{(18)}

where (Ca)a<s(C_a)_{a<s} is a finite partition of 2ω2^\omega by members of C\mathcal{C} and i0,…,is−1∈Ni_0,\ldots,i_{s-1}\in\mathbb{N}. The family D\mathcal{D} has an effective enumeration by the finite codes for these partitions and indices.

Lemma 5.9. The family D\mathcal{D} is dense in the K-sort of the Borel randomization of MTM_T over 2ω2^\omega.

Proof. Let g:2ω→MTg:2^\omega\to M_T be a Borel random variable. Outside Comp, the sequence (fi(X))i(f_i(X))_i enumerates MTM_T without repetition. Define pairwise disjoint Borel sets

Ai={X:g(X)=fi(X) and (∀j<i) g(X)≠fj(X)}.A_i=\{X:g(X)=f_i(X)\text{ and }(\forall j<i)\ g(X)\ne f_j(X)\}.

Their union contains 2ω∖Comp2^\omega\setminus\mathrm{Comp}.

Given ε>0\varepsilon>0, choose NN such that μ(⋃i<NAi)>1−ε/2\mu\left(\bigcup_{i<N}A_i\right)>1-\varepsilon/2. Finite measurable partitions can be approximated in measure by clopen partitions, so there is a clopen partition C0,…,CNC_0,\ldots,C_N such that

∑i<Nμ(Ai△Ci)<ε/2.\sum_{i<N}\mu(A_i\mathbin{\triangle}C_i)<\varepsilon/2.

Let hh equal fif_i on CiC_i for i<Ni<N and equal f0f_0 on CNC_N. Then

{X:g(X)≠h(X)}⊆(2ω∖⋃i<NAi)∪⋃i<N(Ai△Ci),\{X:g(X)\ne h(X)\}\subseteq\left(2^\omega\setminus\bigcup_{i<N}A_i\right)\cup\bigcup_{i<N}(A_i\mathbin{\triangle}C_i),

and hence dK(g,h)<εd_K(g,h)<\varepsilon. Thus D\mathcal{D} is dense. This argument only establishes density; an effective choice of NN or of the approximating clopen partition is not needed. □

Proposition 5.10. Taking D\mathcal{D} as the special points of the K-sort and C\mathcal{C} as the special points of the B-sort yields a computable presentation of the Borel randomization of MTM_T over 2ω2^\omega.

Proof. We show uniformly how to compute all formula events on tuples from D\mathcal{D}. Given an LTL_T-formula φ(xˉ)\varphi(\bar{x}), use Proposition 5.5 to compute a quantifier-free formula ψ(xˉ)\psi(\bar{x}) equivalent to φ\varphi in Th⁡(MT)\operatorname{Th}(M_T). Given a tuple hˉ\bar{h} 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 fif_i.

An equality between two such components is decided by comparing their indices, using (17). An atomic predicate Pn(fi)P_n(f_i) is represented by the uniformly effective clopen set Ei,nE_{i,n}, using (16). Performing the Boolean operations in ψ\psi therefore produces effectively a clopen set Cφ,hˉC_{\varphi,\bar{h}} satisfying

⟦φ(hˉ)⟧=Cφ,hˉ\llbracket\varphi(\bar{h})\rrbracket=C_{\varphi,\bar{h}}

in the probability algebra.

The measure of a clopen subset of 2ω2^\omega is a computable dyadic rational. Consequently, all formula-event function symbols and their measures are computable on the named points. In particular,

dK(h,h′)=μ⟦h≠h′⟧d_{\mathsf K}(h,h')=\mu\llbracket h\ne h'\rrbracket

is computable for h,h′∈Dh,h'\in\mathcal{D}. Boolean operations, measure, and dB(A,B)=μ(A△B)d_{\mathsf B}(A,B)=\mu(A\mathbin{\triangle}B) 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 K\mathsf K-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 MTM_T is decidable and has effective quantifier elimination. By Proposition 5.6, MTM_T 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 [0,1)[0,1), the randomization MT[0,1)M_T^{[0,1)} 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. [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. [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. [3]J. N. Y. Franklin, I. Goldbring and T. H. McNicholl, Effective metric structure theory, Springer Monographs in Mathematics, Springer, Cham, 2026.DOI
  4. [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. [5]H. J. Keisler, Randomizing a model, Adv. Math. 143 (1999), no. 1, 124–158.DOI
  6. [6]D. Marker, Model Theory: An Introduction, Graduate Texts in Mathematics, vol. 217, Springer-Verlag, New York, 2002. doi:10.1007/b98860.DOI

Paper details

vlnc:W_dddbbdtc
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

OpenAI’s ChatGPT 5.6

View statement
Looking for related papers…
Contents