Encontrar un functor que satisfaga una ecuación recursiva

Question

Digamos que quiero encontrar un functor que satisfaga algo como: \N - [FA = 1] \sqcup (A \times FA). Equivalente, quiero encontrar para cada uno $A$ un punto fijo de: \N - [GB = 1] \sqcup (A \times B) (Me preocuparé por lo que $F$ hace sobre los morfismos más tarde).

Lo que quiero hacer es, a grandes rasgos, aplicar $G$ infinitamente muchas veces, y la esperanza $G$ es en cierto sentido "continuo", de modo que el resultado es un punto fijo del mismo. Pero veo al menos dos posibles enfoques: si tengo un objeto inicial, entonces puedo formar el diagrama (de la forma $ \mathbb N$ considerado como una categoría de poset) \to G0 \to GG0 \to \dots\ y tomar el colimito, o si tengo un objeto terminal, entonces el límite de \dots \to GG1 \to G1 \to 1\] (de forma $ \mathbb N^ \mathrm {op}$ ) podría servir para ello (como señaló un comentarista, el límite de la primera y el colimito de la segunda no son interesantes). Presumiblemente quiero elegir el límite o el colimito de acuerdo a cualquiera de los dos $G$ conserva, de modo que puedo argumentar que el resultado realmente es un punto fijo.

Los objetos iniciales y terminales son los "extremos" más obvios de las cadenas anteriores, pero cualquier objeto en el que pueda empezar (es decir, que tenga un morfismo $A \to GA$ o $GA \to A$ ) podría ser de gran ayuda.

¿Cuál de estas estrategias (si es que hay alguna) es sensata? ¿Dan el mismo resultado? ¿Hay otras estrategias?

Answer 1

Ambas estrategias son sensatas para los functores y categorías que se comportan adecuadamente: una corresponde a tomar el punto fijo "más pequeño" (el álgebra libre), y la otra corresponde a tomar el punto fijo "más grande" (el álgebra libre de carbón). Casi nunca son equivalentes --- en su ejemplo, la primera construcción da el tipo de secuencias finitas sobre $A$ mientras que la segunda construcción da el tipo de secuencias contables sobre $A$ .

Categóricamente, lo que ha descrito es un caso muy especial de construcción de la mónada libre y la comónada libre de un endofunctor. Desde mi punto de vista no puedo decirles ningún buen libro de texto sobre el tema (apenas recuerdo que hay un capítulo en "Toposes Triples y Teorías" de Michael Barr, también hay un montón de cosas sobre (co)álgebras escritas por Bard Jacobs). Sin embargo, deberías encontrar mucha información buscando los términos "libre (co)mónada" y "libre (co)triple" (triple es un nombre antiguo para la mónada).

Answer 2

Una buena estrategia para encontrar puntos fijos para los functores es encontrar álgebras iniciales, o carbonillas terminales.

Un álgebra inicial para un functor $F$ es un objeto $A$ emparejado con un morfismo $ \alpha : FA \to A$ de tal manera que para cualquier otro par $(B, \beta )$ hay un morfismo único $f : A \to B$ de tal manera que $f \circ \alpha = \beta \circ Ff$ .

Son interesantes en este contexto porque:

Teorema : Si $(A, \alpha )$ es una inicial $F$ -algebra, entonces $ \alpha $ es un isomorfismo (así que $A$ es un punto fijo de $F$ ).

Prueba : Si $(A, \alpha )$ es un álgebra, entonces también lo es $(FA,F \alpha )$ y $ \alpha $ es (de manera algo trivial) un homomorfismo de álgebra $(FA, F \alpha ) \to (A, \alpha )$ . Entonces, desde $(A, \alpha )$ es inicial, hay un homomorfismo de álgebra único $f : (A, \alpha ) \to (FA,F \alpha )$ y así $ \alpha\circ f$ es un homomorfismo de álgebra de $(A, \alpha )$ a sí mismo. Pero por su singularidad, esta es la identidad. Ahora.., $f$ un homomorfismo de álgebra significa $$f \circ \alpha = F \alpha \circ Ff = F( \alpha \circ f) = F \operatorname {id}_A = \operatorname {id}_{FA}$$ . Así que $f \circ \alpha $ es la identidad también.

Un resultado doble se mantiene para las carbonillas terminales, por supuesto.

La siguiente pregunta es, ¿cuándo existen las álgebras iniciales y cómo se construyen? Introducción al Árbol de Carbono tiene una gran cantidad de teoremas con referencias sobre este y otros temas relacionados. En particular, los siguientes:

3.17. Teorema. Que $ \mathcal A$ tienen y $H$ preservar $ \omega $ -colimites. Si $0$ es el objeto inicial de $ \mathcal A$ y $! : 0 \to H0$ el morfismo único, luego un álgebra inicial $I$ es un colimito de la $ \omega $ -cadena $$0 \xrightarrow {!} H0 \xrightarrow {H!} HH0 \xrightarrow {HH!} \dots $$

Hay otros resultados para entornos más generales, en particular colmillos indexados por ordinales más grandes. La referencia dada para el resultado anterior es:

J. Adámek, Algebras libres y realización de autómatas en el lenguaje de las categorías, Comentario. Matemáticas. Univ. Carolinae 15(1974), 589–602.

Por otra parte, siguiendo el consejo de Mockup en la otra respuesta, pasé por la construcción de listas en $ \mathbf {Set}$ por el método de colimación secuencial, pero partiendo de un objeto no inicial. Lo que obtienes depende de lo que exactamente elijas para tu morfismo $A \to GA$ puede obtener exactamente lo mismo que de otra manera, o puede obtener algunos elementos "extra", por ejemplo, secuencias que satisfagan $x = a:x$ para algunos $a \in A$ .