index set theorem

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

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

Title	index set theorem
Canonical name	IndexSetTheorem
Date of creation	2013-03-22 18:09:51
Last modified on	2013-03-22 18:09:51
Owner	yesitis (13730)
Last modified by	yesitis (13730)
Numerical id	5
Author	yesitis (13730)
Entry type	Theorem
Classification	msc 03D25