The effective Borel hierarchy

M. Vanden Boom. "The effective Borel hierarchy." Fundamenta Mathematicae 195.3 (2007): 269-289. <http://eudml.org/doc/283326>.

@article{M2007,
abstract = {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 φ.},
author = {M. Vanden Boom},
journal = {Fundamenta Mathematicae},
keywords = {effective Borel set; Vaught's theorem; computable embedding},
language = {eng},
number = {3},
pages = {269-289},
title = {The effective Borel hierarchy},
url = {http://eudml.org/doc/283326},
volume = {195},
year = {2007},
}

TY - JOUR
AU - M. Vanden Boom
TI - The effective Borel hierarchy
JO - Fundamenta Mathematicae
PY - 2007
VL - 195
IS - 3
SP - 269
EP - 289
AB - 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 φ.
LA - eng
KW - effective Borel set; Vaught's theorem; computable embedding
UR - http://eudml.org/doc/283326
ER -