2 Binary Relations

A binary relation on n points is a subset R subseteq {1, ..., n} x {1, ..., n}. It can also be seen as a multivalued map from {1, ..., n} to itself, or as a directed graph with vertices {1, ..., n}. The number n is called the degree of the relation. Thus a binary relation R of degree n associates a set i^R of positive integers less than or equal to n to each number between 1 and n. This set i^R is called the set of successors of i under the relation R.

The degree of a binary relation may not be larger than 2^{28}-1 which is (currently) the highest index that can be accessed in a list.

Special cases of binary relations are transformations (see chapter Transformations) and permutations (see chapter "Permutations"). However, an object of one of these types must be converted into a binary relation before most of the functions of this chapter are applicable.

The product of binary relations is defined via composition of mappings, or equivalently, via concatenation of edges of directed graphs. More precisely, if R and S are two relations on {1, ..., n} then their product R S is defined by saying that two points x, y in {1, ..., n} are in relation R S if and only if there is a point z in {1, ..., n} such that x R z and z S y. As multivalued map, the product RS is defined by [ i^(RS) = (i^R)^S quad mboxfor all i = 1, dots, n. ] With respect to this multiplication the set of all binary relations of degree n forms a monoid, the full relation monoid of degree n.

Each relation of degree n is considered an element of the full relation monoid of degree n although it is not necessary to construct a full relation monoid before working with relations. But you can only multiply two relations if they have the same degree. You can, however, multiply a relation of degree n by a transformation or a permutation of degree n.

A binary relation is entered and displayed by giving its lists of successors as an argument to the function Relation. The relation < on the set {1, 2, 3}, for instance, is written as follows.

    gap> Relation( [ [ 2, 3 ], [ 3 ], [ ] ] );
    Relation( [ [ 2, 3 ], [ 3 ], [  ] ] ) 

This chapter describes finite binary relations in GAP and the functions that deal with them. The first sections describe the representation of a binary relation (see More about Relations) and how an object that represents a binary relation is constructed (see Relation). There is a function which constructs the identity relation of degree n (see IdentityRelation) and a function which constructs the empty relation of degree n (see EmptyRelation). Then there are a function which tests whether an arbitrary object is a relation (see IsRelation) and a function which determines the degree of a relation (see Degree of a Relation).

Comparisons of Relations) and which operations are available for relations (see Operations for Relations and Set Functions for Relations). There are functions which test certain properties of relations (see IsReflexive, IsSymmetric, IsTransitiveRel, IsAntisymmetric, IsPartialOrder, and IsEquivalence) and functions that construct different closures of a relation (see ReflexiveClosure, SymmetricClosure, and TransitiveClosure). Moreover there are a function which computes the classes of an equivalence relation (see EquivalenceClasses) and a function which determines the Hasse diagram of a partial order (see HasseDiagram). Finally, two functions are describe which convert a transformation into a binary relation (see RelTrans) and, if possible, a binary relation into a transformation (see TransRel).

The last section of the chapter describes monoids generated by binary relations (see Monoids of Relations).

The functions described in this chapter are in the file "relation.g".


  1. More about Relations
  2. Relation
  3. IsRelation
  4. IdentityRelation
  5. EmptyRelation
  6. Degree of a Relation
  7. Comparisons of Relations
  8. Operations for Relations
  9. Set Functions for Relations
  10. IsReflexive
  11. ReflexiveClosure
  12. IsSymmetric
  13. SymmetricClosure
  14. IsTransitiveRel
  15. TransitiveClosure
  16. IsAntisymmetric
  17. IsPreOrder
  18. IsPartialOrder
  19. IsEquivalence
  20. EquivalenceClasses
  21. HasseDiagram
  22. RelTrans
  23. TransRel
  24. Monoids of Relations
[Previous] [Up] [Next] 

Version 2.4 (May 1998)