The Order-Sobrification Monad
- PDF / 338,890 Bytes
- 8 Pages / 439.37 x 666.142 pts Page_size
- 91 Downloads / 177 Views
The Order-Sobrification Monad Xiaodong Jia1 Received: 7 February 2019 / Accepted: 13 May 2020 © Springer Nature B.V. 2020
Abstract We investigate the so-called order-sobrification monad proposed by Ho et al. (Log Methods Comput Sci 14:1–19, 2018) for solving the Ho–Zhao problem, and show that this monad is commutative. We also show that the Eilenberg–Moore algebras of the order-sobrification monad over dcpo’s are precisely the strongly complete dcpo’s and the algebra homomorphisms are those Scott-continuous functions preserving suprema of irreducible subsets. As a corollary, we show that this monad gives rise to the free strongly complete dcpo construction over the category of posets and Scott-continuous functions. A question related to this monad is left open alongside our discussion, an affirmative answer to which might lead to a uniform way of constructing non-sober complete lattices. Keywords dcpo’s · Order sobrification · Eilenberg–Moore algebras · Strong completion of posets
1 Introduction The Ho–Zhao problem asks whether two directly complete partially ordered sets (dcpo for short) with isomorphic Scott topologies are themselves isomorphic. The question was answered by Ho, Goubault-Larrecq, Jung and Xi [4] in the negative by displaying a counterexample. They also gave a class of special dcpo’s, that of dominated dcpo’s, and proved that any two dominated dcpo’s with isomorphic Scott topologies are isomorphic. A crucial step in proving this positive result is that the authors converted the original question into the following equivalent one: whether two dcpo’s with isomorphic dcpo’s of closed irreducible subsets (ordered by inclusion) are isomorphic? This equivalent conversion heavily relies on the so-called order-sobrification monad proposed in that same paper.
Communicated by Martín Escardó. This research was partially supported by Labex DigiCosme (Project ANR-11-LABEX-0045-DIGICOSME) operated by ANR as part of the program “Investissement d’Avenir” Idex Paris-Saclay (ANR-11-IDEX-0003-02).
B 1
Xiaodong Jia [email protected] LSV, ENS Paris-Saclay, CNRS, Université Paris-Saclay, Saint-Aubin, France
123
X. Jia
Concretely, the order-sobrification monad assigns to a dcpo D the set of all closed irreducible subsets (in the Scott topology) ordered by inclusion. This monad is different from the sobrification monad as the former is not always idempotent as shown in [4, Section 4]. In this note, we take a closer look at this monad and show that it is a commutative monad on the category of dcpo’s and Scott-continuous functions. We also examine its Eilenberg– Moore algebras by showing they are precisely the strongly complete dcpo’s and the algebra morphisms are those Scott-continuous functions preserving suprema of irreducible subsets. This result can be employed to give a free construction of strongly complete dcpo’s over the category of posets and Scott-continuous functions. Alongside our discussion a question about this monad is left open, an affirmative answer to which might lead to a uniform way of con
Data Loading...
