Characterizing finite posets whose probabilistic powerdomain are RB-domains

Hui Kou; Yuxu Chen; Zhenchao Lyu

arxiv: 2607.02231 · v1 · pith:K6VWO2YLnew · submitted 2026-07-02 · 🧮 math.CO · math.GN

Characterizing finite posets whose probabilistic powerdomain are RB-domains

Yuxu Chen , Hui Kou , Zhenchao Lyu This is my paper

Pith reviewed 2026-07-03 10:35 UTC · model grok-4.3

classification 🧮 math.CO math.GN

keywords probabilistic powerdomainRB-domainfinite posetHasse graphstochastic ordertree posetdomain theory

0 comments

The pith

Finite posets have RB-domain probabilistic powerdomains exactly when they possess a least element and their undirected Hasse graph forms a tree.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper classifies all finite posets P for which the probabilistic powerdomain V1(P), consisting of probability measures ordered by stochastic dominance, is an RB-domain. It proves the equivalence to P having a least element and its Hasse graph being a tree. A reader would care because this shows the probabilistic powerdomain operation fails to preserve RB-domains, with the four-point diamond providing an explicit finite counterexample. The argument proceeds by isolating two obstructions to the RB property: absence of a least element forces certain minimal measures to be fixed by all deflations, while a cycle in the Hasse graph renders the local stochastic cone non-simplicial, blocking the needed finite monotone approximations.

Core claim

For a finite nonempty poset P, the probability powerdomain V1(P) is an RB-domain if and only if P has a least element and the undirected Hasse graph of P is a tree. This classification follows from separating the case without a least element, where the face of measures on minimal points is fixed pointwise by every deflation, from the case with a least element, where a cycle produces a non-simplicial local stochastic cone that precludes the finite-valued monotone approximations required by the RB property.

What carries the argument

The probabilistic powerdomain V1(P) ordered by the stochastic order, whose RB-domain property holds precisely under the least-element and tree-Hasse conditions on P.

If this is right

The probabilistic powerdomain does not preserve RB-domains in general, as witnessed by the four-point diamond poset.
V1(P) is an RB-domain only for those finite posets whose Hasse diagrams are trees rooted at a least element.
The two obstructions are independent: fixed-point behavior arises without a bottom element, while non-simpliciality arises from cycles even when a bottom element exists.
The Euclidean finite-step cone argument suffices to rule out RB approximations once a cycle is present.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The same obstructions may limit preservation of other domain properties under probabilistic powerdomains for finite posets.
Tree-structured posets with bottoms could be checked for preservation of additional order-theoretic features beyond RB-domains.
The simpliciality criterion for local cones might be tested in related constructions such as other measure orderings on posets.

Load-bearing premise

That the RB property requires finite-valued monotone approximations below the identity, which are ruled out exactly when minimal-measure faces are fixed by deflations or when local stochastic cones are non-simplicial.

What would settle it

Exhibiting a finite poset whose undirected Hasse graph contains a cycle yet whose V1(P) still admits finite-valued monotone approximations below the identity would falsify the classification.

read the original abstract

We classify the finite posets whose probabilistic powerdomain is an RB-domain. For a finite nonempty poset $P$, let $\Vone(P)$ be the probability powerdomain of $P$, which is the probability simplex ordered by the stochastic order. We prove that $\Vone(P)$ is an RB-domain if and only if $P$ has a least element and the undirected Hasse graph of $P$ is a tree. Consequently, the probabilistic powerdomain does not preserve RB-domains; the four-point diamond gives a finite counterexample. The proof separates two obstructions. First, if $P$ has no least element, then the face of probability measures supported on the minimal points must be fixed pointwise by every deflation below the identity. Secondly, once a least element exists, the Hasse graph is connected, and a cycle in it makes the local stochastic cone non-simplicial. A Euclidean finite-step cone argument then rules out the finite-valued monotone approximations supplied by the RB property.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a clean iff characterization for when a finite poset's probabilistic powerdomain is an RB-domain (bottom element plus tree Hasse graph), separating two obstructions, though the cone non-simpliciality step is only sketched.

read the letter

The core result is that for a finite nonempty poset P, V1(P) is an RB-domain precisely when P has a least element and its undirected Hasse graph is a tree. This also supplies a simple counterexample (the four-point diamond) showing that probabilistic powerdomains do not preserve RB-domains.

The paper does a good job separating the two obstructions explicitly. The no-bottom case is handled by noting that measures on minimal elements are fixed pointwise by any deflation below the identity. Once a bottom exists, the argument shifts to connectivity and then to cycles producing a non-simplicial local stochastic cone, which blocks the finite-valued monotone approximations required by the RB property. The separation is direct and avoids circularity.

The main soft spot is that the necessity direction rests on a Euclidean finite-step cone argument for non-simpliciality, and the abstract only outlines it without the detailed verification. That geometric step is the load-bearing part once the bottom is present, so its rigor matters. The sufficiency direction looks more routine from the sketch.

This is a specialized classification inside domain theory and probabilistic powerdomains. Specialists working on RB-domains or powerdomain constructions will find the explicit criterion and the counterexample useful. It is narrow enough that it will not affect broader work, but the statement is precise and the obstructions are cleanly isolated.

The outline is coherent and the claim is presented as new. It deserves a serious referee to check the cone argument and the approximation details.

Referee Report

2 major / 2 minor

Summary. The paper classifies finite nonempty posets P for which the probabilistic powerdomain V1(P) (the probability simplex under stochastic order) is an RB-domain. It proves the iff statement that V1(P) is an RB-domain precisely when P has a least element and the undirected Hasse graph of P is a tree. As a corollary, the probabilistic powerdomain does not preserve RB-domains, with the four-point diamond as a finite counterexample. The necessity proof separates two obstructions: absence of a least element forces every deflation below the identity to fix the face of measures on minimal points pointwise; presence of a cycle (once a least element exists) renders the local stochastic cone non-simplicial, which a Euclidean finite-step cone argument shows precludes the finite-valued monotone approximations required by the RB property.

Significance. If correct, the result supplies an explicit combinatorial characterization separating independent obstructions (bottom element and acyclicity of the Hasse graph) and gives a concrete finite counterexample to preservation. The direct proof strategy, free of fitted parameters or self-referential reductions, is a strength for domain theory and order-theoretic probability.

major comments (2)

[necessity proof (cycle case)] The necessity direction for cycles: the claim that a cycle renders the local stochastic cone non-simplicial (thereby blocking finite monotone approximations) is load-bearing for the central iff statement, yet the abstract supplies only the outline of the Euclidean finite-step cone argument without explicit verification that non-simpliciality precludes the required approximations.
[sufficiency proof] Sufficiency direction: the construction showing that a tree with bottom yields an RB-domain must be checked for completeness, as the abstract asserts the direction without detailing how the tree structure supplies the finite-valued monotone approximations.

minor comments (2)

Define Vone(P) and the stochastic order explicitly at the first use rather than assuming familiarity with the probability simplex.
Clarify the precise meaning of 'undirected Hasse graph' (e.g., whether multiple edges or self-loops are possible) to avoid ambiguity in the tree condition.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the two load-bearing directions of the main theorem. We address each major comment below and indicate the revisions we will make to strengthen the exposition.

read point-by-point responses

Referee: [necessity proof (cycle case)] The necessity direction for cycles: the claim that a cycle renders the local stochastic cone non-simplicial (thereby blocking finite monotone approximations) is load-bearing for the central iff statement, yet the abstract supplies only the outline of the Euclidean finite-step cone argument without explicit verification that non-simpliciality precludes the required approximations.

Authors: The full manuscript contains the Euclidean finite-step cone argument in Section 3.2, which shows that a non-simplicial local stochastic cone cannot admit a sequence of finite-valued monotone deflations approximating the identity. However, we agree that the abstract presents only an outline and that an explicit verification of the implication 'non-simplicial implies no finite monotone approximations' would improve clarity. In the revision we will insert a self-contained paragraph immediately after the definition of the local stochastic cone that spells out the contradiction: any finite-valued monotone deflation would have to map the cone into a simplicial subcone, which is impossible when the cone is non-simplicial. We will also add the four-point diamond as a worked example illustrating the obstruction. revision: yes
Referee: [sufficiency proof] Sufficiency direction: the construction showing that a tree with bottom yields an RB-domain must be checked for completeness, as the abstract asserts the direction without detailing how the tree structure supplies the finite-valued monotone approximations.

Authors: The sufficiency proof proceeds by induction on the height of the tree, constructing explicit finite-valued monotone deflations at each step that exploit the unique path from the bottom element to any element. The manuscript gives the inductive step in Section 4, but we concede that the abstract does not preview the construction. To make the argument self-contained, the revised version will include a short subsection that explicitly describes the deflation associated with each leaf-to-root path and verifies that these deflations are monotone, finite-valued, and converge to the identity in the Scott topology. This will also clarify why the tree condition is essential for the construction to succeed. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper states an explicit iff theorem characterizing finite posets P for which V1(P) is an RB-domain, proved by separating two independent obstructions (absence of least element; presence of cycle in Hasse graph) and invoking standard domain-theoretic facts about deflations plus a Euclidean cone argument. No parameter fitting, self-definitional reductions, or load-bearing self-citations appear; the central claim is not forced by re-naming or by construction from its own inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The paper is a pure classification theorem in order theory; it introduces no free parameters, no ad-hoc axioms beyond standard poset and domain theory, and no new invented entities.

pith-pipeline@v0.9.1-grok · 5706 in / 1230 out tokens · 34494 ms · 2026-07-03T10:35:38.501054+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

[1]

Abramsky, A

S. Abramsky, A. Jung, Domain theory, in S. Abramsky, D. M. Gabbay, T. S. E. Maibaum (Eds.), Handbook of Logic in Computer Science, Vol. 3, Oxford University Press, 1994, pp. 1–168

work page 1994
[2]

R. T. Rockafellar,Convex Analysis, Princeton Mathematical Series, Vol. 28, Princeton University Press, Princeton, NJ, 1970

work page 1970
[3]

L. C. Evans, R. F. Gariepy,Measure Theory and Fine Properties of Functions, revised ed., CRC Press, Boca Raton, 2015

work page 2015
[4]

Gierz, K

G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott,Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003

work page 2003
[5]

Goubault-Larrecq, QRB-domains and the probabilistic powerdomain,Logical Methods in Computer Science8 (1:14) (2012) 1–32

J. Goubault-Larrecq, QRB-domains and the probabilistic powerdomain,Logical Methods in Computer Science8 (1:14) (2012) 1–32

work page 2012
[6]

Jones, G

C. Jones, G. D. Plotkin, A probabilistic powerdomain of evaluations, inProceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS 1989), IEEE Computer Society Press, 1989, pp. 186–195

work page 1989
[7]

Jung,Cartesian Closed Categories of Domains, CWI Tract 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989

A. Jung,Cartesian Closed Categories of Domains, CWI Tract 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989

work page 1989
[8]

A. Jung, R. Tix, The troublesome probabilistic powerdomain, in A. Edalat, A. Jung, K. Keimel, M. Kwiatkowska (Eds.),Proceedings of the Third Workshop on Computation and Approximation, Electronic Notes in Theoretical Computer Science 13 (1998) 70–91

work page 1998
[9]

Diestel,Graph Theory, 5th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2017

R. Diestel,Graph Theory, 5th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2017

work page 2017
[10]

R. Tix, K. Keimel, G. Plotkin, Semantic domains for combining probability and non-determinism (updated),Electronic Notes in Theoretical Computer Science222 (2009) 1–99. 21

work page 2009

[1] [1]

Abramsky, A

S. Abramsky, A. Jung, Domain theory, in S. Abramsky, D. M. Gabbay, T. S. E. Maibaum (Eds.), Handbook of Logic in Computer Science, Vol. 3, Oxford University Press, 1994, pp. 1–168

work page 1994

[2] [2]

R. T. Rockafellar,Convex Analysis, Princeton Mathematical Series, Vol. 28, Princeton University Press, Princeton, NJ, 1970

work page 1970

[3] [3]

L. C. Evans, R. F. Gariepy,Measure Theory and Fine Properties of Functions, revised ed., CRC Press, Boca Raton, 2015

work page 2015

[4] [4]

Gierz, K

G. Gierz, K. H. Hofmann, K. Keimel, J. D. Lawson, M. Mislove, D. S. Scott,Continuous Lattices and Domains, Encyclopedia of Mathematics and its Applications, Vol. 93, Cambridge University Press, 2003

work page 2003

[5] [5]

Goubault-Larrecq, QRB-domains and the probabilistic powerdomain,Logical Methods in Computer Science8 (1:14) (2012) 1–32

J. Goubault-Larrecq, QRB-domains and the probabilistic powerdomain,Logical Methods in Computer Science8 (1:14) (2012) 1–32

work page 2012

[6] [6]

Jones, G

C. Jones, G. D. Plotkin, A probabilistic powerdomain of evaluations, inProceedings of the Fourth Annual Symposium on Logic in Computer Science (LICS 1989), IEEE Computer Society Press, 1989, pp. 186–195

work page 1989

[7] [7]

Jung,Cartesian Closed Categories of Domains, CWI Tract 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989

A. Jung,Cartesian Closed Categories of Domains, CWI Tract 66, Centrum voor Wiskunde en Informatica, Amsterdam, 1989

work page 1989

[8] [8]

A. Jung, R. Tix, The troublesome probabilistic powerdomain, in A. Edalat, A. Jung, K. Keimel, M. Kwiatkowska (Eds.),Proceedings of the Third Workshop on Computation and Approximation, Electronic Notes in Theoretical Computer Science 13 (1998) 70–91

work page 1998

[9] [9]

Diestel,Graph Theory, 5th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2017

R. Diestel,Graph Theory, 5th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2017

work page 2017

[10] [10]

R. Tix, K. Keimel, G. Plotkin, Semantic domains for combining probability and non-determinism (updated),Electronic Notes in Theoretical Computer Science222 (2009) 1–99. 21

work page 2009