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

.

- More about Relations
- Relation
- IsRelation
- IdentityRelation
- EmptyRelation
- Degree of a Relation
- Comparisons of Relations
- Operations for Relations
- Set Functions for Relations
- IsReflexive
- ReflexiveClosure
- IsSymmetric
- SymmetricClosure
- IsTransitiveRel
- TransitiveClosure
- IsAntisymmetric
- IsPreOrder
- IsPartialOrder
- IsEquivalence
- EquivalenceClasses
- HasseDiagram
- RelTrans
- TransRel
- Monoids of Relations

[Index] Version 2.4 (May 1998)