Publishing house / Journals and Serials / Fundamenta Mathematicae / All issues

Abstract

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$.