# index set theorem

Index Set Theorem: If $A$ is an index set and $A\neq\varnothing,\omega$, then either $K\leq_{1}A$ or $K\leq_{1}A^{\complement}$.

In the statement of the theorem, $K$ is the halting set $\{x:\varphi_{x}(x)\>converges\}$, $\leq_{1}$ is the one-one reducibility (or 1-reducibility) relation symbol, and $A^{\complement}$ stands for the complement of the set $A$ (relative to $\omega$).

Title index set theorem IndexSetTheorem 2013-03-22 18:09:51 2013-03-22 18:09:51 yesitis (13730) yesitis (13730) 5 yesitis (13730) Theorem msc 03D25