Metric structures and probabilistic computation (Q541224): Difference between revisions

The author uses probabilistic computation to study the effective content of continuous first-order logic in the sense of, for example, \textit{I. Ben Yaacov} and \textit{A. P. Pedersen} [J. Symb. Log. 75, No. 1, 168--190 (2010; Zbl 1194.03028)]. The main result is that if \(T\) is a complete decidable continuous first-order theory, then there is a probabilistically decidable continuously weak structure \({\mathcal M}\) with \({\mathcal M}\) a model of \(T\). This is proven by a Henkin construction of sorts. Some relationships with BPP and with reverse mathematics are discussed.