Continuous Logic, Diagrams, and Truth Values for Computable Presentations

Abstract: Goldbring,McNicholl, and I investigated the arithmetic and hyperarithmetic degrees of the finitary and computable infinitary diagrams of continuous logic for computably presented metric structures. As the truth value of a sentence of continuous logic may be any real in [0,1], we introduced two kinds of diagrams at each level: the closed diagram, which encapsulates weak inequalities of truth values, and the open diagram, which encapsulates strict inequalities. We showed that, for any computably presented metric structure and any computable ordinal $\alpha$, the closed and open $\Sigma^c_\alpha$ diagrams are $\Pi^0_{\alpha+1}$ and $\Sigma^0_\alpha$, respectively, and that the closed and open $\Pi^c_\alpha$ diagrams are $\Pi^0_\alpha$ and $\Sigma^0_{\alpha+1}$.

Proving the optimality of these bounds, however, was non-trivial. Since the standard presentation of [0,1] with the Euclidean metric is computably compact, we were forced to work on the natural numbers with the discrete metric (in some sense, the "simplest" non-compact metric space). Along the way, we also proved some surprising combinatorial results. McNicholl and I then continued our study of computable infinitary continuous logic and found that for any nonzero computable ordinal $\alpha$ and any right $\Pi^0_\alpha$ (or $\Sigma^0_\alpha$) real number, there is a $\Pi^c_\alpha$ (or $\Sigma^c_\alpha$) sentence which is universally interpreted as that value.

logic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic