1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%A relation.msk GAP documentation Andrew Solomon
%%
%A @(#)$Id: relation.msk,v 1.13 2002/04/15 10:02:33 sal Exp $
%%
%Y (C) 1999 School Math and Comp. Sci., University of St. Andrews, Scotland
%Y Copyright (C) 2002 The GAP Group
%%
\Chapter{Relations}
\FileHeader{relation}[1]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{General Binary Relations}
\Declaration{IsBinaryRelation}
We have the following general constructors.
\Declaration{BinaryRelationByElements}
\Declaration{IdentityBinaryRelation}
\Declaration{EmptyBinaryRelation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Properties and Attributes of Binary Relations}
\Declaration{IsReflexiveBinaryRelation}
\Declaration{IsSymmetricBinaryRelation}
\Declaration{IsTransitiveBinaryRelation}
\Declaration{IsAntisymmetricBinaryRelation}
\Declaration{IsPreOrderBinaryRelation}
\Declaration{IsPartialOrderBinaryRelation}
\Declaration{IsHasseDiagram}
\Declaration{IsEquivalenceRelation}
\Declaration{Successors}
\Declaration{DegreeOfBinaryRelation}
\Declaration{PartialOrderOfHasseDiagram}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Binary Relations on Points}
We have special construction methods when the underlying <X> of our relation
is the set of integers $\{1,\dots, n \}$.
\Declaration{BinaryRelationOnPoints}
\Declaration{RandomBinaryRelationOnPoints}
\Declaration{AsBinaryRelationOnPoints}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Closure Operations and Other Constructors}
\Declaration{ReflexiveClosureBinaryRelation}
\Declaration{SymmetricClosureBinaryRelation}
\Declaration{TransitiveClosureBinaryRelation}
\Declaration{HasseDiagramBinaryRelation}
\Declaration{StronglyConnectedComponents}
\Declaration{PartialOrderByOrderingFunction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Equivalence Relations}
\index{equivalence relation}
An *equivalence relation* <E> over the set <X> is a relation on <X> which
is reflexive, symmetric, and transitive.
of the set <X>. A *partition* <P> is a set of subsets of <X> such that
for all $R,S\in P$ $R\cap S$ is the empty set and $\cup P=X$.
An equivalence relation induces a partition such that if $(x,y)\in E$ then
$x,y$ are in the same element of <P>.
Like all binary relations in {\GAP} equivalence
relations are regarded as general endomorphic mappings (and the operations,
properties and attributes of general mappings are available).
However, partitions provide an efficient way of representing equivalence
relations. Moreover, only the non-singleton classes
or blocks are listed allowing for small equivalence relations to be
represented on infinite sets. Hence the main attribute of equivalence
relations is `EquivalenceRelationPartition' which provides the partition
induced by the given equivalence.
\Declaration{EquivalenceRelationByPartition}
\Declaration{EquivalenceRelationByRelation}
\Declaration{EquivalenceRelationByPairs}
\Declaration{EquivalenceRelationByProperty}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Attributes of and Operations on Equivalence Relations}
\Declaration{EquivalenceRelationPartition}
\Declaration{GeneratorsOfEquivalenceRelationPartition}
\Declaration{JoinEquivalenceRelations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\Section{Equivalence Classes}
\Declaration{IsEquivalenceClass}
\Declaration{EquivalenceClassRelation}
\Declaration{EquivalenceClasses}!{attribute}
\Declaration{EquivalenceClassOfElement}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%E
|
