Metric structures and probabilistic computation (Q541224)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Metric structures and probabilistic computation
scientific article

    Statements

    Metric structures and probabilistic computation (English)
    0 references
    0 references
    6 June 2011
    0 references
    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.
    0 references
    computable model theory
    0 references
    continuous first-order logic
    0 references
    probabilistic computation
    0 references
    Henkin construction
    0 references

    Identifiers

    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references