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