En la teoría de la recursividad , la teoría matemática de la computabilidad , un conjunto máximo es un subconjunto A coinfinito recursivamente enumerable de los números naturales, de modo que por cada subconjunto B adicional recursivamente enumerable 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 da una definición fácil dentro del enrejado de los conjuntos enumerables recursivamente.
Los conjuntos máximos tienen muchas propiedades interesantes: son simples , hipersimple , hiperhipersimple y r-maximal; Esta última propiedad dice que cada conjunto recursivo R contiene ya sea sólo un número finito de elementos del complemento de A o casi todos los elementos del complemento de A . Hay conjuntos r-máximos que no son máximos; algunos de ellos ni siquiera tienen superconjuntos máximos. Myhill (1956) preguntó si existen conjuntos máximos y Friedberg (1958) construyó uno. Soare (1974) mostró que los conjuntos máximos forman una órbita con respecto al automorfismo de los conjuntos recursivamente enumerables bajo inclusión ( móduloconjuntos finitos). Por un lado, todo automorfismo mapea un conjunto máximo A con otro conjunto máximo B ; por otra parte, por cada dos conjuntos máximos A , B no es un automorfismo de los conjuntos recursivamente enumerables tal que A se asigna a B .
Referencias
- Friedberg, Richard M. (1958), "Tres teoremas sobre enumeración recursiva. I. Descomposición. II. Conjunto máximo. III. Enumeración sin duplicación", The Journal of Symbolic Logic , Association for Symbolic Logic, 23 (3): 309– 316, doi : 10.2307 / 2964290 , JSTOR 2.964.290 , MR 0109125
- Myhill, John (1956), "Solución de un problema de Tarski", The Journal of Symbolic Logic , Association for Symbolic Logic, 21 (1): 49–51, doi : 10.2307 / 2268485 , JSTOR 2268485 , MR 0075894
- H. Rogers, Jr., 1967. The Theory of Recursive Functions and Effective Computability , segunda edición 1987, MIT Press. ISBN 0-262-68052-1 ( tapa blanda), ISBN 0-07-053522-1 .
- Soare, Robert I. (1974), "Automorfismos de la red de conjuntos recursivamente enumerables. I. Conjuntos máximos", Annals of Mathematics , Second Series, Annals of Mathematics, 100 (1): 80-120, doi : 10.2307 / 1970842 , JSTOR 1970842 , MR 0360235