Algoritmo o de la teoría de diagrama persiguiendo

Question

Uno de los componentes estándar de álgebra homológica es "diagrama de persecución", o equivalente argumentos con propiedades universales en abelian categorías. Hay una rigurosa teoría de diagrama de perseguir, e idealmente también un algoritmo?

Para ser precisos acerca de lo que quiero decir, un diagrama es un gráfico dirigido a $D$ cuyos vértices son etiquetados por los objetos en un abelian categoría, y cuyas flechas son etiquetados por morfismos. El diagrama puede tener varios triángulos, y podemos exigir que ciertos triángulos viajar, o anticommute. Podemos exigir que ciertas flechas que desaparecer, que puede ser utilizado para pedir que ciertas composiciones desaparecer. Podemos exigir que ciertas composiciones son exactas. Tal vez algunas de las flechas son sumas o directa sumas de otras flechas, y tal vez algunos de los vértices son proyectivos o inyectiva objetos. A continuación, un diagrama de "lema" es una construcción de otro diagrama de $D'$, con algunos de los nuevos objetos y flechas construido a partir de los de $D$, o al menos algunas de las nuevas restricciones.

Como descrito hasta ahora, el diagrama de $D$ puede expresar un functor de cualquier categoría $\mathcal{C}$ a la abelian categoría $\mathcal{A}$. Esto se ve demasiado general como para que una razonable algoritmo. Así que vamos a tomar el caso de que $D$ es acíclico y finito. Esto es demasiado general para producir una clasificación completa de diagrama de estructuras, ya que acíclicos diagramas de incluir a todos los acíclicos tiembla, y algunos de estos tienen un "salvaje" teoría de la representación. (Por ejemplo, tres flechas de $A$ $B$son un carcaj salvaje. Las representaciones de esta aljaba no son manejables, incluso el trabajo de más de un campo.) En este caso, no estoy pidiendo una clasificación completa, sólo en un restringido de la teoría algebraica que captura lo que se enseña como diagrama de perseguirla.

Tal vez las propiedades de un diagrama que he mencionado en el segundo párrafo ya dan salvajes de la teoría. Está bien para deshacerse de algunos de ellos como sea necesario para tener una fácil respuesta. O para restringir el acceso a la categoría de $\textbf{Vect}(k)$ si es necesario, aunque estoy interesado en una mayor generalidad que eso.

Para hacer una analogía, no es una teoría de la Mentira soporte palabras. Existe un algoritmo relacionados con Lyndon palabras que le dice cuando dos sumas de Mentira soporte palabras son formalmente iguales a través de la identidad de Jacobi. Esta es una respuesta satisfactoria, aunque no es una clasificación de los reales de álgebras de Lie. En el caso de los diagramas conmutativos, no sé razonable de un conjunto de axiomas — tal vez están relacionadas con las categorías trianguladas — mucho menos un algoritmo para caracterizar sus implicaciones formales.

(Esta pregunta fue inspirado por un mathoverflow pregunta acerca de George Bergman de la salamandra lema.)

---

David de referencia es muy interesante, y que podría ser una parte de lo que yo tenía en mente con mi pregunta, pero no es la parte principal. Mi pensamiento es el diagrama de perseguir es aburrido, y que lo ideal sería un algoritmo para obtener todos finito diagrama de perseguir a los argumentos, al menos en el acíclicos caso. Aquí es una simplificación de la cuestión que es totalmente riguroso.

Supongamos que el diagrama de $D$ es finito y acíclicos y que todos los pares de rutas de viaje, por lo que es equivalente a un functor a partir de un número finito de poset categoría $\mathcal{P}$ a la abelian categoría $\mathcal{A}$. Suponga que el único otras decoraciones de $D$ es que: (1) algunos flechas son el cero de morfismos, (2) ciertos vértices son el objeto de cero, y (3) algunos componibles pares de flechas son exactas. (En realidad, la condición 2 puede ser forzado por las condiciones 1 y 3.) Entonces existe un algoritmo para determinar todos los pares de flechas que se ven obligados, para ser exactos? Se puede hacer en el polinomio de tiempo?

Este riguroso simplificación no considera que muchas de las posibles características de los lemas en álgebra homológica. No se dice nada sobre proyectiva o inyectiva objetos, tomando núcleos y cokernels, tomando directamente las sumas de los objetos y morfismos (o, más generalmente, límites finitos y colimits), o hacer la conexión de morfismos. Por ejemplo, no incluye el lema de la serpiente. Asimismo, no se incluyen diagramas en los que sólo algunos pares de rutas de viaje. Pero es suficiente para expresar la monomorphism y epimorphism condiciones, por lo que incluye, por ejemplo, los cinco lema.

Answer 1

He aquí un intento, asumiendo la categoría de destino es finito dimensionales espacios vectoriales y el diagrama es finito acíclicos.

1) Llenar el diagrama por lo que es triangular (es decir, agregar las composiciones de todas las flechas). Agregar los granos y cokernels a cada flecha en el diagrama. Agregar el natural flechas entre estos nuevos objetos (por ejemplo, el núcleo de $f$ de los mapas en el núcleo de $g\circ f$). Repetir este proceso hasta que termina (que lo hace, ya que hay un número finito de flechas, y por lo tanto sólo un número finito de subquotients de objetos de inducir).

2) En este nuevo diagrama, el cómputo de toda la ruta exacta. (Este paso me parece que tienen un alto el tiempo y el espacio de la complejidad, por desgracia.) Por la ruta exacta, me refiero a una infinita largo de la secuencia exacta, para que todos, pero un número finito de objetos son cero.

3) Dada una ruta de acceso exacta $$0\to A_1\to \cdots \to A_i\to \cdots \to A_n\to 0$$ write the equation $$\sum_{i=1}^n (-1)^i \dim~ A_i=0.$$

4) Resolver el sistema lineal resultante de la $\dim~ A_i$'s.

Ya hemos añadido los núcleos y cokernels, resolviendo el sistema nos dice acerca de inyectividad y surjectivity de todas las flechas. Además, tal y como yo lo puede decir cualquier (no negativo) de la solución a este sistema lineal es realizable como un diagrama, por lo que este algoritmo nos da ninguna información que pudiera obtener por el diagrama de perseguirla.

---

Greg ha dado un buen resumen de este método en su respuesta a continuación: él me lleva a la tarea sobre mi afirmación de que cualquier entero no negativo, la solución a este sistema lineal es realizable, así que voy a esbozar un argumento (de nuevo que requiere el diagrama de ser finito acíclicos). También asumimos que el diagrama es "completa" en el sentido de que el paso 1) se ha completado.

Parcialmente la orden de los objetos en el diagrama diciendo $A\leq B$ fib $A$ es un subquotient de $B$; de manera inductiva, esto es lo mismo que decir que $B\leq B$ $A\leq B$ si existe $C\leq B$ tal que $A$ inyecta en $C$ o $C$ surjects en $A$ en este diagrama. Podemos identificar isomorfo objetos; este es un poset por acyclicity. Procedemos por inducción sobre el número de objetos en el diagrama. La de un diagrama de objetos es fácil, así que vamos a hacer la inducción de paso.

Por lo finito, el diagrama contiene una larga cadena; elegir una cadena y considerar su mínimo elemento $X$. Todos los mapas dentro o fuera de la $X$ son surjections o inyecciones, respectivamente, así split $X$ de descuento en todos los objetos que se asigna en ella o que se asigna a un sumando directo. El diagrama de con $X$ retirado hace la inducción de paso.

Answer 2

No estoy seguro de que esto es lo que están buscando, pero si usted mira Gelfand y Manin los Métodos de Álgebra Homológica, el final de la Sección II.5), hacen la siguiente definición:

Deje $Y$ ser objeto de un abelian categoría. Un elemento de $Y$ es un par $(X,h)$,$h: X \to Y$, el modulo de la relación de equivalencia que $(X,h) \sim (X',h')$ si podemos completar el cuadrado

$$\begin{matrix} Z & \to & X' \\ \downarrow & & \downarrow \\ X & \to & Y \end{matrix}$$

así que los mapas de $Z \to X$ $Z \to X'$ son surjective.

El mapa enviar un objeto, $Y$ a sus elementos, $E(Y)$, es claramente un functor de nuestro Abelian categoría a PointedSetsWithAnInvolution, donde el etiquetado de punto de $E(Y)$ es el cero mapa de $0 \to Y$ y la involución es $(X,h) \mapsto (X,-h)$. (Me parece que $(X,h)$ $(X,-h)$ siempre son equivalentes, pero G+M veces el uso de la notación que parece distinguir a los elementos $e$$-e$, así que estoy siguiendo.) Gelfand y Manin estado como ejercicios:

• Un mapa de $f: Y_1 \to Y_2$ es un monomorphism iff $E(f)^{-1}(0) =0$ fib $E(f)$ es inyectiva.
• Un mapa de $f: Y_1 \to Y_2$ es un epimorphism iff $E(f)$ es surjective.
• Un mapa de $f: Y_1 \to Y_2$ es cero iff $E(f)$ es cero.
• Una secuencia $Y_1 \to Y_2 \to Y_3$ es exacta iff, por $e \in E(Y_2)$, el elemento $e$ se toma el elemento $0 \in E(Y_3)$ si y sólo si está en la imagen de $E(Y_1)$.
• Si $y_1$$y_2 \in E(Y)$, entonces hay un elemento $z \in E(Y)$ tal que, para cualquier $f: Y \to Y'$$f(y_i)=0$,$f(z)=(-1)^i f(y_{1-i})$. Por otra parte, si $g: Y \to X$ es cualquier mapa tal que $g(y_1) = g(y_{2})$, podemos tomar $z$ tal que $g(z)=0$. (Por lo $z$ actúa como $y-y'$. Tenga en cuenta que no hay demanda para ser una única $z$ que funciona.)

G y M, a continuación, dar varios ejemplos para demostrar que la mayoría de diagrama de perseguir a los argumentos pueden ser rewrittten el uso de la $E$ en la construcción.

Answer 3

Esta respuesta es una respuesta a Daniel Litt la respuesta anterior. En primer lugar, permítanme destilar su punto. Dado un diagrama de finito-dimensional espacios vectoriales, cada plazo $A$ tiene una dimensión que es un número entero no negativo. Además, todos los morfismos $f:A \to B$ tiene un no-negativos rango que es en la mayoría de las $\min(\dim A,\dim B)$. Si en un par de morfismos $$A \stackrel{f}{\longrightarrow} B \stackrel{g}{\longrightarrow} C,$$ a continuación, obtener una relación lineal $$\mathrm{rank}\ f + \mathrm{rank}\ g = \dim B.$$ Por lo tanto, no es un número entero de un problema de programación para expresar si las dimensiones y rangos son factibles. Puesto que un número entero de un problema de programación es homogénea, usted puede en lugar de tratarlo como un ser racional problema de programación lineal y más tarde borrar de denominadores. Existe un algoritmo para determinar la viabilidad, incluso un polinomio de tiempo del algoritmo. Como Daniel señala, esto es suficiente para establecer el nueve lema en el caso especial de finito-dimensional espacios vectoriales. El argumento/algoritmo funciona incluso en muchas otras categorías que finito-dimensional espacios vectoriales. Por ejemplo funciona para finitos abelian grupos. Por otro lado, el algoritmo no utilice el hecho de que todos los polígonos en el diagrama conmuta (ver más abajo), exceptuando, tal vez, un preprocesamiento de la etapa en la que conmutativa polígonos que son llenadas por los conmutativa triángulos.

Como yo, Daniel le pidió a restringir a acíclicos diagramas. Sin embargo, me di cuenta de que esta restricción es ineficaz para mi toda la pregunta. (Por lo tanto, su algoritmo no es necesaria). Usted puede convertir cualquier diagrama en un acíclicos uno con el hecho de que $$0 \longrightarrow A \stackrel{\phi}{\longrightarrow} A' \longrightarrow 0$$ hace $\phi$ en un isomorfismo. Si $\mathcal{D}$ es un diagrama, usted debe primero triangular todos conmutativa polígonos en hacer conmutativa triángulos. Y luego hacer tres copias $A, A', A''$ de cada objeto $A \in \mathcal{D}$ junto con isomorphisms $$A \stackrel{\phi}{\longrightarrow} A' \stackrel{\phi'}{\longrightarrow} A'.$$ A continuación, un homomorphism $f:A \to B$ $\mathcal{D}$ puede ser expresado acyclically como este conmutativa de la plaza: $$\begin{matrix} A & \stackrel{f}{\longrightarrow} & B' \\ \downarrow && \downarrow \\ A' & \stackrel{f'}{\longrightarrow} & B'' \end{de la matriz}$$ Finalmente, un conmutativa triángulo $h = f \circ g$ puede ser expresado como un conmutativa plaza de $h' \circ \phi = f' \circ g$. O si $f$ $g$ son una pareja exacta, se puede requerir que $f'$ $g$ hacer una pareja exacta.

Daniel dice también sin explicación de que, si hay una solución a la dimensión y rango de ecuaciones, entonces hay maneras de rellenar todos los mapas. Pero sin un trabajo mucho más, no creo que esta inferencia es razonable. La parte difícil es satisfacer conmutativa triángulos. Ciertamente, no es cierto que no es simplemente una elección canónica para cada mapa mediante un esqueleto $\{k^n\}$ de la categoría de finito-dimensional espacios vectoriales. Porque, si $f$ $g$ cada uno tiene algún valor, entonces su composición $f \circ g$ también podría tener algún rango deseado, y que la clasificación depende de las decisiones de $f$$g$. Una interesante señalar aquí es que $$\mathrm{rank}\ f \circ g \le \min(\mathrm{rank}\ f,\mathrm{rank}\ g),$$ y hay una similar a la desigualdad en el otro lado. Sin embargo, creo que hay más cosas que eso.

Por último, vale la pena dar un simple ejemplo para mostrar que la viabilidad en lo finito-dimensional espacios vectoriales no es la misma como la viabilidad en espacios vectoriales. Dada la secuencia exacta $$0 \longrightarrow A \longrightarrow A \longrightarrow A \longrightarrow 0,$$ se puede concluir (el uso de la dimensión de ecuaciones que Daniel sugiere) que $A = 0$ si es finito-dimensional. Pero si es infinito-dimensional, entonces hay soluciones no triviales.

Answer 4

Este fue originalmente iba a ser un lugar diferente post, pero me di cuenta de que mi argumento podría ser adaptado a una (ineficaz) el algoritmo, si es posible reparar el agujero. Al menos, debo decir algunas cosas que puede ser obvio, pero no era para mí hasta que lo vi, y por lo tanto podría no ser obvio para alguien más.

Vamos a arreglar el abelian categoría a la categoría de finito-dimensional espacios vectoriales sobre GF(2). Hemos decorado el diagrama de tipo de Greg describe. Entonces es fácil ver que el no-exactitud que se puede componer de dos flechas en RE ... podemos tener un armario sólo nos dan un contraejemplo, y puesto que todo es finito-dimensional, estamos bien. Así que el "diagrama de perseguir decisión problema" está en el núcleo.

Si pudiéramos efectivamente vinculado a las dimensiones de los espacios vectoriales en un contraejemplo, por supuesto, tendríamos que el problema era recursiva. Al menos para un finito-dimensional espacios vectoriales sobre un campo finito. Pero no sé cómo esto es posible. Mi pregunta: ¿es posible evitar la necesidad de un eficaz vinculado de alguna manera? Creo que usted puede conseguir una complejidad de la teoría de la mejora de dejar el armario de calcular todo como una "caja negra" y "la comprobación de la honestidad" en la logarítmica del tamaño de subespacios, pero puede ser que sea misremembering. Hay algunos extraordinariamente inteligente manera de hacer algo como esto para la computabilidad? (Estoy pensando en los resultados como el collar de la reconstrucción problema, o el problema de B6 en este año del examen Putnam, aunque en ambos casos el uniforme "obligado" se esconde una gran cantidad de información que no parece tener en cualquier lugar de ir en este escenario...)

En realidad, supongo que realmente el único escenario que preocuparse sería si las dimensiones en el más pequeño de contraejemplo a la exactitud de algunos par creció más rápido que cualquier computable en función del tamaño del diagrama, haga? En caso contrario, tenemos que el problema está en co-NSPACE(BigFunction(n)), y así es en NSPACE(BigFunction(n)). Que tipo de tasa de crecimiento parece inverosímil, pero de nuevo no tengo idea de cómo probar que es imposible.