¿Pullbacks y pushouts en la categoría de dígrafos?

Question

Por definición de la categoría de los bigramas es:

• Los objetos son endomorphisms de la categoría $\mathbf{Rel}$ (que se establece equipado con una relación binaria en ese conjunto).
• Morfismos de un objeto $\mu$ a un objeto $\nu$ discretamente funciones continuas, que es de las funciones de $f$ tal que $f\circ\mu\subseteq\nu\circ f$. (Esta fórmula es equivalente a $\mu\subseteq f^{-1}\circ\nu\circ f$$f\circ\mu\circ f^{-1}\subseteq\nu$.)
• La composición es la composición de funciones.

Me han demostrado que en categorías como este todos los productos pequeños y pequeñas que se co-productos están definidos.

Para demostrar que esta categoría es (co)completa permanece para mostrar la existencia de pullbacks y pushouts.

Por favor me ayudan a examinar la existencia de pullbacks y pushouts en la categoría de los bigramas.

Answer 1

Dado que podría ser de interés para porton o de otros, voy a ampliar mi comentario anterior, que la categoría de los bigramas es en realidad un Grothendieck quasitopos. Por lo tanto no es la única completa y cocomplete, también es localmente cartesiana cerrada, entre otras cosas.

En primer lugar, recordemos que la categoría de 'multigraphs' $\mathbf{Gph}$ (como en Tom Hirschowitz la respuesta) es el topos de presheaves $G^{op} \to \mathbf{Set}$ en la categoría

$$G = (0 \stackrel{\overset{s}{\longrightarrow}}{\underset{t}{\longrightarrow}} 1).$$

Entonces, yo reclamo que la inclusión $i: \mathbf{Dig} \to \mathbf{Gph}$ en la de Tom respuesta es la misma que la inclusión de separados presheaves para el $\neg\neg$-topología. Es bien sabido que separaba presheaves para un Grothendieck topología de formar un Grothendieck quasitopos (véase, por ejemplo, Johnstone del Elefante).

El reclamo no es muy difícil comprobar. Lo representable $\hom_G(-, 1)$ es el dígrafo $\bullet \to \bullet$, y lo representable $\hom_G(-, 0)$ es el dígrafo $\bullet$; puede ser calculado que la única $\neg\neg$-denso subpresheaf de $\hom(-, 0)$ $\hom(-, 0)$ sí, y que la única $\neg\neg$-denso subpresheaf de $\hom(-, 1)$ además de sí mismo es el dígrafo inclusión

$$(\bullet \;\;\; \bullet) \hookrightarrow (\bullet \to \bullet).$$

Ahora un presheaf $X$ $G$ es separado si, para cada objeto $c$ y cada una de las $\neg\neg$-denso de inclusión $i: F \hookrightarrow \hom(-, c)$, la inducida por el mapa

$$X(c) \cong \mathbf{Set}^{G^{op}}(\hom(-, c), X) \stackrel{\mathbf{Set}^{G^{op}}(i, X)}{\to} \mathbf{Set}^{G^{op}}(F, X)$$

es inyectiva. Puesto que sólo tenemos un no-trivial densa inclusión (el dígrafo inclusión se muestra arriba), la separación de la condición en $X$ se reduce a decir que la canónica mapa

$$X(1) \to \hom((\bullet \;\;\; \bullet), X) \cong X(0) \times X(0)$$

es inyectiva, es decir, que el mapa de tomar cada arista $e \in X(1)$ a la de origen-destino de par $(s^\ast(e), t^\ast(e))$ es inyectiva. Pero esto sólo significa $X$ es isomorfo a un dígrafo (en el sentido de este post), por lo que estamos por hacer. (Esta información puede estar disponible a petición.)

Answer 2

Deje $\mathbf{Dig}$ sea su categoría de bigramas, y deje $\mathbf{Gph}$ el valor de la categoría de `multigraphs', es decir, presheaves más de los habituales de la categoría $[0] \rightrightarrows [1]$ (por favor, pregunte si eso está claro). $\mathbf{Dig}$ es un completo, reflexivo subcategoría de $\mathbf{Gph}$, que abarca simples gráficos, es decir, todos los $G$ tal que $G(x,y)$ $\emptyset$ o $1$ todos los $x,y$. La izquierda adjunto, de forma intuitiva, mantiene vértices sin cambios, e identifica todos los bordes paralelos.

Así, para cualquier diagrama en $\mathbf{Dig}$, lo ven como un diagrama en $\mathbf{Gph}$, calcular su colimit allí (que es un presheaf gato!), y, a continuación, reflejan de vuelta a $\mathbf{Dig}$ a través de la izquierda adjunto. Esto produce un colimit para el diagrama original, debido a la izquierda adjoints preservar colimits.

En cuanto a los límites, es fácil comprobar que arbitraria de los productos de los bigramas, calculado en $\mathbf{Gph}$, son de nuevo los bigramas. Lo mismo vale para los sintonizadores, lo que demuestra que no sólo los límites no existen en $\mathbf{Dig}$, pero también que son calculadas como en $\mathbf{Gph}$. En otros términos, el derecho adjoint crea límites.

Finalmente, he aquí un contraejemplo a la izquierda adjunto la preservación de colimits. Considere los dos morfismos de la terminal gráfica en el gráfico con un vértice y dos bordes. Su ecualizador es el discreto gráfico con un vértice, que es un dígrafo. Sin embargo, la aplicación de la izquierda adjunto a nuestro morfismos, obtenemos el doble de la identidad en la terminal de caracteres especiales, cuya ecualizador no es discreto.

[Gracias por los comentarios!]