Cтраница 4
Это свойство позволяет назвать [ N, ] свободным моноидом с одной образующей, а [ Р, ] - свободной полугруппой с одной образующей. [46]
Более того, положив к ( х) х для всех х X, легко видеть, что F оказывается свободной полугруппой со свободной порождающей системой X. Однако свойство единицы позволяет эти элементы выбросить. Последний часто отождествляется с пустым словом. Условимся считать, что длина пустого слова равна нулю. [47]
В этой последней главе мы намерены показать, что имеется целый ряд комбинаторных результатов и методов, которые объясняются фактически алгебраическими свойствами свободных полугрупп и моноидов. С этой целью мы излагаем набросок принадлежащей Фоата [1965] теории1), которая не только дает доказательство Главной теоремы2) Мак-Магона, но также в некоторой степени вскрывает ее таинственную природу. Выбор этой теории среди прочих объясняется тем фактом, что использованные здесь приемы представляются достаточно типичными, чтобы стимулировать другие обобщения чисто комбинаторных результатов в аналогичных направлениях. [48]
Ьа Ь2У свободной полугруппы а, Ь не является конечно определенной ( заметим, что оценка 4 здесь точная; все 3-порожденные подполугруппы свободных полугрупп конечно определены, причем для 2-порожденных из них попросту выполняется альтернатива - быть подполугруппой бесконечной моногенной полугруппы или быть изоморфной свободной полугруппе ранга 2, см. [30], с. Обратно, любая рекурсивно определенная полугруппа вложима в некоторую к. [49]
В § 0.7 мы видели, что свободную ассоциативную алгебру k X на множестве X над полем k можно определить как полугрупповую алгебру свободной полугруппы Sx над k слабый алгоритм, выполняющийся в свободной алгебре, можно считать аналогом условия ( iii) теоремы 6.1. Используя эту теорему, мы покажем, что однородные элементы алгебры k X образуют свободную полугруппу. В дальнейшем будем считать множество X линейно упорядоченным и упорядочим одночлены от X разной длины по их длине, а одночлены одинаковой длины-лексикографически. [50]