On the complexity of the theory of a computably presented metric structure

We consider the complexity (in terms of the arithmetical hierarchy) of the various quantifier levels of the diagram of a computably presented metric structure. As the truth value of a sentence of continuous logic may be any real in [0, 1], we introduce two kinds of diagrams at each level: the closed diagram, which encapsulates weak inequalities of the form phi(M) <= r, and the open diagram, which encapsulates strict inequalities of the form phi(M) < r. We show that the closed and open Sigma(N) diagrams are Pi(0)(N+1) and Sigma(0)(N) respectively, and that the closed and open Pi(N) diagrams are Pi(0)(N) and Sigma(0)(N+1) respectively. We then introduce effective infinitary formulas of continuous logic and extend our results to the hyperarithmetical hierarchy. Finally, we demonstrate that our results are optimal.

Automated summary

This article examines the complexity of the quantifier levels of computably presented metric structures in terms of the arithmetical hierarchy. Two types of diagrams, closed and open, are introduced at each level, representing weak and strict inequalities respectively. The closed Sigma(N) and open Sigma(N) diagrams are proven to be Pi(0)(N+1) and Sigma(0)(N) respectively, while the closed Pi(N) and open Pi(N) diagrams are shown to be Pi(0)(N) and Sigma(0)(N+1) respectively. Effective infinitary formulas of continuous logic are introduced and the results are extended to the hyperarithmetical hierarchy. The optimality of the results is demonstrated.