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

.

- 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

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*i*th 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)

`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 ] ] )

`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

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

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

`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*.

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

`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

or `new`[`i`] = `list`[`i`] * `rel`

, respectively.
`new`[`i`] =
`rel` * `list`[`i`]

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

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

is related to `elm`[1]

, and to
`elm`[2]`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

`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 ] ] ) ); trueA relation

`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).

`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.)

`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).

`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.)

`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).

`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*.

`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 ] ] ) ); trueA relation

`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).

`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 ] ] ) ); trueA relation

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

`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*.

`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 ] ] )

`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 ] )

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