Me gustaría saber cuál es la verdadera diferencia entre el topos recursivo (en el sentido de Mulry) y el topos efectivo (en el sentido de Hyland). Especialmente lo relacionado con las funciones recursivas. ¿Tienen el mismo poder semántico? Agradeceré algunas pistas sobre textos relacionados con esto.
Gracias de antemano.
PD: No doy definiciones por su gran extensión, pero podría darlas si alguien quiere.
Tu pregunta es un poco confusa, pero una diferencia obvia entre estas dos topos es que el topos recursivo es un topos de gavillas, por lo tanto cocompleto, mientras que el topos efectivo sólo tiene coproductos finitos (no triviales). Por ejemplo, el objeto de los números naturales en el topos efectivo es no un coproducto contable de 1's.
Si se busca una explicación más profunda, tal vez sea justo decir que el topos recursivo modela la computabilidad a la manera de Banach-Mazur (un mapa es computable si lleva secuencias computables a secuencias computables) y el topos efectivo modela la computabilidad a la manera de Kleene (un mapa es computable si es realizado por una máquina de Turing). En muchos aspectos, la noción de computabilidad de Kleene es mejor, pero tendrás que hacer otra pregunta para saber por qué :-)
Lo que sé es que en ambos topos se pueden representar funciones recursivas. El problema para mí es: aunque en Eff es bastante fácil ver cómo se hace (porque la realizabilidad recursiva es un concepto bastante fácil) en Rec todo es más difícil. Una de las razones es que los documentos de Mulry son más difíciles de encontrar que los de Hyland. Por eso pido referencias (abiertas y gratuitas). Al mismo tiempo me gustaría unirme a la pregunta de Krishnaswami aquí:mathoverflow.net/questions/21947/... hecha después de la mía. Gracias, A. Bauer, y... ¿tienes los documentos clave de Mulry?
Soy consciente de que estoy respondiendo a una pregunta antigua, pero para completar MathOverflow, me gustaría señalar que La tesis de G. Rosolini de 1986 "Continuidad y eficacia en los topoi" contiene (capítulo 6) una descripción de los topoi efectivos y recursivos, y una comparación de los mismos mediante la construcción de un functor de los efectivos a los recursivos (preservando límites, coproductos finitos, imágenes y el objeto número natural, fieles en la subcategoría completa de objetos contables y completos y fieles en la subcategoría completa de objetos separados contables). Según el autor, "la principal diferencia entre el topos efectivo y el topos recursivo es que el [objeto número natural] en [el topos efectivo] no no generan el topos", y el functor lleva un objeto del topos efectivo al conjunto de mapas del objeto números naturales a él, que puede verse como un objeto del topos recursivo.
Por lo que sé (corregidme si me equivoco, por favor):
1 El topos recursivo fue introducido en "The topos of recursive sets", Tesis, Buffalo, 1980. Se trata de $Rec=Sh_{J}(Set^{M^{op}})$ donde:
-M es el monoide de funciones recursivas totales en $\mathbb{N}$
-Sh se relaciona con las poleas
-J es la topología canónica de Grothendieck
Hay que tomar algunos ideales y pullbacks concretos para tener una representación de las funciones recursivas parciales a través de Rec.
2 Para el topos efectivo (introducido por Hyland en "The Effective Topos", Cambridge, 1982) podría sugerir "An introduction to fibrations, the effective topos and modest sets" de W. Phoa y una explicación más breve en: http://xorshammer.com/2008/10/13/what-would-the-world-look-like-if-everything-was-computable-an-introduction-to-hylands-effective-topos/
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
Le agradecería una definición si no le importa demasiado. Gracias por ofrecerla.
0 votos
Bien. Dame un tiempo.
1 votos
Los topos no son equivalentes. ¿Puede ser un poco más específico sobre el tipo de diferencia que le gustaría escuchar? ¿En términos de sus propiedades categóricas? ¿En términos de su lenguaje interno? ¿Para qué quiere utilizar estas topos?