Trees in Coalgebra from Generalized Reachability

Problem Statement
The paper addresses the fundamental structural properties of state-based systems modeled as coalgebras. While the concept of reachability (where every state is accessible from an initial state) has been well-characterized coalgebraically via universal properties (absence of proper subcoalgebras) and iterative constructions (union of successor states), a corresponding coalgebraic characterization of tree structure has been lacking. Specifically, the authors seek to define when a coalgebra is a "tree" in a way that generalizes the intuitive graph-theoretic notion: a system where every state is reachable via a unique path from the initial state. The challenge lies in handling systems where transitions may be partial, non-deterministic, or involve sharing, and in providing a characterization that works for a broad class of functors, including those that do not preserve monomorphisms (such as the bag functor).

Methodology
The authors employ a categorical approach based on factorization systems and coalgebra theory. Their methodology proceeds through three main stages:

1. Generalization of Minimality: They first generalize the notion of "minimality" in a category. Moving beyond the classical definition where a minimal object has no proper subobjects (requiring morphisms to be isomorphisms), they introduce $M$-minimality (Definition 4.1). An object is $M$-minimal if every morphism from a class $M$ into it is a split epimorphism. This generalization allows $M$ to be the class of all morphisms, not just monomorphisms.
2. Connection to Projectivity and Reachability: They establish a link between this generalized minimality and $M$-projectivity (Theorem 4.7). They then instantiate this theory in the category of pointed coalgebras to define generalized reachability (Definition 5.1). A coalgebra is $M$-reachable if every pointed $M$-subcoalgebra is a split epimorphism.
3. Iterative Construction via Precise Maps: To construct the reachable or tree-unravelled version of a coalgebra, the authors utilize precise morphisms (Definition 3.1). Unlike "least bounds" (bases) which rely on monomorphisms to avoid sharing, precise maps ensure that elements in the codomain are used exactly once in the definition of the map. They prove that for analytic functors, precise factorizations exist and coincide with least bounds when restricted to monomorphisms (Proposition 3.27, Corollary 3.22).

Key Contributions
The paper provides two equivalent characterizations for when a coalgebra is a tree, mirroring the dual characterizations of reachability:

• Universal Property (Tree Definition): A pointed coalgebra is a tree if it has no proper unravelings. Formally, a coalgebra is a tree if every unravelling (a pointed coalgebra homomorphism into it) is a split epimorphism (Definition 6.1). This generalizes the reachability condition by allowing the morphism class $M$ to be the class of all morphisms, rather than just monomorphisms.
• Iterative Construction (Tree Unravelling): The authors present an iterative construction (Construction 6.23) that transforms an arbitrary pointed coalgebra into a tree. This construction involves taking the coproduct of levels, where each level is computed via precise factorizations of the transition map. The resulting coalgebra is the "tree unravelling" of the original system.
• Unification: The paper demonstrates that both reachability and the property of being a tree are instances of the same generalized notion of $M$-minimality. Reachability corresponds to $M$ being a class of monomorphisms, while the tree property corresponds to $M$ being the class of all morphisms.

Results
The authors validate their theory by recovering expected notions of trees for various standard examples:

• Partial Deterministic Automata: The tree unravelling corresponds to the "coalgebra of defined inputs," where states are identified with the unique words leading to them (Lemma 6.11, Corollary 6.12).
• Multigraphs (Bag Functor): For coalgebras over the bag functor (modeling multigraphs), the tree unravelling is the "coalgebra of rooted paths." A bag-coalgebra is a tree if and only if there is a unique path from the root to every vertex (Theorem 6.18).
• Powerset Functor: The paper highlights a limitation: for the powerset functor (modeling simple graphs), the characterization implies that almost no coalgebra is a tree. This is because the powerset functor allows "copying" (e.g., $\{x\} = \{x, x\}$), which prevents the existence of precise maps for non-empty sets (Proposition 3.3). Consequently, trees in this setting are trivial (single vertex, no edges).

Significance
The paper claims significance by providing a unified theoretical framework that extends the theory of reachable coalgebras to tree structures.

• Generalization: It successfully generalizes the concept of reachability from proper factorization systems (monos) to arbitrary factorization systems, enabling the treatment of tree structures where morphisms need not be injective.
• Analytic Functors: The iterative construction is shown to work for all analytic set functors (Corollary 3.22), a broad class including polynomial functors and the bag functor, which are central to modeling various computational systems.
• Conceptual Clarity: By linking minimality to projectivity and providing both universal and iterative characterizations, the paper offers a robust categorical foundation for understanding tree-like behavior in state-based systems, distinguishing it clearly from the behavior of systems modeled by the powerset functor.

The authors note that this work is an extended version of a conference paper, adding full proofs and further generalizations, particularly the connection between minimality and projectivity and the detailed analysis of precise factorizations.