Universal homogeneous graph-like structures and domains

Abstract

We present explicit constructions of universal homogeneous objects in categories of domains with stable embedding–projection pairs as arrows. These results make use of a representation of such domains through graph-like structures and apply a generalization of Rado’s result on the existence of the universal homogeneous countable graph. In particular, we build universal homogeneous objects in the categories of coherence spaces and qualitative domains, introduced by Girard (Girard 1987; Girard 1986), and two categories of hypercoherences recently studied by Ehrhard (Ehrhard 1993). Our constructions rely on basic numerical notions. We also show that a suitable random construction of Rado’s graph and its generalizations produces with probability 1 the universal homogeneous structures presented here.