Conjunto máximo

En la teoría de la recursión , la teoría matemática de la computabilidad , un conjunto maximal es un subconjunto A recursivamente enumerable y cofinito de los números naturales tal que para cada subconjunto recursivamente enumerable B adicional de los números naturales, B es cofinito o B es una variante finita de A o B no es un superconjunto de A. Esto proporciona una definición fácil dentro de la red de los conjuntos recursivamente enumerables.

Los conjuntos maximales tienen muchas propiedades interesantes: son simples , hipersimples , hiperhipersimples y r-maximales; la última propiedad dice que cada conjunto recursivo R contiene o bien sólo un número finito de elementos del complemento de A o bien casi todos los elementos del complemento de A. Hay conjuntos r-maximales que no son maximales; algunos de ellos ni siquiera tienen superconjuntos maximales. Myhill (1956) preguntó si existían conjuntos maximales y Friedberg (1958) construyó uno. Soare (1974) mostró que los conjuntos maximales forman una órbita con respecto al automorfismo de los conjuntos recursivamente enumerables bajo inclusión ( conjuntos módulo finitos). Por un lado, cada automorfismo asigna un conjunto maximal A a otro conjunto maximal B ; por otro lado, para cada dos conjuntos maximales A , B hay un automorfismo de los conjuntos recursivamente enumerables tal que A se asigna a B.

• Friedberg, Richard M. (1958), "Tres teoremas sobre la enumeración recursiva. I. Descomposición. II. Conjunto máximo. III. Enumeración sin duplicación", The Journal of Symbolic Logic , 23 (3), Association for Symbolic Logic: 309–316, doi :10.2307/2964290, JSTOR  2964290, MR  0109125, S2CID  25834814
• Myhill, John (1956), "Solución de un problema de Tarski", The Journal of Symbolic Logic , 21 (1), Association for Symbolic Logic: 49–51, doi :10.2307/2268485, JSTOR  2268485, MR  0075894, S2CID  19695459
• H. Rogers, Jr., 1967. La teoría de funciones recursivas y computabilidad efectiva , segunda edición, 1987, MIT Press. ISBN 0-262-68052-1 (libro de bolsillo), ISBN 0-07-053522-1 .  
• Soare, Robert I. (1974), "Automorfismos de la red de conjuntos recursivamente enumerables. I. Conjuntos maximales", Anales de Matemáticas , Segunda serie, 100 (1), Anales de Matemáticas: 80–120, doi :10.2307/1970842, JSTOR  1970842, MR  0360235