# 88 Binary Relations

A binary relation on n points is a subset R subseteq {1, dots, n} times {1, dots, n}. It can also be seen as a multivalued map from {1, dots, n} to itself, or as a directed graph with vertices {1, dots, 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, dots, n} then their product R S is defined by saying that two points x, y in {1, dots, n} are in relation R S if and only if there is a point z in {1, dots, 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

A binary relation seen as a directed graph on n points is completely determined by its degree and its list of edges. This information is represented in the form of a successors list which, for each single point i in {1, dots, n} contains the set i^R of succesors of i. Here each single set of successors is represented as a subset of {1, dots, n} by boolean list (see chapter "Boolean Lists").

A relation R of degree n is represented by a record with the following category components.

`isRelation`:

is always set to `true`.

`domain`:

is always set to `Relations`.

Moreover a relation record has the identification component

`successors`:

containing a list which has as its ith entry the boolean list representing the successors of i.

A relation record rel can aquire the following knowledge components.

`isReflexive`:

set to `true` if rel represents a reflexive relation (see IsReflexive)

`isSymmetric`:

set to `true` if rel represents a symmetric relation (see IsSymmetric)

`isTransitive`:

set to `true` if rel represents a transitive relation (see IsTransitiveRel) `isPreOrder`:
set to `true` if rel represents a preorder (see IsPreOrder)

`isPartialOrder`:

set to `true` if rel represents a partial order (see IsPartialOrder)

`isEquivalence`:

set to `true` if rel represents an equivalence relation (see IsEquivalence)

## 88.2 Relation

`Relation( list )`

`Relation` returns the binary relation defined by the list list of subsets of {1, dots, n} where n is the length of list.

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

Alternatively, list can be a list of boolean lists of length n, each of which is interpreted as a subset of {1, dots, n} (see chapter "Boolean Lists").

```    gap> Relation( [
> [ true, true, false ],
> [ false, false, false ],
> [ true, false, true ] ] );
Relation( [ [ 1, 2 ], [  ], [ 1, 3 ] ] ) ```

## 88.3 IsRelation

`IsRelation( obj )`

`IsRelation` returns `true` if obj, which may be an object of arbitrary type, is a relation and `false` otherwise. It will signal an error if obj is an unbound variable.

```    gap> IsRelation( 1 );
false
gap> IsRelation( Relation(  [ [ 1 ], [ 2 ], [ 3 ] ] ) );
true ```

## 88.4 IdentityRelation

`IdentityRelation( n )`

`IdentityRelation` returns the identity relation of degree n. This is the relation `=` on the set {1, dots, n}.

```    gap> IdentityRelation( 5 );
Relation( [ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ] ) ```

The identity relation of degree n acts as the identity in the full relation monoid of degree n.

## 88.5 EmptyRelation

`EmptyRelation( n )`

`EmptyRelation` returns the empty relation of degree. This is the relation { } subseteq {1, dots, n} times {1, dots, n}.

```    gap> EmptyRelation( 5 ) ;
Relation( [ [  ], [  ], [  ], [  ], [  ] ] ) ```

The empty relation of degree n acts as zero in the full relation monoid of degree n.

## 88.6 Degree of a Relation

`Degree( rel )`

`Degree` returns the degree of the binary relation rel.

```    gap> Degree( Relation( [ [ 1 ], [ 2, 3 ], [ 2, 3 ] ] ) );
3 ```

The degree of a relation R subseteq {1, dots, n} times {1, dots, n} is defined as n.

## 88.7 Comparisons of Relations

`rel1 = rel2`
`rel1 < rel2`

The equality operator `=` applied to two relations rel1 and rel2 evaluates to `true` if the two relations are equal and to `false` otherwise. The inequality operator `<` applied to two relations rel1 and rel2 evaluates to `true` if the two relations are not equal and to `false` otherwise. A relation can also be compared to any other object that is not a relation, of course they are never equal. Two relations are considered equal if and only if their successors lists are equal as lists. In particular, they must have the same degree.

```    gap> Relation( [ [ 1 ], [ 2 ], [ 3 ], [ 4 ] ] ) =
> IdentityRelation( 4 );
true
gap> Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) =
> Relation( [ [ ], [ 1 ], [ 1, 2 ], [ ] ] );
false```

`rel1 < rel2`
`rel1 <= rel2`
`rel1 rel2`
`rel1 = rel2`

The operators `<`, `<=`, , and `=` evaluate to `true` if the relation rel1 is less than, less than or equal to, greater than, or greater than or equal to the relation rel2, and to `false` otherwise.

Let rel1 and rel2 be two relations that are not equal. Then rel1 is considered smaller than rel2 if and only if the successors list of rel1 is smaller than the successors list of rel2.

You can also compare relations with objects of other types. Here any object that is not a relation will be considered smaller than any relation.

## 88.8 Operations for Relations

`rel1 * rel2`

The operator `*` evaluates to the product of the two relations rel1 and rel2 if both have the same degree.

`rel * trans`
`trans * rel`

The operator `*` evaluates to the product of the relation rel and the transformation trans in the given order provided both have the same degree (see chapter Transformations).

`rel * perm`
`perm * rel`

The operator `*` evaluates to the product of the relation rel and the permutation perm in the given order provided both have the same degree (see chapter "Permutations").

`list * rel`
`rel * list`

The operator `*` evaluates to the list of products of the elements in list with the relation rel. That means that the value is a new list new such that `new[i] = list[i] * rel` or ```new[i] = rel * list[i]```, respectively.

`i ^ rel`

The operator `^` evaluates to the set of successors <i>^<rel> of the positive integer i under the relation rel if i is smaller than or equal to the degree of rel.

`set ^ rel`

The operator `^` evaluates to the image or the set set under the relation rel which is defined as the union of the sets of successors of the elements of set.

`rel ^ 0`

The operator `^` evaluates to the identity relation on n points if rel is a relation on n points (see IdentityRelation).

`rel ^ i`

For a positive integer i the operator `^` evaluates to the i-th power of the relation rel which is defined in the usual way as the i-fold product of rel by itself.

`rel ^ -1`

The operator `^` evaluates to the inverse of the relation rel. The inverse of a relation R subseteq {1, dots, n} times {1, dots, n} is given by {(y, x) mid (x, y) in R}. Note that, in general, the product of a binary relation and its inverse is not equal to the identity relation. Neither is it in general equal to the product of the inverse and the binary relation.

## 88.9 Set Functions for Relations

Relations are not implemented as GAP domains, therefore the usual set functions (like `Elements` and `Size`) do not apply (even if we provide methods for them). However, union and difference of relations are implemented through the operators `+` and `-`.

`rel1 + rel2`

The operator `+` evaluates to the union of the relations rel1 and rel2 if both have the same degree.

```    gap> a:= Relation( [ [  ], [ 4 ], [ 1, 4 ], [ 1 ] ] );;
gap> b:= Relation( [ [ 1 ], [  ], [ 4 ], [  ] ] );;
gap> a + b;
Relation( [ [ 1 ], [ 4 ], [ 1, 4 ], [ 1 ] ] ) ```

`rel1 - rel2`

The operator `-` evaluates to the difference of the relations rel1 and rel2 if both have the same degree.

```    gap> a:= Relation( [ [  ], [ 4 ], [ 1, 4 ], [ 1 ] ] );;
gap> b:= Relation( [ [ 1 ], [  ], [ 4 ], [  ] ] );;
gap> a - b;
Relation( [ [  ], [ 4 ], [ 1 ], [ 1 ] ] ) ```

`elm in rel`

The operator `in` evaluates to `true` if the pair elm is in the relation rel, that is if `elm[1]` is related to `elm[2]`, and to `false` otherwise. If elm is not a pair, or if an entry in pair exceeds the degree of rel an error is produced.

```    gap> a:= Relation( [ [  ], [ 4 ], [ 1, 4 ], [ 1 ] ] );;
gap> [1,2] in a;
false
gap> [2,4] in a;
true ```

## 88.10 IsReflexive

`IsReflexive( rel )`

`IsReflexive` returns `true` if the binary relation rel is reflexive and `false` otherwise.

```    gap> IsReflexive( Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) );
false
gap> IsReflexive( Relation( [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
true ```
A relation R subseteq {1, dots, n} times {1, dots, n} is reflexive if (i, i) in R for all i = 1, dots, n. (See also ReflexiveClosure.)

## 88.11 ReflexiveClosure

`ReflexiveClosure( rel )`

`ReflexiveClosure` returns the reflexive closure of the relation rel, i.e., the relation R subseteq {1, dots, n} times {1, dots, n} that consists of all pairs in rel and the pairs (1, 1), dots, (n, n), where n is the degree of rel.

```    gap> ReflexiveClosure( Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) );
Relation( [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) ```

By construction, the reflexive closure of a relation is reflexive (see IsReflexive).

## 88.12 IsSymmetric

`IsSymmetric( rel )`

`IsSymmetric` returns `true` if the binary relation rel is symnmetric and `false` otherwise.

```    gap> IsSymmetric( Relation( [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
false
gap> IsSymmetric( Relation( [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) );
true ```

A relation R subseteq {1, dots, n} times {1, dots, n} is symmetric if (y, x) in R for all (x, y) in R. (See also SymmetricClosure.)

## 88.13 SymmetricClosure

`SymmetricClosure( rel )`

`SymmetricClosure` returns the symmetric closure of the binary relation rel.

```    gap> SymmetricClosure( Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) );
Relation( [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) ```

By construction, the symmetric closure of a relation is symmetric (see IsSymmetric).

## 88.14 IsTransitiveRel

`IsTransitiveRel( rel )`

`IsTransitiveRel` returns `true` if the binary relation rel is transitive and `false` otherwise.

```    gap> IsTransitiveRel( Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) );
true
gap> IsTransitiveRel( Relation( [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) );
false ```

A relation R subseteq {1, dots, n} times {1, dots, n} is transitive if (x, z) in R whenever (x, y) in R and (y, z) in R for some y in {1, dots, n}. (See also TransitiveClosure.)

## 88.15 TransitiveClosure

`TransitiveClosure( rel )`

`TransitiveClosure` returns the transitive closure of the binary relation rel.

```    gap> TransitiveClosure( Relation( [ [ ], [ 1 ], [ 2 ], [ 3 ] ] ) );
Relation( [ [  ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) ```

By construction, the transitive closure of a relation is transitive (see IsTransitiveRel).

## 88.16 IsAntisymmetric

`IsAntisymmetric( rel )`

`IsAntisymmetric` returns `true` if the binary relation rel is antisymmetric and `false` otherwise.

```    gap> IsAntisymmetric( Relation( [ [  ], [ 1 ], [ 1, 2 ] ] ) );
true
gap> IsAntisymmetric( Relation( [ [ 2, 3 ], [ 1, 3 ], [ 1, 2 ] ] ) ) ;
false ```

A relation R subseteq {1, dots, n} times {1, dots, n} is antisymmetric if (x, y) in R and (y, x) in R implies x = y.

## 88.17 IsPreOrder

`IsPreOrder( rel )`

`IsPreOrder` returns `true` if the binary relation rel is a preoder and `false` otherwise.

```    gap> IsPreOrder( Relation( [ [  ], [ 1 ], [ 1, 2 ] ] ) );
false
gap> IsPreOrder( Relation( [ [ 1, 2 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
true ```
A relation rel is called a preorder if rel is reflexive and transitive.

## 88.18 IsPartialOrder

`IsPartialOrder( rel )`

`IsPartialOrder` returns `true` if the binary relation rel is a partial order and `false` otherwise.

```    gap> IsPartialOrder( Relation( [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
true
gap> IsPartialOrder( Relation( [ [ 1, 2 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
false ```

A relation rel is called a partial order if rel is reflexive, transitive and antisymmetric, i.e., if rel is an antisymmetric preorder (see IsPreOrder).

## 88.19 IsEquivalence

`IsEquivalence( rel )`

`IsEquivalence` returns `true` if the binary relation rel is an equivalence relation and `false` otherwise.

```    gap> IsEquivalence( Relation( [ [ ], [ 1 ], [ 1, 2 ] ] ) );
false
gap> IsEquivalence( Relation( [ [ 1 ], [ 2, 3 ], [ 2, 3 ] ] ) );
true ```
A relation rel is an equivalence relation if rel is reflexive, symmetric, and transitive, i.e., if rel is a symmetric preorder (see IsPreOrder). (See also EquivalenceClasses.)

## 88.20 EquivalenceClasses

`EquivalenceClasses( rel )`

returns the list of equivalence classes of the equivalence relation rel. It will signal an error if rel is not an equivalence relation (see IsEquivalence).

```    gap> EquivalenceClasses( Relation( [ [ 1 ], [ 2, 3 ], [ 2, 3 ] ] ) );
[ [ 1 ], [ 2, 3 ] ] ```

## 88.21 HasseDiagram

`HasseDiagram( rel )`

`HasseDiagram` returns the Hasse diagram of the binary relation rel if this is a partial order. It will signal an error if rel is not a partial order (see IsPartialOrder).

```    gap> HasseDiagram( Relation( [ [ 1 ], [ 1, 2 ], [ 1, 2, 3 ] ] ) );
Relation( [ [  ], [ 1 ], [ 2 ] ] ) ```

The Hasse diagram of a partial order R subseteq {1, dots, n} times {1, dots, n} is the smallest relation H subseteq {1, dots, n} times {1, dots, n} such that R is the reflexive and transitive closure of H.

## 88.22 RelTrans

`RelTrans( trans )`

`RelTrans` returns the binary relation defined by the transformation trans (see chapter Transformations).

```    gap> RelTrans( Transformation( [ 3, 3, 2, 1, 4 ] ) );
Relation( [ [ 3 ], [ 3 ], [ 2 ], [ 1 ], [ 4 ] ] ) ```

## 88.23 TransRel

`TransRel( rel )`

`TransRel` returns the transformation defined by the binary relation rel (see chapter Transformations). This can only be applied if every set of successors of rel has size 1. Otherwise an error is signaled.

```    gap> TransRel( Relation( [ [ 3 ], [ 3 ], [ 2 ], [ 1 ], [ 4 ] ] ) );
Transformation( [ 3, 3, 2, 1, 4 ] ) ```

## 88.24 Monoids of Relations

There are no special functions provided for monoids generated by binary relations. The action of such a monoid on sets, however, provides a way to convert a relation monoid into a transformation monoid (see chapter Actions of Monoids). This monoid can then be used to investigate the structure of the original relation monoid.

```    gap> a:= Relation( [ [  ], [  ], [ 1, 3, 4 ], [  ], [ 2, 5 ] ] );;
gap> b:= Relation( [ [  ], [ 2 ], [ 4 ], [ 1, 2, 3 ], [ 1 ] ] );;
gap> M:= Monoid( a, b );
Monoid( [ Relation( [ [  ], [  ], [ 1, 3, 4 ], [  ], [ 2, 5 ] ] ),
Relation( [ [  ], [ 2 ], [ 4 ], [ 1, 2, 3 ], [ 1 ] ] ) ] )
gap> # transform points into singleton sets.
gap> one:= List( [ 1 .. 5 ], x-> [ x ] );
[ [ 1 ], [ 2 ], [ 3 ], [ 4 ], [ 5 ] ]
gap> # determine all reachable sets.
gap> sets:= Union( Orbits( M, one ) );
[ [  ], [ 1 ], [ 1, 2 ], [ 1, 2, 3 ], [ 1, 2, 3, 4 ], [ 1, 3, 4 ],
[ 2 ], [ 2, 4 ], [ 2, 5 ], [ 3 ], [ 4 ], [ 5 ] ]
gap> # construct isomorphic transformation monoid.
gap> act:= Action( M, sets );
Monoid( [ Transformation( [ 1, 1, 1, 6, 6, 6, 1, 1, 9, 6, 1, 9 ] ),
Transformation( [ 1, 1, 7, 8, 5, 5, 7, 4, 3, 11, 4, 2 ] ) ] )
gap> Size(act);
11```

GAP 3.4.4
April 1997