En la teoría de la computabilidad, el teorema del isomorfismo de Myhill , llamado así por John Myhill , proporciona una caracterización de dos numeraciones para inducir la misma noción de computabilidad en un conjunto.
Teorema del isomorfismo de Myhill
Conjuntos A y B de los números naturales se dice que son de forma recursiva isomorfo si hay un total de computable biyección f entre el conjunto de números naturales a sí mismo de tal manera que f ( A ) = B .
Se dice que un conjunto A de números naturales es uno a uno reducible a un conjunto B si hay una inyección computable total [ desambiguación necesaria ] f en los números naturales tal que y .
Isomorfismo de Myhill teorema afirma que dos conjuntos A y B de los números naturales son recurrentemente isomorfos si y sólo si A es una reducible a B y B es uno reducible a una .
El teorema recuerda al teorema de Schroeder-Bernstein . Sin embargo, la prueba es diferente. La demostración de Schroeder-Bernstein usa las inversas de las dos inyecciones, lo cual es imposible en el marco del teorema de Myhill ya que estas inversas podrían no ser recursivas. La demostración del teorema de Myhill, por otro lado, define la biyección inductivamente, lo cual es imposible en el contexto de Schroeder-Bernstein a menos que se utilice el axioma de elección (que no es necesario para la demostración).
Un corolario del teorema de Myhill es que dos numeraciones totales son uno equivalente si y solo si son computablemente isomórficas .
Ver también
- Conjetura de Berman-Hartmanis , un enunciado análogo en la teoría de la complejidad computacional
Referencias
- Myhill, John (1955), "Conjuntos creativos", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik , 1 : 97–108, doi : 10.1002 / malq.19550010205 , MR 0071379.
- Rogers, Hartley, Jr. (1987), Teoría de funciones recursivas y computabilidad efectiva (2a ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.