3 - Relations

Summary

Already in the previous chapters, relations have shown up in a more or less naïve form, for example as permutation matrices or as (partial) identity relations. Here, we provide ideas for more stringent data types for relations. Not least, these will serve to model graph situations, like graphs on a set, bipartitioned graphs, or hypergraphs.

What is even more important at this point is the question of denotation. We have developed some scrutiny when denoting basesets, elements of these, and subsets; all the more will we now be careful in denoting relations. Since we restrict ourselves mostly to binary relations, this will mean denoting the source of the relation as well as its target and then denoting the relation proper. It is this seemingly trivial point which will be stressed here, namely from which set to which set the relation actually leads.

Relation representation

We aim mainly at relations over finite sets. Then a relation R between sets V, W is announced as R : V → W.

— as a set of pairs {(x, y),…} with x ∈ V, y ∈ W

— as a list of pairs [(x,y),…] with x∷V,y∷W

— in predicate form {(x, y) ∈ V × W ∣ p(x, y)} with a binary predicate p