Elena Di Lavore ; Mario Román ; Paweł Sobociński ; Márk Széles - Order in Partial Markov Categories

entics:16686 - Electronic Notes in Theoretical Informatics and Computer Science, December 20, 2025, Volume 5 - Proceedings of MFPS XLI - https://doi.org/10.46298/entics.16686
Order in Partial Markov CategoriesArticle

Authors: Elena Di Lavore ; Mario Román ; Paweł Sobociński ; Márk Széles

    Partial Markov categories are a recent framework for categorical probability theory that provide an abstract account of partial probabilistic computation with updating semantics. In this article, we discuss two order relations on the morphisms of a partial Markov category. In particular, we prove that every partial Markov category is canonically preorder-enriched, recovering several well-known order enrichments. We also demonstrate that the existence of codiagonal maps (comparators) is closely related to order properties of partial Markov categories. Finally, we introduce a synthetic version of the Cauchy--Schwarz inequality and, from it, we prove that updating increases validity.

    20 pages, MFPS XVI. In a previous version, an invocation of the restriction preorder in quasi-Markov categories [FGLPS25, Proposition 2.16] was missing the positivity hypothesis; we thank Areeb Shah Mohammed for pointing it out


    Volume: Volume 5 - Proceedings of MFPS XLI
    Published on: December 20, 2025
    Accepted on: October 15, 2025
    Submitted on: April 3, 2025
    Keywords: Logic in Computer Science, 18M05