A Lopez-Escobar Theorem for Continuous Domains

Abstract: We prove an effective version of the Lopez-Escobar theorem for continuous domains. Let

M o d (a u

be the set of countable structures with universe

o m e g a

in vocabulary

a u

topologized by the Scott topology. We show that an invariant set

X s u b s e t e q M o d (a u)

is

P i_{a}^{0} l p h a

in the effective Borel hierarchy of this topology if and only if it is definable by a

P i_{a}^{p} l p h a

- formula, a positive

P i_{a}^{0} l p h a

formula in the infinitary logic

L_{o m e g a_{1}, o m e g a}

. As a corollary of this result we obtain a new pullback theorem for computable embeddings: Let

K

be computably embeddable in

K^{'}

by

P h i

, then for every

P i_{a}^{p} l p h a

formula

x i

in the vocabulary of

K^{'}

there is a

P i_{a}^{p} l p h a

formula

x i^{s} t a r

in the vocabulary of

K

such that for all

A i n K

,

A m o d e l s x i^{s} t a r

if and only if

P h i (A) m o d e l s x i

. We use this to obtain new results on the possibility of computable embeddings into the class of linear orderings.

This page was built for publication: A Lopez-Escobar Theorem for Continuous Domains