# 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"`.

### Subsections

[Index]

Version 2.4 (May 1998)