A Lopez-Escobar theorem for continuous domains

Abstract

We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let Mod(τ) be the set of countable structures with universe ω in vocabulary τ topologized by the Scott topology. We show that an invariant set X ⊆ Mod(τ) is Π0α in the effective Borel hierarchy of this topology if and only if it is definable by a Πpα-formula, a positive Π0α formula in the infinitary logic Lω1ω. As a corollary of this result we obtain a new pullback theorem for positive computable embeddings: Let K be positively computably embeddable in K′ by Φ, then for every Πpα formula ξ in the vocabulary of K′ there is a Πpα formula ξ∗ in the vocabulary of K such that for all A ∈ K, A |= ξ∗ if and only if Φ(A) |= ξ. We use this to obtain new results on the possibility of positive computable embeddings into the class of linear orderings.