# 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 |