The effective Borel hierarchy

Volume 195 / 2007

M. Vanden Boom Fundamenta Mathematicae 195 (2007), 269-289 MSC: Primary 03E15; Secondary 03C57, 03C75, 03D55 DOI: 10.4064/fm195-3-4


Let $K$ be a subclass of $\mathop{\rm Mod}(\mathcal{L})$ which is closed under isomorphism. Vaught showed that $K$ is ${\bf\Sigma}_\alpha$ (respectively, ${\bf\Pi}_\alpha$) in the Borel hierarchy iff $K$ is axiomatized by an infinitary $\Sigma_\alpha$ (respectively, $\Pi_\alpha$) 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 $\Sigma_\alpha$ or effective $\Pi_\alpha$ 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 ${\mit\Phi}$ is a Turing computable embedding of $K \subseteq \mathop{\rm Mod}(\mathcal{L})$ into $K' \subseteq \mathop{\rm Mod}(\mathcal{L'})$, then for any computable infinitary sentence $\varphi$ in the language $\mathcal{L}$, we can find a computable infinitary sentence $\varphi^*$ in $\mathcal{L}'$ such that for all $\mathcal{A}\in K$, $\mathcal{A}\models\varphi^*$ iff ${\mit\Phi}(\mathcal{A})\models\varphi$, where $\varphi^*$ has the same complexity as~$\varphi$.


  • M. Vanden BoomDepartment of Mathematics
    University of Notre Dame
    Notre Dame, IN 46556, U.S.A.

Search for IMPAN publications

Query phrase too short. Type at least 4 characters.

Rewrite code from the image

Reload image

Reload image