Terminal Coalgebras in Countably Many Steps

Resumo Técnico: Coálgebras Terminais em Passos Contáveis

Enunciado do Problema
O artigo aborda a construção de coálgebras terminais para endofuntores em várias categorias. Um método padrão para construir uma coálgebra terminal $\nu F$ envolve iterar o frutificador $F$ sobre o morfismo único $F1 \to 1$ para formar uma cadeia transfinita (a cadeia da coálgebra terminal). Embora essa cadeia convirja para $\nu F$ se o frutificador preservar o limite relevante, o número de iterações necessárias pode ser arbitrariamente grande, ou a cadeia pode não convergir de forma alguma (por exemplo, para o frutificador do conjunto das partes).

Um resultado seminal de Worrell [49] estabeleceu que, para endofutores finitários na categoria dos conjuntos ($\mathbf{Set}$), a coálgebra terminal é obtida em exatamente $\omega + \omega$ passos (ou seja, $\nu F = V_{\omega+\omega}$). O problema central deste artigo é generalizar o resultado de Worrell para outras categorias base e determinar os limites de convergência para classes específicas de frutificadores, como frutificadores polinomiais em espaços topológicos e métricos.

Metodologia
Os autores empregam uma combinação de técnicas de teoria das categorias e argumentos de finitude específicos:

1. Condição de Cadeia Descendente (DCC): O artigo introduz o conceito de categorias DCC, que são categorias localmente finitamente apresentáveis onde objetos finitamente apresentáveis satisfazem uma condição de cadeia descendente sobre subobjetos e quocientes fortes. Essa condição garante que os limites $\omega^{op}$ nessas categorias sejam "finitários" (Proposição 3.16).
2. Propriedades de Preservação: Os autores isolam propriedades de preservação específicas necessárias para a convergência:
   • Preservação de interseções binárias não vazias (pullbacks de monomorfismos com domínios iniciais não estritos).
   • Preservação de imersões isométricas (no contexto de espaços métricos).
3. Iteração de Dois Estágios: A metodologia baseia-se na técnica de Worrell de uma "segunda iteração infinita". Se o primeiro limite $\omega$ ($V_\omega$) não for preservado, os autores iteram $F$ sobre o morfismo de conexão $m: FV_\omega \to V_\omega$ para formar a cadeia $V_\omega \leftarrow V_{\omega+1} \leftarrow \dots$, cujo limite é $V_{\omega+\omega}$.
4. Representações por Árvores: Para frutificadores específicos (conjunto das partes finito, Vietoris, Hausdorff), os autores caracterizam os limites $V_\omega$ e as coálgebras terminais usando árvores (fortemente estensíveis, de ramificação compacta e árvores com arestas rotuladas).

Principais Contribuições e Resultados

1. Generalização para Categorias DCC (Seção 4)
O artigo prova que, para qualquer categoria DCC $\mathcal{A}$ e qualquer endofutificador finitário $F$ que preserve interseções binárias não vazias, a cadeia da coálgebra terminal converge em $\omega + \omega$ passos ($\nu F = V_{\omega+\omega}$).

• Escopo: Isso se aplica a categorias incluindo $\mathbf{Set}$, $\mathbf{Pos}$ (posets), $\mathbf{Gra}$ (grafos), $\mathbf{K\text{-}Vec}$ (espaços vetoriais) e pré-esquemas sobre conjuntos finitos.
• Espaços Métricos: Como $\mathbf{Met}$ (espaços métricos) não é localmente finitamente apresentável, os autores fornecem uma condição suficiente separada (Teorema 4.10): um endofutificador finitário em $\mathbf{Met}$ que preserve interseções binárias não vazias e imersões isométricas também converge em $\omega + \omega$ passos.

2. Frutificadores Polinomiais em Espaços Topológicos (Seção 7)
Os autores estudam frutificadores polinomiais de Vietoris na categoria de espaços topológicos ($\mathbf{Top}$), construídos a partir do frutificador de Vietoris $V$ (atribuindo subconjuntos compactos com a topologia de Vietoris), constantes e identidade.

• Resultado: Se as constantes no frutificador forem espaços Hausdorff, a coálgebra terminal é obtida em $\omega$ passos ($\nu F = V_\omega$).
• Subcategorias: Este resultado é válido para as categorias de espaços Hausdorff ($\mathbf{Haus}$), espaços compactos de Hausdorff ($\mathbf{KHaus}$) e espaços de Stone. A prova baseia-se em mostrar que o frutificador de Vietoris preserva limites de cadeias $\omega^{op}$ nessas categorias.
• Significância: Isso melhora os resultados anteriores de Hofmann et al. [29] e Abramsky [1], fornecendo uma prova direta de convergência em $\omega$ passos sem depender de provas incompletas de Zenor [50].

3. Frutificadores Polinomiais em Espaços Métricos (Seção 8)
Os autores definem frutificadores polinomiais de Hausdorff em $\mathbf{Met}$, usando o frutificador de Hausdorff $H$ (atribuindo subconjuntos compactos com a métrica de Hausdorff).

• Resultado: Diferentemente do caso de Vietoris, a coálgebra terminal para frutificadores polinomiais de Hausdorff requer $\omega + \omega$ passos ($\nu F = V_{\omega+\omega}$).
• Raciocínio: O frutificador de Hausdorff não preserva limites de cadeias $\omega^{op}$ em $\mathbf{Met}$ (ao contrário do frutificador de Vietoris em $\mathbf{Haus}$).
• Representação Concreta: O artigo fornece uma representação concreta da coálgebra terminal para um frutificador de sistema de transição rotulado métrico $FX = H(\Sigma \times X)$ como o espaço de árvores de arestas rotuladas, fortemente estensíveis e de ramificação finita, equipadas com uma métrica específica derivada dos rótulos.

4. Provas Detalhadas e Contraexemplos

• Descrição de Worrell: O artigo fornece uma prova detalhada da descrição de Worrell para a coálgebra terminal do frutificador do conjunto das partes finito $P_f$ em termos de árvores, o que anteriormente era afirmado sem prova.
• Subconjuntos Fechados: Os autores provam que o frutificador $P_{cl}$ (atribuindo todos os subconjuntos fechados) em $\mathbf{Met}$ não possui coálgebra terminal (não possui pontos fixos), e o subfrutificador $P'_{cl}$ (subconjuntos fechados não vazios) não possui pontos fixos além do conjunto vazio e dos singulares (Teorema 8.19).

Significância e Alegações
O artigo afirma generalizar o teorema de Worrell além de $\mathbf{Set}$ ao identificar as propriedades estruturais (DCC e preservação de interseção) que garantem a convergência em $\omega + \omega$ passos. Ele distingue entre diferentes frutificadores polinomiais com base em suas categorias base:

• Polinomiais de Vietoris em $\mathbf{Haus}$ convergem em $\omega$ passos.
• Polinomiais de Hausdorff em $\mathbf{Met}$ e polinomiais de Kripke em $\mathbf{Set}$ convergem em $\omega + \omega$ passos.

Os autores declaram explicitamente que seu trabalho melhora os resultados de Abramsky [1] e Hofmann et al. [29] em relação aos frutificadores de Vietoris. Eles também observam que, embora o Teorema do Limite de Makkai e Paré [34] garanta a existência de coálgebras terminais para frutificadores acessíveis em categorias localmente apresentáveis, ele não fornece o limite de convergência específico de $\omega + \omega$ passos, que é a principal contribuição deste trabalho.

Problemas Abertos
O artigo deixa em aberto duas questões:

1. Todo frutificador polinomial de Vietoris na categoria total $\mathbf{Top}$ (permitindo constantes não-Hausdorff) possui uma coálgebra terminal?
2. Todo frutificador polinomial de Vietoris em $\mathbf{KHaus}$ (com constantes compactas de Hausdorff e coprodutos finitos) possui uma álgebra inicial? (Os autores observam que os argumentos padrão para álgebras iniciais falham aqui porque os monomorfismos não são suaves em $\mathbf{KHaus}$).