A Lopez-Escobar Theorem for Continuous Domains

Abstract

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let $Mod(\tau )$ be the set of countable structures with universe $\omega$ in vocabulary $\tau$ topologized by the Scott topology. We show that an invariant set $X\subseteq Mod(\tau )$ is ${\Pi }_{\alpha }^0$ in the effective Borel hierarchy of this topology if and only if it is definable by a ${\Pi }_{\alpha }^p$ - formula, a positive ${\Pi }_{\alpha }^0$ formula in the infinitary logic $L_{{\omega }_1,\omega }$. As a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let $K$ be positively computably embeddable in $K^{\prime }$ by $\Phi$, then for every ${\Pi }_{\alpha }^p$ formula $\xi$ in the vocabulary of $K^{\prime }$ there is a ${\Pi }_{\alpha }^p$ formula ${\xi }^{\star }$ in the vocabulary of $K$ such that for all $A\in K$, $A\models {\xi }^{\star }$ if and only if $\Phi (A)\models \xi$. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings.

17 pages

References in corpus (1)

• Computable embeddings for pairs of linear orders