En la teoría de la computabilidad , hay una serie de teoremas básicos . Estos teoremas muestran que determinados tipos de conjuntos siempre deben tener algunos miembros que, en términos del grado de Turing , no sean demasiado complicados. Una familia de teoremas básicos se refiere a los conjuntos efectivamente cerrados no vacíos (es decir, conjuntos no vacíos en la jerarquía aritmética ); estos teoremas se estudian como parte de la teoría clásica de la computabilidad. Otra familia de teoremas básicos se refiere a los conjuntos analíticos lightface no vacíos (es decir, en la jerarquía analítica ); estos teoremas se estudian como parte de la teoría hiperaritmética .
Los conjuntos efectivamente cerrados son un tema de estudio en la teoría clásica de la computabilidad. Un conjunto efectivamente cerrado es el conjunto de todos los caminos a través de algún subárbol computable del árbol binario . Estos conjuntos son cerrados, en el sentido topológico , como subconjuntos del espacio de Cantor , y el complemento de un conjunto efectivamente cerrado es un conjunto efectivamente abierto en el sentido de espacios polacos efectivos . Kleene demostró en 1952 que existe un conjunto no vacío, efectivamente cerrado sin ningún punto computable (Cooper 1999, p. 134). Los teoremas de base muestran que debe haber puntos que no estén "demasiado lejos" de ser computables, en un sentido informal.
Una clase es una base para conjuntos efectivamente cerrados si cada conjunto efectivamente cerrado no vacío incluye un miembro de (Cooper 2003, p. 329). Los teoremas de base muestran que clases particulares son bases en este sentido. Estos teoremas incluyen (Cooper 1999, p. 134):
Aquí, un conjunto es bajo si su salto de Turing , el grado del problema de detención , tiene grado hiperinmune libre si cada función computable total está dominada por una función computable total (es decir, para todos ).
No se pueden combinar dos de los tres teoremas anteriores para el conjunto de compleciones consistentes de PA (o solo EFA ; los grados de Turing son los mismos). El único grado de Turing que calcula una compleción consistente de PA es 0'. Sin embargo, el teorema de base baja y el teorema de base libre hiperinmune se pueden combinar con la evitación del cono, es decir, para cada X no computable , podemos elegir un miembro (como en el teorema) que no calcule X. Los teoremas también relativizan por encima de un real arbitrario.
También existen teoremas de base para conjuntos de caras claras. Estos teoremas de base se estudian como parte de la teoría hiperaritmética . Un teorema es el teorema de base de Gandy, que es análogo al teorema de base baja. El teorema de base de Gandy muestra que cada conjunto no vacío tiene un elemento que es hiperaritméticamente bajo, es decir, su hipersalto tiene el mismo hipergrado (y para el teorema, incluso el mismo grado de Turing) que el conjunto de Kleene .
