Es la teoría de categorías decidable?

Question

Hay una gran cantidad de teoremas básicos del álgebra homológica, tales como los cinco lema o el lema de la serpiente, que parece que sería más fácil de probar por ordenador que a mano. Esto me llevó a considerar la siguiente pregunta: ¿ es la teoría de categorías decidable?

Más específicamente, me preguntaba si o no declaraciones acerca de abelian categorías puede ser determinado de verdadero o falso en tiempo finito. También, si puede ser determinado a ser falsa, no es posible describir explícitamente un contraejemplo? Si se sabe que se decidable, se sabe algo de la complejidad? (Otros decidable teorías a menudo tienen multiplicación exponencial de tiempo complejidades.) Si se sabe que es indecidible, decir mediante la incorporación de la detención problema, entonces puedo cambiar mi hipótesis un poco y hacer decidable? (Por ejemplo, tal vez yo no debería estar buscando en abelian categorías, después de todo.)

Gracias de antemano.

Edit: parece Que una es necesaria una aclaración. Mi objetivo era estudiar la teoría mínima que podía estado de cosas como los cinco lema, pero no necesariamente prueba. Por ejemplo, quiero decir:

Si en un abelian categoría, usted tiene un montón de mapas de $0\to A \to B \to C\to 0$ $0\to A' \to B' \to C'\to 0$ que hacer dos breves secuencias exactas y algunos mapas más $a:A\to A'$, $b:B\to B'$, $c:C\to C'$ que conmuta con los mapas anteriores, y $a$ $c$ son isomorphisms, a continuación, $b$ es un isomorfismo.

Las sentencias de esta forma sería entradas para un programa, el cual decide si esta declaración es la verdad en ZFC (o su favorito otros axiomatization de la categoría de la teoría). El punto aquí es que yo soy la restricción de las penas uno puede introducir en el programa, pero manteniendo ZFC o lo que sea como mi marco.

Yo esperaba (tal vez ingenuamente) que si me restringido a la clase de oraciones, podría ser decidable si o no estas declaraciones eran verdad. Por ejemplo, yo me imaginaba que todo teorema es probado por el diagrama de perseguir, o es posible encontrar un ejemplo concreto de los mapas de entre, digamos, R-módulos que se contradicen con el resultado.

Answer 1

Gracias por aclarar tu pregunta. La formulación que usted y Dorais dar parece perfectamente razonable. Usted tiene un de primer orden lenguaje para la categoría de teoría, donde se puede cuantificar sobre los objetos y morfismos, usted puede componer morfismos de manera adecuada y se puede expresar que un determinado objeto es la inicial o terminal de objetos de un determinado morfismos. En este lenguaje, se puede describir de varias finito diagramas, expresar si son o no son conmutativas, y así sucesivamente. En particular, se puede expresar que la composición es asociativa, etc. y describir lo que significa ser un la categoría de esta manera.

La pregunta ahora es: ¿es esta la teoría decidable? En otras palabras, hay una computable procedimiento para determinar, dada una afirmación en este idioma, si se tiene en todas las categorías?

La respuesta es No.

Una forma de ver esto es para mostrar aún más: ni siquiera se puede decidir si un enunciado es verdadero es verdadero en todos los categorías tener un solo objeto. La razón es que el grupo de la teoría no es un decidable teoría. No es computable procedimiento para determinar si una sentencia dada en el de primer orden lenguaje de la teoría de grupos es cierto en todos los grupos. Pero el punto de categorías incluyen, naturalmente, todos los grupos (y que podemos definir en una sola instrucción en la categoría de la teoría del lenguaje exactamente lo que se necesita para la colección de morfismos en que el objeto a ser un grupo). Por lo tanto, si pudiéramos decidir categoría de teoría, entonces podríamos decidir las traducciones de la teoría de grupos de preguntas en categoría de la teoría, y que sería capaz de decidir en grupo la teoría, que no se puede. Contradicción.

El obstáculo fundamental para decidability aquí, como yo mencioné en mi respuesta anterior (véase la edición de la historia), el capacidad para codificar la aritmética. La noción de un fuertemente indecidible estructura es la clave para probar la existencia de varias teorías son indecidible. Un fuertemente indecidible teoría es un finitely axiomatizable la teoría, de tal manera que ninguna teoría consistente con lo que se indecidible. Robinson demostró que existe una fuerte indecidible de la teoría de la aritmética, conocido como Robinson P. Un fuertemente indecidible estructura es una estructura de modelado de un fuertemente indecidible de la teoría. Estas estructuras son increíbles, para cualquier teoría de la verdad en un fuertemente indecidible estructura es indecidible. Por ejemplo, el modelo estándar de la aritmética, que satisface P, es fuertemente indecidible. Si es fuertemente indecidible e interpretado en B, entonces se sigue que B también es fuertemente indecidible. Por lo tanto, podemos probar que la teoría de grafos es indecidible, que el anillo de la teoría es indecidible y que la teoría de grupos es indecidible, simplemente por encontrar un gráfico, un anillo o un grupo en el que el natural los números se interpreta. Tarski encuentra fuertemente indecidible grupo, a saber, el grupo G de las permutaciones de los números enteros Z. es fuertemente indecidible porque los números naturales puede ser interpretado en este grupo. Básicamente, el número n está representado por la traducción-por-n. Uno puede identificar la colección de traducciones, exactamente como aquellos que se desplazan con s = traducción-por-1. Entonces, se puede definir además como composición (es decir, la suma de los exponentes) y la divide la relación está definida por: i divide j iff nada que desplazamientos con s^yo también desplazamientos con s^j. Y así sucesivamente.

Yo reclamo del mismo modo que no es fuertemente indecidible categoría. Esto es casi inmediata, ya que cada grupo puede ser visto como el morfismos de una categoría de objeto, y el grupo se interpreta como el morfismos de esta categoría. Por lo tanto, la categoría interpreta el fuertemente indecidible grupo, y así, la categoría también es fuertemente indecidible. En en particular, cualquier teoría de la verdad en la categoría también es indecidible. Para la categoría de teoría en sí misma, es indecidible.

Answer 2

Esta respuesta se basa en las de F. G. Dorais y Joel David Hamkins para responder a tu "pregunta", la pregunta queda abierta por ellos, es decir, si la teoría de abelian categorías es decidable.

La respuesta es que todavía no.

Incluso la siguiente más limitado de la familia de los problemas es indecidible:

Palabras $r, r_1,\ldots,r_m$ $x_1,\ldots,x_n$ (es decir, cada una de las $r_i$ es un producto finito de la $x_i$ y sus inversas), decidir si es cierto que cada vez que el $x_i$ son interpretados como automorfismos de un objeto $M$ en un abelian categoría, $r_1=\cdots=r_m=1_M$ implica $r=1_M$.

Si la respuesta a la instancia correspondiente de la palabra problema para finitely presentan grupos es sí, entonces la respuesta a esta abelian categoría pregunta es sí. Por el contrario si la respuesta a la palabra problema instancia es no, entonces podemos construir la finitely presentó el grupo de $G = \langle x_1,\ldots,x_n | r_1,\ldots,r_m \rangle$, de forma que el anillo de grupo $\mathbb{Z}G$, y deje $M$ $\mathbb{Z}G$ como un módulo más de sí mismo, lo que demuestra que la respuesta a la abelian categoría pregunta es que no.

Así que si hay un algoritmo para decidir esta familia de abelian categoría de problemas, habría también un algoritmo para decidir la palabra problema para finitely presentan grupos. Pero el P. S. Novikov demostrado en 1955 que el último algoritmo no existe.

Answer 3

La teoría de categorías es indecidible. Por la teoría de categorías me refiero a la teoría con dos tipos de Obstetricia (objetos) y Ar (flechas), junto con las operaciones dom:Ar → Ob, cod:Ar → Ob, 1:Ob → Ar y o:Ar×Ar→Ar (posiblemente parcial de la composición), y la evidente axiomas.

Una forma de ver esto es para interpretar la teoría de grupos — que es indecidible por un hermoso teorema de Trakhtenbrot — dentro de la teoría de la punta de categorías, que es categorías con un distinguido objeto * (que es un secundario de extensión). De hecho, la definibles por el conjunto de invertible flechas de * a * formar un grupo, y cada grupo puede ser interpretado como el conjunto de flechas en una categoría con * como su único objeto. Sospecho que la teoría de Abelian categorías no es decidable bien, pero no he tratado de demostrar que (todavía).