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.