Conjunto solucionable

Un conjunto solucionable (también recursivo , computable ) es un conjunto de números naturales para los que existe un algoritmo que recibe cualquier número natural como entrada y, después de un número finito de pasos, termina por determinar si pertenece a ese conjunto. En otras palabras, un conjunto es decidible si su función característica es computable . Un conjunto que no es soluble se llama indecidible . También se puede hablar de un conjunto solucionable que consta de cualquier objeto constructivo codificado por números naturales. Todo conjunto decidible es enumerable y aritmético . Los conjuntos resolubles corresponden al nivel de la jerarquía aritmética . ${\ estilo de visualización \ Delta _ {1} ^ {0}}$

En el caso general, un subconjunto del conjunto de elementos constructivos se llama decidible con respecto a , si existe un algoritmo que se puede aplicar a objetos de y, si se aplica a algún objeto , que responda a la pregunta de si ese objeto pertenece [ 1] . ${\mathfrak{M}}_{1}$ ${\mathfrak{M}}_{2}$ ${\mathfrak{M}}_{2}$ ${\mathfrak{M}}_{2}$ ${\mathfrak{M}}_{2}$ ${\mathfrak{M}}_{1}$

Hay conjuntos enumerables que no son decidibles. Además, un conjunto enumerable es decidible si y solo si su complemento también es enumerable. La proyección de un conjunto decidible es enumerable, pero puede no ser decidible. Un subconjunto de un conjunto decidible puede no ser decidible (y puede que ni siquiera sea aritmético).

El conjunto de todos los subconjuntos solubles es contable , y el conjunto de todos los subconjuntos irresolubles es incontable , ya que el conjunto de todos los subconjuntos de enteros positivos es incontable. [2] $\matemáticas {N}$ $\matemáticas {N}$ ${\ estilo de visualización 2^{P}}$

Existe una correspondencia biunívoca entre los subconjuntos computables y los números reales computables [2] . $S\subconjunto P$ ${\ estilo de visualización x \ en [0,1]}$

Ejemplos

El conjunto vacío es decidible.
Cualquier conjunto finito y su complemento son conjuntos solubles.
Hay infinitos conjuntos resolubles con complemento infinito. Por ejemplo, el conjunto de todos los números pares y el conjunto de todos los números primos son solucionables.
El complemento de un conjunto decidible es decidible.
La unión y la intersección de un número finito de conjuntos solubles también son solubles.
Todo conjunto enumerable cuyo complemento también es enumerable es decidible ( teorema de Post ).
El conjunto de los números racionales menores $\Pi$ que , es resoluble.
Un conjunto cuyo único elemento es igual a uno si la hipótesis de Riemann es verdadera, y cero en caso contrario, es decidible (porque es finito).
El conjunto de números de ceros no triviales de la función ζ , para los que se viola la hipótesis de Riemann , es decidible (aunque no se sabe si es vacío, finito o infinito).
El conjunto de cadenas que son pruebas válidas en ZFC es decidible. Su proyección -el conjunto de sentencias demostrables en ZFC- es enumerable, pero, bajo la condición de que ZFC sea consistente , es indecidible.

Notas

↑ Ebbinhouse, 1972 , pág. 19
↑ 1 2 Birkhoff G. , Barty T. Álgebra aplicada moderna. - M., Mir, 1976. - pág. 375-376

Literatura

Ebbinhaus GD, Jacobs K., Man FK, Hermes G. Máquinas de Turing y funciones recursivas. — M .: Mir, 1972. — 262 p.