COMPUTABLE PRESENTATIONS OF RANDOMIZATIONS

Abstract We initiate the effective metric structure theory of Keisler randomizations. We show that a classical countable structure M $\mathcal M$ script upper M has a decidable presentation if and only if its Borel randomization M [ 0 , 1 ) $\mathcal {M}^{[0,1)}$ script upper M Superscript left bracket 0 comma 1 right parenthesis 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 M $\mathcal M$ script upper M is effectively ω $\omega $ omega -categorical, then M [ 0 , 1 ) $\mathcal {M}^{[0,1)}$ script upper M Superscript left bracket 0 comma 1 right parenthesis 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.