9.7. Полугруппы, образующие и соотношения

Сейчас мы объясним, как только что доказанное утверждение о двусторонних ассоциативных исчислени­ях переводится на алгебраический язык. (Ничего нового по существу при этом не утверждается, это просто пе­ревод.) Напомним некоторые сведения из алгебры.

Полугруппой называется произвольное непустое мно­жество С с ассоциативной операцией, записываемой как умножение, причём существует единичный элемент 1, для которого 1хш = з;х1 = 1 для всех х Е С (Полугруп­пы без единичного элемента нам не потребуются.) Пусть С — некоторая полугруппа. Говорят, что множество А С С С является множеством образующих для полугруп­пы С, если всякий элемент полугруппы может быть полу­чен как произведение образующих (возможно, пустое — такое произведение считается равным 1). Полугруппа на­зывается конечно порождённой, если она имеет конечное множество образующих.

Пусть А = {а\,..., ап} — алфавит. Тогда множество всех слов в алфавите А образует полугруппу. Умноже­ние в ней — это конкатенация слов, то есть приписы­вание одного к другому. Единичный элемент — пустое слово. Очевидно, а\,..., ап являются образующими этой полугруппы. (Точнее следовало бы говорить об однобук-венных словах как образующих.) Эта полугруппа назы­вается свободной полугруппой с образующими а\,..., ап. Будем обозначать её 7-(а\,..., а„).

Пусть С — произвольная полугруппа, и д\,..., дп — любые её элементы. Тогда существует единственный го­моморфизм К полугруппы 7-(а\,..., ап) в полугруппу С, для которого /г(а,-) = <?,-. (Гомоморфизмом полугрупп на­зывают отображение, при котором образ произведения равен произведению образов и единица переходит в еди­ницу.) Он переводит слово из символов а,- в произведение соответствующих элементов <?,-; образом пустого слова является единичный элемент. Очевидно, образ этого го­моморфизма совпадает со всей полугруппой С тогда и только тогда, когда элементы д\,..., дп являются обра­зующими группы С

Соотношениями мы будем называть равенства ви­да X = У, где X и У — элементы свободной полугруп­пы 7-(а\,..., ап), то есть слова в алфавите А. Говорят, что соотношение X = У выполнено в полугруппе С с выделенными элементами д\,..., дп, если образы слов X и У при описанном гомоморфизме, то есть произведе­ния соответствующих элементов д{, равны. Пусть имеет­ся некоторый набор соотношений Х\ = У\,..., Л* д. = У;.. Будем рассматривать различные полугруппы С с выде­ленными п элементами, в которых выполнены все эти со­отношения, и в которых выделенные элементы являются образующими. (Например, полугруппа из единственного единичного элемента также входит в их число.) Среди та­ких полугрупп, как мы сейчас увидим, есть «максималь­нал», в которой выполнено меньше всего соотношении.

Введём на словах алфавита А отношение эквивалент­ности, считая, что Р = <5, если Р можно преобразовать в <5 в двустороннем ассоциативном исчислении с прави­лами Х\ -Н- У\,..., Хк -Н- Ук. (Другими словами, в любом слове разрешается заменить его подслово Л; на подсло-во У,- и наоборот.) Очевидно, это отношение действитель­но будет отношением эквивалентности. Заметим, что ес­ли Р = <5, то РК = <5Л и КР = Л<5 для произвольно­го слова К (в цепочке преобразований можно дописать ко всем словам К слева или справа). Рассмотрим классы эквивалентности этого отношения. На них можно опреде­лить операцию произведения, считая произведением двух классов, содержащих слова Р и <5, класс, содержащий их конкатенацию Р<5- Отмеченное свойство отношения эквивалентности гарантирует корректность этого опре­деления (класс-произведение не зависит от выбора пред­ставителей в сомножителях). Тем самым мы получаем по­лугруппу С, в которой единичным элементом будет класс пустого слова, а классы = [а,-] эквивалентности одно-буквенных слов будут образующими. Её обозначают

и называют полугруппой с образующими а\,..., ак и со­отношениями Х\ = У\,...,Хк = У&. Ясно, что в полу­группе С выполнены исходные соотношения Л; = У,-. Легко понять также, что в ней нет никаких других со­отношений, кроме следствий исходных:

Теорема 63. Если соотношение X = У выполнено в полугруппе

то оно выполнено в любой полугруппе С с выделенными элементами д\ ,...,<?„, в которой выполнены все соотно­шения Л; = У,-.

<] В самом деле, словам X и У соответствуют их клас­сы эквивалентности по описанному отношению, так что

ап)/(Хг = У1.,....,Хк=¥к)

ап)/(Х1=¥1.,....,Хк=¥к)из X можно получить У по правилам двустороннего ас­социативного исчисления. Но все эти правила не меняют значение элемента в любой полугруппе, в которой вы­полнены соотношения Х{ = У,-, и потому в любой такой полугруппе словам X и У будет соответствовать один и тот же элемент. >

78. Рассмотрим полугруппу с двумя образующими <ц и 02 и соотношениями си аз = Л, азси = Л. Что это за полугруппа?

79. Рассмотрим полугруппу с двумя образующими си и 02 и соотношением си аз = а.2а.\. Что это за полугруппа?

80. Рассмотрим полугруппу с двумя образующими си и 02 и соотношениями си си = Л, 0202 = Л, си <32 = а.2а.\ . Что это за полугруппа?

81. Рассмотрим полугруппу с двумя образующими си и 02

И СООТНОШеНИЯМИ СИ СИ   = Л, 020202  = Л, 0102  = 020201. Что

это за полугруппа?

Теперь мы можем сформулировать утверждение о су­ществовании неразрешимых двусторонних ассоциатив­ных исчислений в терминах полугрупп.

Теорема 64. Существует полугруппа, с конечным чи­слом образующих и конечным числом соотношений, в ко­торой задача проверки равенства двух слов, составлен­ных из образующих, алгоритмически неразрешима (нет алгоритма, который по двум словам такого вида узнавал, равны они в этой полугруппе или не равны).

<] Согласно определению, равенство двух слов, соста­вленных из образующих, означает возможность преобра­зовать одно из них в другое по правилам двустороннего исчисления, так что эта теорема представляет собой пе­реформулировку теоремы 62 (с. 124) >

Эта теорема была доказана в 1947 году независимо По­стом и Андреем Андреевичем Марковым (младшим); вско­ре после этого Пётр Сергеевич Новиков усилил её, построив пример группы (а не только полугруппы!) с конечным числом образующих и соотношений, для которой проблема равенства двух слов из образующих неразрешима.