Probabilistic Completion of Nondeterministic Models

AbstractThis work continues ongoing research in combining theories of nondeterminism and probabilistic choice. First, we adapt the above choice theories to allow for uncountably indexed nondeterministic operators, and countably indexed probabilistic operators. Classically, models for mixed choice were obtained by enhancing arbitrary models for probabilistic choice with appropriately distributive nondeterministic operations. In this paper, we focus on the dual approach: constructing mixed choice models by completing nondeterministic models with suitably behaved probabilistic operations. We introduce a functorial construction, called convex completion, which freely computes set-theoretical and posetal mixed choice models from the appropriate semilattices. The completion construction relies upon a new closure operation on convex sets, dependant on the given semilattice. Finally, we show that building a free mixed choice model is equivalent to applying the convex completion functor to its corresponding free nondeterministic model