A binary relation on n points is a subset R ⊆ {1, ..., n} × {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 iR of positive integers less than or equal to n to each number between 1 and n. This set iR is called the set of successors of i under the relation R.
The degree of a binary relation may not be larger than 228-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. 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 ∈ {1, ..., n} are in relation R S if and only if there is a point z ∈ {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 for all i = 1, ..., 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 GAP3 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).
The next sections describe how relations are compared (see Comparisons of Relations) and which operations are available for relations (see Operations 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. 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".
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 ∈ {1, ..., n} contains the set iR of succesors of i. Here each single set of successors is represented as a subset of {1, ..., 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:true.
domain:Relations.
Moreover a relation record has the identification component
successors:A relation record rel can aquire the following knowledge components.
isReflexive:true if rel represents a reflexive relation (see
IsReflexive)
isSymmetric:true if rel represents a symmetric relation (see
IsSymmetric)
isTransitive:true if rel represents a transitive relation (see
IsTransitiveRel)
isPreOrder:true if rel represents a preorder (see IsPreOrder)
isPartialOrder:true if rel represents a partial order (see
IsPartialOrder)
isEquivalence: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, ..., 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, ..., 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, ..., 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 { } ⊆ {1, ..., n} × {1, ..., 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 ⊆ {1, ..., n} × {1, ..., 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.
The operator * evaluates to the product of the two relations rel1
and rel2 if both have the same degree.
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).
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").
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.
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.
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).
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.
The operator ^ evaluates to the inverse of the relation rel. The
inverse of a relation R ⊆ {1, ..., n} × {1, ...,
n} is given by {(y, x) | (x, y) ∈ 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.
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 ⊆ {1, ..., n} × {1, ..., n} is reflexive if (i, i) ∈ R for all i = 1, ..., n. (See also ReflexiveClosure.)
ReflexiveClosure( rel )
ReflexiveClosure returns the reflexive closure of the relation rel,
i.e., the relation R ⊆ {1, ..., n} × {1, ..., n}
that consists of all pairs in rel and the pairs (1, 1), ..., (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 ⊆ {1, ..., n} × {1, ..., n} is symmetric if (y, x) ∈ R for all (x, y) ∈ 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 ⊆ {1, ..., n} × {1, ..., n} is transitive if (x, z) ∈ R whenever (x, y) ∈ R and (y, z) ∈ R for some y ∈ {1, ..., 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 ⊆ {1, ..., n} × {1, ..., n} is antisymmetric if (x, y) ∈ R and (y, x) ∈ 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 ] ] ) );
true
A relation rel is called a preorder if rel is reflexive and transitive.
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 ] ] ) );
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.)
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 ⊆ {1, ..., n} × {1, ..., n} is the smallest relation H ⊆ {1, ..., n} × {1, ..., 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
gap3-jm