Mathematically, a relation on a set X is a subset of
X ×X. In GAP a relation on X is a general mapping
from X to itself. In fact, the category IsBinaryRelation is
the same as the category IsEndoGeneralMapping.
Of course, a binary relation can have the properties:
IsReflexiveBinaryRelation, IsTransitiveBinaryRelation and
IsSymmetricBinaryRelation. When all three are true, we call
the relation an equivalence relation.
IsBinaryRelation( R ) C
IsBinaryRelation(R) is true precisely when IsEndoGeneralMapping(R) is true.
IsSymmetricBinaryRelation( rel ) P
IsTransitiveBinaryRelation( rel ) P
IsReflexiveBinaryRelation( rel ) P
Properties of binary relations. Note that a reflexive binary relation is necessarily total.
ReflexiveClosureBinaryRelation( Relation ) O
SymmetricClosureBinaryRelation( Relation ) O
TransitiveClosureBinaryRelation( Relation ) O
Closure operations for binary relations. TransitiveClosureBinaryRelation is a modified version of the Floyd-Warshall method of solving the all-pairs shortest-paths problem on a directed graph. Its asymptotic runtime is O(n^3) where n is the size of the vertex set. It only assumes there is an arbitrary (but fixed) ordering of the vertex set.
IsEquivalenceRelation( Relation ) P
An equivalence relation is a symmetric, transitive, reflexive binary relation.
EquivalenceRelationPartition( equiv ) A
EquivalenceRelationPartition returns a list of lists of elements. The lists are precisely the nonsingleton equivalence classes. This allows us to describe ``small'' equivalences on infinite sets.
EquivalenceRelationByPartition( domain, list ) F
domain is the domain over which the relation is defined, and list is a list of lists, each of these is a list of elements of domain which are related to each other. list need only contain the nontrivial blocks and will ignore singletons.
EquivalenceRelationByRelation( rel ) F
EquivalenceRelationByRelation(rel) - form the smallest equivalence relation containing rel.
EquivalenceRelationByPairs( D, elms ) F
EquivalenceRelationByPairsNC( D, elms ) F
EquivalenceRelationByPairs is the smallest equivalence relation on the domain D such that every pair in elms is in the relation.
In the second form, it is not checked that elms are in the domain
IsEquivalenceClass( O ) C
An equivalence class is a collection of elements which are mutually related to each other in the associated equivalence relation. Note, this is a special category of object and not just a list of elements.
EquivalenceClassRelation( C ) A
The equivalence relation of which C is a class.
EquivalenceClasses( rel ) A
A list of all equivalence classes of the equivalence relation rel. Note, is is possible that different methods will yield the list in a different order, so that for two equivalence relations c1 and c2 we may have c1 = c2 but not EquivalenceClasses(c1) = EquivalenceClasses(c2).
EquivalenceClassOfElement( rel, elt ) O
EquivalenceClassOfElementNC( rel, elt ) O
The equivalence class of elt in rel. In the second form, it is not checked that elt is in the domain over which rel is defined.
[Top] [Previous] [Up] [Next] [Index]
GAP 4 manual