31 Relations

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.

Sections

  1. General Binary Relations
  2. Equivalence Relations

31.1 General Binary Relations

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

    31.2 Equivalence Relations

  • 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
    February 2000