Can I read On the Complexity of the Theory of a Computably Presented Metric Structure on EtoBox?

On the Complexity of the Theory of a Computably Presented Metric Structure by Caleb Camrud; Isaac Goldbring; Timothy H. McNicholl is a Computer Science article available to read on EtoBox.

What is On the Complexity of the Theory of a Computably Presented Metric Structure about?

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 φ M ≤ r , and the open diagram, which encapsulates strict inequalities of the form φ M < r . We show that the closed and open N diagrams are 0 N +1 and 0N respectively, and that the closed and open N diagrams are 0 N and 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.

Who reads On the Complexity of the Theory of a Computably Presented Metric Structure?

Author

Caleb Camrud; Isaac Goldbring; Timothy H. McNicholl

Publisher

Springer Science and Business Media LLC

Published

2023

Language

EN

Field

Computer Science (Physical Sciences)