Coalgebraic Non-Wellfounded Proofs: Recursiveness and GTC
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2026
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911687864483840 |
|---|---|
| author | Kori, Mayuko |
| author_facet | Kori, Mayuko |
| contents | Non-wellfounded proof systems impose a global condition called the global trace condition (GTC) on a derivation tree to ensure soundness. Providing a categorical characterisation of the GTC that guarantees soundness remains challenging due to the global, non-compositional nature of these conditions and the infinitary structure of non-wellfounded proofs. We develop a coalgebraic framework for non-wellfounded proof systems where derivation trees are modelled as coalgebras of generalised polynomial functors on presheaves. Since the GTC is a constraint on infinite paths in derivation graphs, we employ graphs of coalgebras and formulate the GTC coalgebraically as a condition on these graphs. Soundness is then formulated as the existence of a unique coalgebra-to-algebra morphism from a coalgebra representing a derivation graph to an algebra specifying semantics. Within this framework, we characterise the GTC via recursive coalgebras: a coalgebra satisfies the GTC if and only if its image under a suitable adjoint is recursive. Under an appropriate assumption on the given semantic algebra, this yields soundness, that is, every proof admits a unique coalgebra-to-algebra morphism. We demonstrate our framework through a non-wellfounded proof system for the modal mu-calculus, one for higher-order fixed-point logics, and a non-wellfounded variant of Santocanale's circular proof system in mu-bicomplete categories. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_15664 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Coalgebraic Non-Wellfounded Proofs: Recursiveness and GTC Kori, Mayuko Logic in Computer Science Non-wellfounded proof systems impose a global condition called the global trace condition (GTC) on a derivation tree to ensure soundness. Providing a categorical characterisation of the GTC that guarantees soundness remains challenging due to the global, non-compositional nature of these conditions and the infinitary structure of non-wellfounded proofs. We develop a coalgebraic framework for non-wellfounded proof systems where derivation trees are modelled as coalgebras of generalised polynomial functors on presheaves. Since the GTC is a constraint on infinite paths in derivation graphs, we employ graphs of coalgebras and formulate the GTC coalgebraically as a condition on these graphs. Soundness is then formulated as the existence of a unique coalgebra-to-algebra morphism from a coalgebra representing a derivation graph to an algebra specifying semantics. Within this framework, we characterise the GTC via recursive coalgebras: a coalgebra satisfies the GTC if and only if its image under a suitable adjoint is recursive. Under an appropriate assumption on the given semantic algebra, this yields soundness, that is, every proof admits a unique coalgebra-to-algebra morphism. We demonstrate our framework through a non-wellfounded proof system for the modal mu-calculus, one for higher-order fixed-point logics, and a non-wellfounded variant of Santocanale's circular proof system in mu-bicomplete categories. |
| title | Coalgebraic Non-Wellfounded Proofs: Recursiveness and GTC |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2605.15664 |