Multi-relations in Z. A cross between multi-sets and binary relations (Q1186512)

Both the theories of binary relations and multi-sets (or bags) in \(Z\) have been usefully applied to software specification and development. In this paper we examine a useful theory --- multi-relations --- which is a cross between these two theories. One way of viewing relations is as sets of pairs. Here, by analogy, we view multi-relations as multi-sets of pairs, and we define multi-relation equivalents of most of the traditional operators defined on binary relations. Multi-relations can also be viewed as graphs or two-dimensional matrices (with indices over arbitrary sets). The use of multi-relations is illustrated by specifying a bill-of- materials system. This provides a good example of the paradigm of building a suitable mathematical theory first and then developing a specification in terms of the theory.