Ejemplo básico de Yoneda Lemma?

Question

Me ha gustado toda la internet y los libros en la categoría de teoría tratando de entender el Yoneda Lema. He leído el Tom Leinster "Yoneda Lema: Whas se trata todo esto?", y vio la charla de Steve Awdoey en ese tema también. Ambos de ellos no me ayudan mucho, y me estoy empezando a entender el asunto.

Sin embargo, la mayoría de los ejemplos que me podría encontrar siempre se refieren a cosas sobre las matemáticas que no he tenido ningún contacto con (tales como Anillos, Grupos, Topos, ...). Soy un Estudiante de informática, y sé lo básico de la Categoría de la Teoría de Conjuntos, el Posets, Conjuntos y Funciones Parciales, Gráficos, visto como una categoría).

¿Hay algún ejemplo que me pueda dar (o sepa) que utiliza el Yoneda Lema y conocimientos básicos de la categoría de la teoría? Estoy interesado en un ejemplo de la aplicación de la Lexema o la Incrustación de objetos para resolver o demostrar algo.

Answer 1

Científicos de la computación de hacer uso de un buen par de estructuras algebraicas, sólo son ligeramente diferentes de las de los matemáticos suelen centrarse en. De equipo de científicos tienden a preocuparse acerca de monoids, semigroups, semirings, y seminearrings. Por ejemplo, la libre monoid en algunos de $\Sigma$ es sólo la lista de $\Sigma^*$. Un autómata de estado finito determinista es sólo un monoid acción de la libre monoid en un conjunto finito. Relatedly, los operadores de expresiones regulares en forma de una estrella semiring. De hecho, muchas cosas en el CS de formar una estrella semiring que conduce a la sorprendente conexiones.

De todos modos, cuando se oye hablar de la Yoneda lema, invariablemente escuchar acerca de su corolario, la Yoneda functor es completa y fiel. Todo esto significa es que $$\text{Nat}(\text{Hom}(\_,A),\text{Hom}(\_,B)) \cong \text{Hom}(A,B)\text{ and} \\ \text{Nat}(\text{Hom}(A,\_),\text{Hom}(B,\_)) \cong \text{Hom}(B,A)$$ natural in $UN$ and $B$. A key general result is a fully faithful functor reflects isomorphisms. That is, if $F$ is fully faithful and $FX \cong FY$ then $X \cong Y$. You should prove this. (All functors preserve isomorphisms.) Specializing, this means if $\text{Hom}(a,X) \cong \text{Hom}(A,Y)$ natural in $$, then $X \cong Y$, and similarly for the other argument of $\text{Hom}$. For example, here's a proof that left adjoints preserve coproducts (basically the same proof will show that left adjoints preserve all colimits). Assume $F \dashv U$, i.e. $\text{Hom}(FA,X) \cong \text{Hom}(A, UX)$ natural in$$ and $X$. The defining property of a coproduct is the following $\text{Hom}(a+B\_) \cong \text{Hom}(A,\_)\times\text{Hom}(B,\_)$. La prueba: $$\begin{align} \text{Hom}(F(A+B),\_) &\cong \text{Hom}(A+B,U\_) \\ &\cong \text{Hom}(A,U\_)\times\text{Hom}(B,U\_) \\ &\cong \text{Hom}(FA,\_)\times\text{Hom}(FB,\_) \\ &\cong \text{Hom}(FA+FB,\_) \end{align}$$ Por Yoneda, tenemos $F(A+B) \cong FA + FB$. Este uso de Yoneda es tan omnipresente que generalmente es usado de forma tácita. (Como una nota de lado, le recomiendo esta cadena-de-isomorphisms estilo de hacer de la categoría de la teoría de que es impulsado por la noción de un representable functor. Combinado con (co)termina, enormes sectores de pruebas categóricas se convierten así de fácil.)

Monoid acciones tienen una especialmente bonita representación en la categoría de teoría, ya que monoids puede ser visto como un objeto de categorías. Deje $M$ ser un monoid visto como una categoría. Un (a la izquierda) $M$-acción es un functor $M \to \mathbf{Set}$. Llamar a la persona objeto de $\star$. (Derecho $M$-acción es un functor $M^{op}\to\mathbf{Set}$.) Por definición, $\text{Hom}(\star, \star) = M$ donde aquí estamos viendo el $M$ como un monoid. Cuando tenemos un $M$, $\phi$, en un conjunto $X$, nos referimos a $\phi(\star) = X$.

El Yoneda lema establece que un $M$, $\phi$, es la misma cosa como una función de $h : M \to \phi(\star)$ que satisface $h(m_1 m_2) = \phi(m_1)(h(m_2))$. En otras palabras, una $A^*$-acción es exactamente la misma cosa como un derecho de veces. Para autómatas, derecho $\Sigma^*$-acciones tiene más sentido que el de la izquierda. El mismo cálculo se producen a la izquierda doblar en ese caso, aunque se describe como un derecho de doble sobre una inversión de la lista.

Mucho de la categoría de la teoría puede ser considerada como un categorification de orden/de celosía de la teoría de las ideas. Decategorifying categórica concepto generalmente produce un concepto útil en el fin de la teoría. La interpretación abstracta es un área en la CS donde el orden teórico de las ideas son utilizadas. En lugar de ver posets como categorías especiales, me gusta ver como $\mathbf{2}$enriquecido categorías o, equivalentemente, (0,1)-categorías. Esto puede sonar intimidante, pero en realidad hace las cosas mucho más sencillo y claro. (Me gustaría que alguien había sugerido que puedo ver los Sub functor como un índice (0,1)-categoría.)

El resultado de todo esto es que en lugar de tener una familia de hom-conjuntos, tenemos un solo hom-relación. En este contexto, a menudo la noción de hacia arriba/hacia abajo-conjunto cerrado se utiliza. Deje $\mathbf{2}\equiv\{\bot,\top\}$ con el pedido de $\bot\leq\top$. Un alza subconjunto cerrado de un poset $X$ puede ser identificado con una forma monotónica $X \to \mathbf{2}$ que se puede hacer en un poset mediante el punto de sabio pedido. Se puede comprobar que si $f : X \to \mathbf{2}$ es monótona y definimos $U = \{x\in X\mid f(x)=\top\}$, $U$ es hacia arriba-cerrado, es decir, si $x\in U$$x\leq y$$y \in U$. Además, el pointwise pedido en funciones corresponde al subconjunto de pedidos. Escribir $\text{Up}(X)$ para el conjunto de arriba-cerrado los subconjuntos de a $X$ con el subconjunto de pedidos. Escribir $\text{Down}(X)\equiv\text{Up}(X^{op})$ para el conjunto de la baja de conjuntos cerrados. El Yoneda la inclusión es, a continuación, $\mathcal{Y}(x) = \{y\in X\mid y \leq x\}$ $\mathcal{Y} : X \to \text{Down}(X)$ es una forma monotónica. El Yoneda lema es, a continuación, la declaración de $U \in \text{Down}(X)$: $$x \in U \iff \forall y\in X.y\leq x \Rightarrow y \in U$$ The co-Yoneda lemma then says $$x \in U \iff \exists y\in X. x\leq y \land y \in U$$