Let K be a subclass of Mod() which is closed under isomorphism. Vaught showed that K is (respectively, ) in the Borel hierarchy iff K is axiomatized by an infinitary (respectively, ) sentence. We prove a generalization of Vaught’s theorem for the effective Borel hierarchy, i.e. the Borel sets formed by union and complementation over c.e. sets. This result says that we can axiomatize an effective or effective Borel set with a computable infinitary sentence of the same complexity. This result yields an alternative proof of Vaught’s theorem via forcing. We also get a version of the pull-back theorem from Knight et al. which says if Φ is a Turing computable embedding of K ⊆ Mod() into K’ ⊆ Mod(ℒ’), then for any computable infinitary sentence φ in the language , we can find a computable infinitary sentence φ* in ’ such that for all ∈ K, ⊨ φ* iff Φ( ) ⊨ φ, where φ* has the same complexity as φ.
@article{bwmeta1.element.bwnjournal-article-doi-10_4064-fm195-3-4,
author = {M. Vanden Boom},
title = {The effective Borel hierarchy},
journal = {Fundamenta Mathematicae},
volume = {193},
year = {2007},
pages = {269-289},
zbl = {1125.03035},
language = {en},
url = {http://dml.mathdoc.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm195-3-4}
}
M. Vanden Boom. The effective Borel hierarchy. Fundamenta Mathematicae, Tome 193 (2007) pp. 269-289. http://gdmltest.u-ga.fr/item/bwmeta1.element.bwnjournal-article-doi-10_4064-fm195-3-4/