Quelle  congpairs.gi   Sprache: unbekannt

############################################################################
##
##  congruences/congpairs.gi
##  Copyright (C) 2015-2022                               Michael C. Young
##
##  Licensing information can be found in the README file of this package.
##
#############################################################################

#############################################################################
## This file contains functions for any congruence of a semigroup with
## generating pairs, regardless of representation.
#############################################################################

InstallImmediateMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
                       IsMagmaCongruence and IsSemigroupCongruence
                         and HasGeneratingPairsOfMagmaCongruence,
                       0,
                       GeneratingPairsOfMagmaCongruence);

InstallImmediateMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
                       IsLeftMagmaCongruence and IsLeftSemigroupCongruence
                         and HasGeneratingPairsOfLeftMagmaCongruence,
                       0,
                       GeneratingPairsOfLeftMagmaCongruence);

InstallImmediateMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
                       IsRightMagmaCongruence and IsRightSemigroupCongruence
                         and HasGeneratingPairsOfRightMagmaCongruence,
                       0,
                       GeneratingPairsOfRightMagmaCongruence);

BindGlobal("SEMIGROUPS_ImmediateNoGeneratingPairs",
function(C)
  if IsEmpty(GeneratingPairsOfMagmaCongruence(C)) then
    return [];
  fi;
  TryNextMethod();
end);

InstallImmediateMethod(GeneratingPairsOfLeftMagmaCongruence,
                       IsMagmaCongruence and IsSemigroupCongruence
                         and HasGeneratingPairsOfMagmaCongruence,
                       0,
                       SEMIGROUPS_ImmediateNoGeneratingPairs);

InstallImmediateMethod(GeneratingPairsOfRightMagmaCongruence,
                       IsMagmaCongruence and IsSemigroupCongruence
                         and HasGeneratingPairsOfMagmaCongruence,
                       0,
                       SEMIGROUPS_ImmediateNoGeneratingPairs);

# Some types of congruences (such as CongruenceByKernelAndTrace) do not know
# their generating pairs by default, and hence we require the following methods
# in addition to the immediate methods above.

InstallMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
"for a right semigroup congruence",
[IsRightSemigroupCongruence],
GeneratingPairsOfRightMagmaCongruence);

InstallMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
"for a left semigroup congruence",
[IsLeftSemigroupCongruence],
GeneratingPairsOfLeftMagmaCongruence);

InstallMethod(GeneratingPairsOfLeftRightOrTwoSidedCongruence,
"for a semigroup congruence",
[IsSemigroupCongruence],
GeneratingPairsOfMagmaCongruence);

InstallMethod(AsSemigroupCongruenceByGeneratingPairs,
"for semigroup congruence",
[IsSemigroupCongruence],
function(C)
  local S, pairs;
  S := Range(C);
  pairs := GeneratingPairsOfMagmaCongruence(C);
  return SemigroupCongruenceByGeneratingPairs(S, pairs);
end);

InstallMethod(AsRightSemigroupCongruenceByGeneratingPairs,
"for a right semigroup congruence",
[IsRightSemigroupCongruence],
function(C)
  local S, pairs;
  S := Range(C);
  pairs := GeneratingPairsOfRightMagmaCongruence(C);
  return RightSemigroupCongruenceByGeneratingPairs(S, pairs);
end);

InstallMethod(AsLeftSemigroupCongruenceByGeneratingPairs,
"for a left semigroup congruence",
[IsLeftSemigroupCongruence],
function(C)
  local S, pairs;
  S := Range(C);
  pairs := GeneratingPairsOfLeftMagmaCongruence(C);
  return LeftSemigroupCongruenceByGeneratingPairs(S, pairs);
end);

#############################################################################
# Properties of congruences
#############################################################################

InstallMethod(IsRightSemigroupCongruence,
"for a left semigroup congruence with known generating pairs",
[IsLeftSemigroupCongruence and HasGeneratingPairsOfLeftMagmaCongruence],
function(congl)
  local pairs, cong2;
  # Is this left congruence right-compatible?
  # First, create the 2-sided congruence generated by these pairs.
  pairs := GeneratingPairsOfLeftMagmaCongruence(congl);
  cong2 := SemigroupCongruence(Range(congl), pairs);

  # congl is right-compatible iff these describe the same relation
  if congl = cong2 then
    SetGeneratingPairsOfMagmaCongruence(congl, pairs);
    SetIsSemigroupCongruence(congl, true);
    return true;
  else
    SetIsSemigroupCongruence(congl, false);
    return false;
  fi;
end);

InstallMethod(IsLeftSemigroupCongruence,
"for a right semigroup congruence with known generating pairs",
[IsRightSemigroupCongruence and HasGeneratingPairsOfRightMagmaCongruence],
function(congr)
  local pairs, cong2;
  # Is this right congruence left-compatible?
  # First, create the 2-sided congruence generated by these pairs.
  pairs := GeneratingPairsOfRightMagmaCongruence(congr);
  cong2 := SemigroupCongruence(Range(congr), pairs);

  # congr is left-compatible iff these describe the same relation
  if congr = cong2 then
    SetGeneratingPairsOfMagmaCongruence(congr, pairs);
    SetIsSemigroupCongruence(congr, true);
    return true;
  else
    SetIsSemigroupCongruence(congr, false);
    return false;
  fi;
end);

InstallMethod(IsSemigroupCongruence,
"for a left semigroup congruence with known generating pairs",
[IsLeftSemigroupCongruence and HasGeneratingPairsOfLeftMagmaCongruence],
IsRightSemigroupCongruence);

# The method below matches more than one declaration of IsSemigroupCongruence,
# hence the Other
InstallOtherMethod(IsSemigroupCongruence,
"for a right semigroup congruence with known generating pairs",
[IsRightSemigroupCongruence and HasGeneratingPairsOfRightMagmaCongruence],
IsLeftSemigroupCongruence);

#############################################################################
# Printing and viewing of congruences
#############################################################################

InstallMethod(PrintObj,
"for left, right, or 2-sided congruences with known generating pairs",
[IsLeftRightOrTwoSidedCongruence
 and HasGeneratingPairsOfLeftRightOrTwoSidedCongruence],
10,
function(C)
  local string;
  if not IsMagmaCongruence(C) then
    # Don't need to check IsSemigroupCongruence because we check
    # IsLeftRightOrTwoSidedCongruence above.
    string := ShallowCopy(CongruenceHandednessString(C));
    string[1] := UppercaseChar(string[1]);
  else
    string := "";
  fi;

  Print(string, "SemigroupCongruence( ");
  PrintObj(Range(C));
  Print(", ");
  Print(GeneratingPairsOfLeftRightOrTwoSidedCongruence(C));
  Print(" )");
end);

InstallMethod(ViewObj,
"for left, right, or 2-sided congruences with known generating pairs",
[IsLeftRightOrTwoSidedCongruence
 and HasGeneratingPairsOfLeftRightOrTwoSidedCongruence],
9,  # to beat the library method
function(C)
  Print("<", CongruenceHandednessString(C), " semigroup congruence over ");
  ViewObj(Range(C));
  Print(" with ",
        Size(GeneratingPairsOfLeftRightOrTwoSidedCongruence(C)),
        " generating pairs>");
end);

########################################################################
# Comparison operators
########################################################################

InstallMethod(\=,
"for left, right, or 2-sided congruences with known generating pairs",
[IsLeftRightOrTwoSidedCongruence and
 HasGeneratingPairsOfLeftRightOrTwoSidedCongruence,
 IsLeftRightOrTwoSidedCongruence and
 HasGeneratingPairsOfLeftRightOrTwoSidedCongruence],
function(lhop, rhop)
  local lpairs, rpairs;
  if CongruenceHandednessString(lhop) <> CongruenceHandednessString(rhop) then
    TryNextMethod();
  fi;

  lpairs := GeneratingPairsOfLeftRightOrTwoSidedCongruence(lhop);
  rpairs := GeneratingPairsOfLeftRightOrTwoSidedCongruence(rhop);
  return Range(lhop) = Range(rhop)
         and ForAll(lpairs, x -> x in rhop)
         and ForAll(rpairs, x -> x in lhop);
end);

########################################################################
# Algebraic operators
########################################################################

BindGlobal("_JoinLeftRightOrTwoSidedCongruences",
function(XSemigroupCongruence, GeneratingPairsOfXCongruence, lhop, rhop)
  local pairs;
  if Range(lhop) <> Range(rhop) then
    ErrorNoReturn("cannot form the join of congruences over ",
                  "different semigroups");
  elif lhop = rhop then
    return lhop;
  fi;
  pairs := Concatenation(GeneratingPairsOfXCongruence(lhop),
                         GeneratingPairsOfXCongruence(rhop));
  return XSemigroupCongruence(Range(lhop), pairs);
end);

InstallMethod(JoinSemigroupCongruences,
"for a semigroup congruence with known generating pairs",
[IsSemigroupCongruence and HasGeneratingPairsOfMagmaCongruence,
 IsSemigroupCongruence and HasGeneratingPairsOfMagmaCongruence],
function(lhop, rhop)
  return _JoinLeftRightOrTwoSidedCongruences(SemigroupCongruence,
                             GeneratingPairsOfMagmaCongruence,
                             lhop,
                             rhop);
end);

InstallMethod(JoinLeftSemigroupCongruences,
"for a left semigroup congruence with known generating pairs",
[IsLeftSemigroupCongruence and HasGeneratingPairsOfLeftMagmaCongruence,
 IsLeftSemigroupCongruence and HasGeneratingPairsOfLeftMagmaCongruence],
function(lhop, rhop)
  return _JoinLeftRightOrTwoSidedCongruences(LeftSemigroupCongruence,
                             GeneratingPairsOfLeftMagmaCongruence,
                             lhop,
                             rhop);
end);

InstallMethod(JoinRightSemigroupCongruences,
"for a right semigroup congruence with known generating pairs",
[IsRightSemigroupCongruence and HasGeneratingPairsOfRightMagmaCongruence,
 IsRightSemigroupCongruence and HasGeneratingPairsOfRightMagmaCongruence],
function(lhop, rhop)
  return _JoinLeftRightOrTwoSidedCongruences(RightSemigroupCongruence,
                             GeneratingPairsOfRightMagmaCongruence,
                             lhop,
                             rhop);
end);