index set theorem

Index Set Theorem: If A is an index setMathworldPlanetmathPlanetmath and A,ω, then either K1A or K1A.

In the statement of the theorem, K is the halting set {x:φx(x)converges}, 1 is the one-one reducibility (or 1-reducibility) relation symbol, and A stands for the complement of the set A (relative to ω).

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