Вернуться к списку примеров

Соответствия в системе GAP

Для задания соответствия в GAP необходимо указать область отправления X, область прибытия Y и либо график соответствия G (который является списком, состоящим из упорядоченных пар, в которых первый элемент принадлежит области отправления, а второй - области прибытия), либо функцию, которая будет определять элемент из Y, соответствующий заданному элементу из X.

Для задания соответствий с помощью графика используется функция GeneralMappingByElements. В качестве примера зададим соответствие между множествами натуральных чисел и целых чисел, определяемое упорядоченными парами (1,1), (2,2), (2,-2), (3,3) и (4,3). Обратите внимание на то, что обыкновенный список их двух элементов [a,b] является упорядоченной парой в обычном понимании этого термина, однако не может быть использован для задания графика соответствия - к нему необходимо сначала применить функцию Tuple для  создания упорядоченной пары специального вида.

gap> l:=[[1,1],[2,2],[2,-2],[3,3],[4,3]];
[ [ 1, 1 ], [ 2, 2 ], [ 2, -2 ], [ 3, 3 ], [ 4, 3 ] ]
gap> lt:=List(l,Tuple);
[ Tuple( [ 1, 1 ] ), Tuple( [ 2, 2 ] ), Tuple( [ 2, -2 ] ),
  Tuple( [ 3, 3 ] ), Tuple( [ 4, 3 ] ) ]
gap> f:=GeneralMappingByElements(PositiveIntegers,Integers,lt);
<general mapping: PositiveIntegers -> Integers >
Для задания соответствий вторым способом используется функция MappingByFunction. В качестве примера зададим функцию, которая каждому целому числу будет ставить в соответствие его остаток от деления на 2:
gap> g:=MappingByFunction(Integers,Integers, x -> x mod 2);
MappingByFunction( Integers, Integers, function( x ) ... end )
Область отправления и область прибытия соответствия определяются с помощью функций Source и Range соответственно:
gap> Source(f);
PositiveIntegers
gap> Source(g);
Integers
gap> Range(f);
Integers
gap> Range(g);
Integers
Если f - cоответствие, то определяющее его отношение можно получить с помощью функции UnderlyingRelation. Обратно, имея отношение, можно узнать соответствие, из которого оно получено, с помощью функции UnderlyingGeneralMapping:
gap> r1:=UnderlyingRelation(f);
<object>
gap> r2:=UnderlyingRelation(g);
<object>
gap> g=UnderlyingGeneralMapping(r2);
true
Поскольку r1 конечно, мы можем теперь получить график соответствия как список элементов r1:
gap> l:=AsList(r1);
[ Tuple( [ 1, 1 ] ), Tuple( [ 2, 2 ] ), Tuple( [ 2, -2 ] ),
  Tuple( [ 3, 3 ] ), Tuple( [ 4, 3 ] ) ]
После этого несложно вычислить его область определения и область значения, получив их как множество соответственно первых и вторых компонент упорядоченных пар, входящих в его график:
gap> Set(List(l, x -> x[1]));
[ 1, 2, 3, 4 ]
gap> Set(List(l, x -> x[2]));
[ -2, 1, 2, 3 ]
Для второго соответствия мы не можем получить бесконечный список упорядоченных пар, но зато можем проверить, принадлежит ли та или иная упорядоченная пара графику соответствия:
gap> Tuple([10,0]) in r2;
true
gap> Tuple([10,1]) in r2;
false
Далее, образы и прообразы элементов можно находить с помощью функций Images и PreImages (см. также другие функции для работы с образами и прообразами в конце данной статьи):
gap> Images(f,1);
[ 1 ]
gap> Images(f,2);
[ -2, 2 ]
gap> PreImages(f,2);
[ 2 ]
gap> PreImages(f,3);
[ 3, 4 ]
Обратное соответствие определяется с помощью функции InverseGeneralMapping:
gap> InverseGeneralMapping(f);
InverseGeneralMapping( <general mapping: PositiveIntegers -> Integers > )
Функция CompositionMapping вычисляет композицию соответствий. Пример ее применения будет дан ниже. Обратите внимание на порядок записи аргументов в ней - соответствия начинают рассматриваться, начиная с последнего.

Завершим первую половину статьи заданием двух соответствий специального вида. С помощью функции IdentityMapping задается тождественное отображение:
gap> i:=IdentityMapping(Integers);
IdentityMapping( Integers )
gap> Images(i,100);
[ 100 ]
Далее, если область прибытия содержит нулевой элемент, то можно задать отображение в него всех элементов области отправления с помощью функции ZeroMapping:
gap> z:=ZeroMapping(PositiveIntegers,Integers);
ZeroMapping( PositiveIntegers, Integers )
gap> Images(z,2);
[ 0 ]
Прежде чем перейти к следующему примеру, необходимо сделать небольшое примечание об ограничениях, налагаемых в GAP на область отправления и область прибытия. Для задания соответствия они должны являться доменами (domain) - так в GAP называются множества с дополнительной структурой (например, группы, классы сопряженных элементов, векторные пространства и т.п.). Поэтому в предыдущих примерах в их областей отправления и прибытия использовались системы натуральных и целых чисел, а не их конечные подмножества. Примерам соответствий, в которых областями отправления и прибытия являются конечные множества с дополнительной алгебраической структурой, посвящена вторая половина данной статьи. Тем, кто впервые изучает курс алгебры, рекомендуется вернуться к этому материалу после ознакомления с элементами теории групп.

Для построения примера сначала зададим симметрические группы подстановок третьей и второй степени:
gap> S3:=SymmetricGroup(3);
Sym( [ 1 .. 3 ] )
gap> S2:=SymmetricGroup(2);
Sym( [ 1 .. 2 ] )
Кроме того, нам понадобится мультипликативная группа кольца целых чисел {-1,1}.Для ее задания мы сначала создадим полугруппу, порожденную -1, а потом укажем, что будем рассматривать ее, как группу:
gap> U:=Semigroup(-1);
<semigroup with 1 generator>
gap> AsList(U);
[ -1, 1 ]
gap> U:=AsGroup(U);
<group of size 2 with 1 generators>
Примечание. Для построения примера было бы достаточно использовать полугруппу U, однако мы превратили ее в группу, чтобы обратить внимание на еще одну тонкость. Дело в том, что в GAP нельзя непосредственно задать группу, состоящую из целых, рациональных или комплексных чисел, так как тогда невозможно будет однозначно истолковать операцию  ^, которая, в зависимости от аргументов, может означать как возведение в степень, так и сопряжение с помощью элемента группы (и даже образ элемента под действием отображения). Поэтому U сначала задается в виде полугруппы, а потом "превращается" в группу.

Теперь зададим цепочку соответствий между S3, U и S2. Первое из них будет отображать подстановки из S3 в их знак, равный единице, если подстановка четная, и -1, если подстановка нечетная:
gap> f:=MappingByFunction(S3,U, SignPerm);
MappingByFunction( Sym( [ 1 .. 3 ] ), <group of size 2 with 1 generators>,
         function( perm ) ... end )
Второе отображение действует из U в S2 и отображает -1 в тождественную подстановку (), а 1 - в транспозицию (1,2). Заметим, что отображение g намеренно выбрано таким образом, чтобы оно не являлось гомоморфизмом, поскольку в для гомоморфизмов в GAP имеются свои, более эффективные инструменты.
gap> g:=GeneralMappingByElements(U,S2,[Tuple([-1,()]),Tuple([1,(1,2)])]);
<general mapping: Group( [ -1 ] ) -> SymmetricGroup( [ 1 .. 2 ] ) >
Наконец, третье соответствие отображает все подстановки из S2 в тождественную подстановку, а четвертое является тождественным отображением на S2:
gap> h:=MappingByFunction(S2,S2, x -> ());
MappingByFunction( Sym( [ 1 .. 2 ] ), Sym( [ 1 .. 2 ] ), function( x ) ... end )
gap> i:=IdentityMapping(S2);
IdentityMapping( Sym( [ 1 .. 2 ] ) )
Теперь мы можем вычислить композицию g и h (обратите внимание на порядок следования отображений - они выполняются в обратном порядке):
comp:=CompositionMapping(h,g);
CompositionMapping( <general mapping: SymmetricGroup( [ 1 .. 2 ] ) ->
  SymmetricGroup( [ 1 .. 2 ] ) >, <general mapping: Group( [ -1 ] ) ->
  SymmetricGroup( [ 1 .. 2 ] ) > )
Аналогично вычисляется композиция трех отображений:
gap> comp:=CompositionMapping(h,g,f);
CompositionMapping( MappingByFunction( Sym( [ 1 .. 2 ] ), Sym( [ 1 .. 2 ] ),
  function( x ) ... end ), CompositionMapping( <general mapping: Group( [ -1 ] ) ->
  SymmetricGroup( [ 1 .. 2 ] ) >, MappingByFunction( Sym( [ 1 .. 3 ] ),
  <group of size 2 with 1 generators>,  function( perm ) ... end ) ) )
Легко видеть, что последнее отображение переводит любой элемент группы S3 в тождественную подстановку. Проверим это, например, для подстановки (1,2,3), обратив внимание на еще один вариант записи образа элемента относительно отображения:
gap> (1,2,3)^comp;
()
Функция InverseGeneralMapping вычисляет обратное соответствие. Вычислим обратное соответствие к соответствию g, а затем найдем образы элементов S2 под его действием:
gap> v:=InverseGeneralMapping(g);
InverseGeneralMapping( <mapping: Group( [ -1 ] ) -> SymmetricGroup( [ 1 .. 2 ] ) > )
gap> ()^v;
-1
gap> (1,2)^v;
1
Для использования в последующих примерах вычислим композицию t соответствий f и g:
gap> t:=CompositionMapping(g,f);
CompositionMapping( <mapping: Group( [ -1 ] ) ->
  SymmetricGroup( [ 1 .. 2 ] ) >, MappingByFunction( Sym( [ 1 .. 3 ] ),
  <group of size 2 with 1 generators>, function( perm ) ... end ) )
Очевидным образом определяется, является ли t всюду определенным, функциональным, инъективным, сюръективным и биективным:
gap> IsTotal(t);
true
gap> IsSingleValued(t);
true
gap> IsInjective(t);
false
gap> IsSurjective(t);
true
gap> IsBijective(t);
false
Как и в предыдущих примерах, мы можем получить график соответствия t:
gap> UnderlyingRelation(t);
<object>
gap> AsList(last);
[ Tuple( [ (), (1,2) ] ), Tuple( [ (2,3), () ] ), Tuple( [ (1,2), () ] ),
  Tuple( [ (1,2,3), (1,2) ] ), Tuple( [ (1,3,2), (1,2) ] ), Tuple( [ (1,3), () ] ) ]
В завершение укажем функции, которые используются для определения образов и прообразов отдельных элементов и их множеств. Напомним, что область отправления и область прибытия опредеделяются с помощью функций Source и Range соответвственно:
gap> Range(t);
Sym( [ 1 .. 2 ] )
gap> Source(t);
Sym( [ 1 .. 3 ] )
Образ соответствия можно определять с помощью функций ImagesSource или Image:
gap> ImagesSource(t);
Sym( [ 1 .. 2 ] )
gap> Image(t);
Sym( [ 1 .. 2 ] )
Кроме того, имеются различные функции для определения образов элемента или даже целого множества:
gap> ImagesElm(t,(1,2,3));            # множество всех образов элемента
[ (1,2) ]
gap> ImagesRepresentative(t,(1,2,3)); # представитель множества образов элемента
(1,2)
gap> ImagesSet(t,[(1,2,3),(1,2)]);    # множество всех образов элементов множества
[ (), (1,2) ]                         # (второй аргумент и результат - множества)
 gap> Images(t,[(1,2,3),(1,2)]);       # образ множества или поддомена
 [ (), (1,2) ]                         # (второй аргумент и результат -
                                      # множества или домены)
gap> ImageElm(t,(1,2,3));             # образ элемента (для всюду определенного
(1,2)                                 # и функционального соответствия)
gap> Image(t,(1,2,3));                # для всюду определенного и функционального
(1,2)                                 # соответствия в зависмости от второго аргумента
                                      # - образ всего соответствия, отдельного
                                      # элемента, подмножества или поддомена

Аналогичная функциональность имеется и для прообразов:
gap> PreImagesRange(t);               # прообраз (область определения) соответствия
Sym( [ 1 .. 3 ] )
gap> PreImagesElm(t,());              # множество всех прообразов элемента
[ (2,3), (1,2), (1,3) ]
gap> PreImagesRepresentative(t,());   # представитель множества прообразов элемента  
(2,3)
gap> PreImagesSet(t,[(1,2)]);         # множество всех прообразов элементов множества
[ (), (1,2,3), (1,3,2) ]
gap> PreImages(t);                    # прообраз (область определения соответствия)
Sym( [ 1 .. 3 ] )
gap> PreImages(t,(1,2));              # прообраз элемента
[ (), (1,2,3), (1,3,2) ]
gap> PreImages(t,[(),(1,2)]);         # прообраз множества или поддомена
[ (), (2,3), (1,2), (1,2,3), (1,3,2), (1,3) ]
gap> PreImageElm(g,(1,2));            # прообраз элемента (для инъективного и
1                                     # сюръективного соответствия)
gap> PreImage(t);                     # прообраз соответствия (не обязательно
Sym( [ 1 .. 3 ] )                     # сюръективного и инъективного)
gap> PreImage(g,(1,2));               # прообраз элемента (для сюръективного
1                                     # и инъективного соответствия
gap> PreImage(g,[(),(1,2)]);          # прообраз множества или поддомена (для
[ -1, 1 ]                             # инъективного и сюръективного соответствия,
                                      # результат - множество или домен)
Более подробно различия между функциями для работы с образами и прообразами, а также особенности их использования описаны в разделе "Mappings" документации по системе GAP.


Вернуться к списку примеров