Conjunto enumerado

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 26 de mayo de 2021; las comprobaciones requieren 7 ediciones .

Un conjunto enumerable ( efectivamente enumerable , recursivamente enumerable , semidecidible [1] ) es un conjunto de objetos constructivos (por ejemplo, números naturales ), cuyos elementos pueden obtenerse utilizando algún algoritmo . El complemento de un conjunto enumerable se llama corecursivamente enumerable [2] . Todo conjunto enumerable es aritmético . Un conjunto enumerable correcursivamente puede no ser enumerable, pero siempre es aritmético. Los conjuntos enumerados corresponden al nivel jerarquía

Todo conjunto soluble es enumerable. Un conjunto enumerable es decidible si y solo si su complemento también es enumerable. En otras palabras, un conjunto es decidible si y sólo si es enumerable y correcursivamente enumerable. Un subconjunto de un conjunto enumerable puede no ser enumerable (y puede que ni siquiera sea aritmético).

El conjunto de todos los subconjuntos enumerables es un conjunto contable , y el conjunto de todos los subconjuntos no enumerables  es incontable .

Variantes de definición

Distintas formalizaciones del concepto de algoritmo corresponden a distintas definiciones formales del concepto de conjunto enumerable, que resultan ser equivalentes. Por lo tanto, según el concepto de función recursiva , los conjuntos enumerables de números naturales se pueden definir como imágenes de funciones parcialmente recursivas de una variable (por lo tanto, los conjuntos enumerables de números naturales a veces se denominan "conjuntos recursivamente enumerables"). De manera similar, los conjuntos enumerables de palabras en algún alfabeto A pueden introducirse como conjuntos de salidas de máquinas de Turing con alfabeto externo A , o como conjuntos de palabras en el alfabeto A de salidas de algoritmos normales en el alfabeto A.

En la teoría de los algoritmos , se demuestra la afirmación de que los conjuntos enumerables, y solo los conjuntos enumerables, pueden servir como dominios de los algoritmos. Esto nos permite introducir otra forma equivalente de definir el concepto de conjunto enumerable. Por lo tanto, los conjuntos enumerables de números naturales pueden considerarse rangos de funciones recursivas, conjuntos de palabras, áreas de aplicabilidad de las máquinas de Turing o algoritmos normales con los alfabetos correspondientes.

Ejemplos

• El conjunto vacío es enumerable.
• Cualquier conjunto decidible (en particular, cualquier conjunto finito ) es enumerable.
• El conjunto de números de las máquinas de Turing que se detienen en una entrada vacía también es enumerable (aunque no decidible , ya que su complemento no es enumerable).
• La proyección de un conjunto enumerable es enumerable.
• La unión y la intersección de un número finito de conjuntos enumerables también son enumerables.
• El conjunto de números naturales cuya notación decimal aparece como una subcadena en la notación decimal del número π es enumerable, y si π es normal , incluso trivialmente solucionable (el conjunto completo de números naturales).
• El conjunto de números racionales menores que la constante Ω de Khaitin es enumerable pero no decidible.
• Pero el conjunto de números racionales mayores que la constante Ω de Khaitin no es enumerable (aunque es enumerable aritmética y correcursivamente).
• El conjunto de proposiciones demostrables en aritmética de primer orden es enumerable.
• Pero el conjunto de enunciados verdaderos en la aritmética de primer orden no es enumerable ni correcursivamente enumerable (y ni siquiera es aritmética, lo que constituye la afirmación del teorema de Tarski sobre la inexpresabilidad de la verdad en la aritmética).

Diofántico

Cualquier conjunto enumerable de números enteros (o tuplas de números enteros) tiene una representación Diofántica , es decir, es una proyección del conjunto de todas las soluciones de alguna ecuación algebraica Diofántica.

Esto significa, en particular, que cualquier conjunto enumerable coincide con el conjunto de valores positivos tomados para parámetros enteros por algún polinomio con coeficientes enteros. Este resultado fue establecido por Yuri Matiyasevich .

Véase también

• conjunto inmune

Notas

1. ↑ A. E. Pentus, M. R. Pentus, Teoría matemática de los lenguajes formales, Conferencia 14: Problemas algorítmicos // Intuit.ru, 09/07/2007
2. ↑ Barwise, Kenneth John. Libro de referencia sobre lógica matemática. Parte 3: teoría de la recursión. — M .: Nauka, 1982.

Literatura

• Rogers H. Teoría  de funciones recursivas y computabilidad efectiva: [trad. del  ingles ] / ed. V. A. Uspensky: per. De inglés. V. A. Dushsky, M. I. Kanovich, E. Yu. Nogina. — M  .: Mir, 1972.