The effective Borel hierarchy

M. Vanden Boom¹

¹ Department of Mathematics University of Notre Dame Notre Dame, IN 46556, U.S.A.

Fundamenta Mathematicae, Tome 195 (2007) no. 3, pp. 269-289.

Résumé

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

Détail

DOI : 10.4064/fm195-3-4

Keywords: subclass mathop mod mathcal which closed under isomorphism vaught showed sigma alpha respectively alpha borel hierarchy axiomatized infinitary sigma alpha respectively alpha sentence prove generalization vaughts theorem effective borel hierarchy borel sets formed union complementation sets result says axiomatize effective sigma alpha effective alpha borel set computable infinitary sentence complexity result yields alternative proof vaughts theorem via forcing get version pull back theorem knight which says mit phi turing computable embedding subseteq mathop mod mathcal subseteq mathop mod mathcal computable infinitary sentence varphi language mathcal computable infinitary sentence varphi * mathcal mathcal mathcal models varphi * mit phi mathcal models varphi where varphi * has complexity varphi