Свободные полугруппы

Введение

—————————————————————————————————- 3

1. Понятие свободной полугруппы————————————- 4

1.1. Слова—————————————————————————————— 4

1.2. Понятие свободной полугруппы————————————— 5

2. Применение—————————————————————————- 9

2.1. Циклические (моногенные) полугруппы———————- 9

2.2. Сводные коммутативные полугруппы————————— 12

2.3. Упражнения————————————————————————— 13

3. Обзор результатов по проблеме Туэ—————————— 15

Литература

—————————————————————————————;

Дипломная работа посвящена теории свободных полугрупп. Свободные алгебраические объекты играют важную роль в общей алгебре, поскольку любая алгебраическая структура является гомоморфным образом свободной алгебраической структуры того же типа.

В теории полугрупп свободные объекты описываются конструктивно, именно как полугруппы слов над некоторым алфавитом. Поэтому большое место в работе уделено рассмотрению свойств полугрупп слов. Эти свойства носят, как правило, комбинаторный характер.

Кроме того, в работе изучаются и абстрактные свойства свободных полугрупп и некоторых связанных с ним полугрупп.

В первом параграфе вводятся основные понятия и доказательства теорем о существовании и единственности свободных полугрупп с множеством образующих данной мощности.

Второй параграф посвящён двум применениям свободных полугрупп:

1) описание циклических полугрупп;

2) свободной коммутативной полугруппе.

Там же доказываются некоторые комбинаторные свойства слов над произвольным алфавитом.

В третьем параграфе даётся обзор проблематики Туэ о существовании бесквадратных и бескубных слов произвольной длины над различными алфавитами.

В дипломной работе используются книги [1 — 4] из приведённого списка библиографии.

1. Понятие свободной подгруппы

1.1. Слова

Алфавит, А — это непустое конечное множество. Буквы (символы) — элементы алфавита А. Слово над алфавитом, А — это конечная цепочка, состоящая из нуля или более букв из А, причем одна и та же буква может входить несколько раз. Цепочка, состоящая из нулевого количества букв, называется пустым словом и обозначается. Таким образом, 0, 1, 010, 1111 суть слова над алфавитом, А ={0, 1}. Множество всех слов над алфавитом, А обозначается W (A), а множество всех непустых слов обозначается Z (A).

Если u и v — слова над алфавитом А, то их катенация xy (результат приписывания) — тоже слово над А: и. Катенация является ассоциативной операцией, и пустое множество служит единицей по отношению к ней: x=x= для всех x. Если х — слово, а i — натуральное число, то обозначает слово, полученное катенацией i слов, каждое из которых есть х.

Длина слова х, обозначается, есть число букв в х, причем каждая буква считается столько раз, сколько раз она входит в х. Опять по определению =0. Функция длины обладает некоторыми свойствами логарифма: для всех слов х, у и неотрицательных некоторых i

.

В теории языков важнейшей операцией является операция морфизма. Морфизмом называется отображение h: W (A) M (A), где W (A) и M (A) -множества всех слов удовлетворяющие условию h (xy)=h (x)h (y) для всех слов х, у.

1.2. Понятие свободной полугруппы

Пусть S — полугруппа, а Х — ее непустое подмножество. Пересечение Т всех подполугрупп полугруппы S, содержащих Х, называется подполугруппой, порожденной множеством Х. Существовавние полугруппы Т вытекает из следующего простого факта: Непустое пересечение любого множества подполугрупп является подполугруппой.

Доказательство. Пусть Т — пересечение некоторого множества подполугрупп. Если х, у принадлежат Т, то х и у лежат в каждой из подполугрупп рассматриваемого множества. Но тогда в каждой из них лежит и произведение ху, а значит ху принадлежит Т. Ч.т.д.

Поэтому подполугруппы, содержащие множество Х существуют, например сама S, и пересечение их непусто (все они содержат Х). Значит Т — это наименьшая среди подполугрупп полугруппа S, содержащая Х. Если эта наименьшая подполугруппа совпадает с S, то говорят, что полугруппа S порождается множеством Х.

Полугруппа S=S (Х) называется свободной полугруппой со свободным порождающим множеством Х, если:

(1) S порождается множеством Х;

(2) для любого отображения, где Е — произвольная полугруппа, существует гомоморфизм такой, что

для любых х Х.

Теорема 1.1. (существование свободной полугруппы).

W=W (x) — свободная полугруппа со свободно порождающим множеством Х.

Доказательство. Оба свойства (1) и (2) свободной полугруппы проверим индукцией по длине слов W.

(1) Пусть Т — подполугруппа полугруппы W, порожденная множеством Х. Тогда любое слово w принадлежащее W, лежит в Т. Действительно, если =1, то w принадлежит Х и подмножество Т. Если >1, то w=w'x, где < и х принадлежит Х. следовательно, w', x принадлежит Т по предположению индукции. Так как Т — подполугруппа, а w — произведение двух элементов w' и х, то w принадлежит Т. Поэтому W подмножество Т. Обратное включение очевидно. Итак, T=W.

(2). Пусть — произвольное отображение множества Х в некоторую полугруппу Е с операцией. Определим элемент полугруппы Е индукцией по. Если =1,w принадлежит Х и мы положим

(*)

Если >1, то w=w'x где < и х принадлежит Х. Тогда и уже определены. Положим

(**)

Покажем, что отображение: WЕ является гомоморфизмом, то есть что для любых .

Проведем индукцию по длине второго сомножителя. Если =1, то доказываемое следует из равенства (**). Если >1, то =' х, где < и х принадлежит Х. Поэтому, учитывая (**) и индуктивное предположение получаем:

Кроме того, если х принадлежит Х, то в силу равенства (*). Итак, условия (1) и (2) выполнены. Ч.т.д.

Теорема 1.2. (свойство универсальности свободной полугруппы).

Для всякой полугруппы Е найдутся свободная полугруппа S и гомоморфное наложение: SЕ.

Доказательство. Пусть S — свободная полугруппа со свободно порождающим множеством Е. В силу свойства (2) из определения свободной полугруппы, тождественное отображение множества Е на себя продолжается до гомоморфизма: SЕ, который в данном случае оказался наложением. Ч.т.д.

Теорема 1.3. (о единственности свободной полугруппы).

Если S=S (x) — свободная полугруппа со свободно порождающим множеством Х, то существует изоморфизм полугруппы S на полугруппу W=W (x) слов в алфавите Х, причем, для всех х принадлежащих Х.

Доказательство. По Т1. и свойству (2) из определения свободной полугруппы, тождественное отображение множества Х на себя продолжается до гомоморфизмов: SW и: WS, причем, для любых х принадлежащих Х. Таким образом Х и Х.

По теореме «Если: АВ — гомоморфизм полугруппы, то — подполугруппа В «и свойству (1) и, то есть как, так и оказываются наложениями. Более того, поскольку для всех х принадлежащих Х, не трудно заметить, что для любого слова w в алфавите Х, то есть. Если некоторых a, b принадлежащих W, то

Следовательно — вложение, а значит и изморфизм. Ч.т.д.

Теорема 1.4. (об изоморфности свободных полугрупп) Свободные полугруппы S (X) и S (Y) изоморфны равномощны множества X и Y.

Доказательство. Необходимость. По теореме 1.3. имеем S (X)W (X) и S (Y) W (Y). В полугруппе W (X) неразложимыми элементами будут в точности буквы алфавита Х.

Пусть S (X) S (Y). Тогда W (X) W (Y). Поскольку при изоморфизме полугрупп сохраняются все алгебраические свойства, то неразложимые элементы перейдут в неразложимые. Значит между X и Y будет установлено взаимно однозначное соответствие.

Достаточность. Пусть X равномощно Y, то есть существует биекция f множества X на множество Y. Тогда f продолжается до гомоморфизма, а обратное продолжается до гомоморфизма .

Легко видеть, что гомоморфизмы и взаимно обратны — это изоморфизм свободных полугрупп S (X) и S (Y).Ч.т.д.

2. Применения

2.1. Циклические (моногенные) полугруппы

Полугруппа В называется циклической (моногенной), если в ней содержится такой элемент а, что всякий элемент х из В может быть записан в форме для некоторого n >0. Элемент а называется образующим (порождающим) циклической полугруппы. Важнейшим примером циклической полугруппы является полугруппа Р положительных целых чисел относительно сложения. Её образующим служит 1. Зафиксируем положительные числа n и d и рассмотрим разбиение множества Р, состоящее из одноэлементных классов [1]={1}, [2]={2},…,[d-1]={d-1} и бесконечных классов

[d]={d, d+n, d+2n, …, d+kn,…},

[d+1]={d+1, d+1+n, d+1+2n,…, d+1+kn,…},

[d+(n-1)]={d+(n-1), d+(n-1)+n, d+(n-1)+2n,…, d+(n-1)+kn,…}.

Убедимся, что это разбиение допустимо. В самом деле, пусть х, u[ I ], y, v[ j ], где 1 I, j< d+n. Возможны следующие четыре случая: 1) I, j < d, j d; 3) I d, j< d; 4) I, j d. В первом случае имеем: x=u=I и y=v=j, откуда [x+y]=[u+v], поскольку x+y=u+v. Во втором случае x=u=I, y=j+kn и v=j+Ln для подходящих k, L. Используя деление с остатком запишем

I + j — d=sn + r ,

где 0 r< n. Тогда

x + y = I + j + kn = d + (I + j — d) + kn = d + r + (s + k) n

и u + v = I + j + Ln = d + (I + j — d) + Ln = d + r + (s + L) n,

откуда [x + y] = [d + r] = [u + v]. Третий случай рассматривается аналогично. В четвертом случае, используя определение смежных классов, можно записать

x =I + kn = d + (I — d) + kn,

u = I + Ln = d + (I — d) + Ln,

y = j + pn = d + (j — d) + pn,

v = j + qn = d + (j — d) + qn.

Тогда

x + y = d + (d + (I — d) + (j — d)) + (k + p) n

и

u + v = d + (d +(I — d) + (j — d)) + (L + q) n.

Разделив с остатком, получим

d + (I — d) + (j — d) = sn + r,

где 0 r< n. Отсюда

x + y = d + r + (k + p + s) n

и

u + v = d + r + (L + q + s) n,

т.е. [x + y] = [d + r] = [u + v].

Факторполугруппу полугруппы Р по рассмотренному разбиению называют циклом с хвостом.

При d = 1 хвост оказывается пустым. Такую полугруппу называют циклом.

Теорема.

Всякая циклическая полугруппа изоморфна или аддитивной полугруппе Р положительных чисел, или некоторому циклу с хвостом (возможно пустым).

Доказательство. Пусть В — циклическая полугруппа с образующим а. Рассмотрим отображение полугруппы Р в полугруппу В, определяемое условием .

Ввиду циклической полугруппы В, оказывается наложением. В силу теоремы: «для всех m, n > 0.»

т.е. является гомоморфизмом. Из следующей теоремы:

Если — гомоморфное наложение полугрупп и — естественный гомоморфизм, то существует изоморфизм такой, что, вытекает, что В изоморфна факторполугруппе Р/, где =. Если все классы разбиения одноэлементны, то В изоморфна Р. В противном случае обозначим через d наименьшее целое число, входящее в неодноэлементный класс, а число n выберем так, чтобы d + n было наименьшим числом, отличным от d, но входящим в один класс с d. Тогда имеем классы [1], [2],…, [d — 1], [d], [d + 1],…, [d + n — 1], среди которых первые d — 1 одноэлементные и [d][d + I] при I= 1,2,…, n — 1. Докажем, что

[d + I] = [d + I + kn] (*)

при любых I и k. В силу определения разбиения, для этого достаточно установить, что

. (**)

При k = 0 это очевидно. Допустим, что (**) доказано при всех I и

k = 0,1,…, t — 1. Тогда, вспоминая, что, получаем

Тем самым равенство (**), а значит (*), доказано. Остаётся убедится, что разбиение совпадает с разбиением (d +n). С этой целью заметим, что одноэлементные классы этих разбиений совпадают. Ввиду равенства (*), для доказательства совпадения бесконечных классов достаточно установить, что смежные классы [d + I] и [d + j] разбиения, где, различны. Но если [d + I] = = [d + j], то

[d] = [d + n] = [d + j] + [n — j] = [d + I] + [n — j] = [d + (n — (j — I))]

и, поскольку 0< n — (j — I)

2.2. Свободные коммутативные полугруппы

Свободные коммутативные полугруппы определяются точно также, как свободные полугруппы, но только в классе коммутативных полугрупп.

Предложение 2.1.

Если — такие элементы полугруппы, что для любых i и j, то

где — произвольная подстановка на множестве {1, 2, …, n}.

Доказательство. При n = 2 утверждение теоремы справедливо по условию. Допустим, что теорема верна для n — 1 сомножителей. Если (n) = n, то учитывая теорему: «Произведение нескольких элементов полугруппы не зависит от расстановки скобок», и индуктивное предположение, имеем

.

Если n = (k), где k

Следствие.

Для любых элементов коммутативной полугруппы и любой подстановки на множестве {1, 2, …, n} справедливо равенство

.

Теорема 2. 2.

Если, А = {} - множество свободных образующих коммутативной полугруппы S, то S = {, — неотрицательные целые числа, одновременно не равные нулю}, причём различные наборы показателей () дают различные элементы S.

Доказательство. По теореме 1.2. существует гомоморфное наложение, при котором для всех =1, 2, …, n. Значит, каждый элемент sS имеет вид. Поскольку мультипликативная полугруппа {, } изоморфны аддитивной полугруппе, то различные её элементы будут иметь различные наборы показателей. Ч.т.д.

2.3.Упражнения

Для полугруппы слов W (X) верны следующие утверждения.

1. ef = gh e = gu и h = uf либо g = eu и f = uh, для некоторого слова u (возможно непустое).

2. Из ef = fe e = fk = kf для некоторого слова u либо f=eu=ue для некоторого слова u.

3. Если ef = fe, то следует слово h, для которого e = и f=, где k, m — натуральные числа.

Докажем эти утверждения.

(1). Пусть, и — слова в алфавите Х. По условию ef = gh. Если, то очевидно: e = g и f = h; в этом случае u = - пустое слово. Пусть nm. Будем считать, что n>m (случай m>n симметричен рассматриваемому). Имеем

=

=

откуда e = gu и h = uf для слова u = .

. Пусть для определённости и e = gu и h = uf. Тогда ef=(gu)f=g (uf)=gh. Ч.т.д.

(2) Это частный случай (1) при g = e и g = f.

(3) Пусть ef = fe. При ясно, что e = f, то имеем e=f=h=. Далее доказательство проведём индукцией по числу n=max (). Можно считать, что n = 2 имеем и =1, то есть е=ab и f=c, где a, b, c X. Тогда ef = abc и fe = cab. Поскольку ef = fe, то a = c, b = a, c = b, или a = b = c. Значит, e = и f = .

Предположим, что для всех натуральных чисел < n утверждение верно. Поскольку ef = fe, то в силу (2) e = fu = uf, где max ()< n. По индуктивному предположению существует слово h, для которого f = и u =. Получаем f = и e = f = = .Ч.т.д.

Обзор результатов по проблеме Туэ

Аксель Туэ (1863 — 1922) — норвежский математик. Хотя он был специалистом по теории чисел, но остался в истории, как родоначальник теории формальных языков, связанные с решёнными им задачами о формальных словах известных теперь, как проблемы Туэ. Задачи решены в 1912 — 1914 г.

I. Введём следующие определения.

1) Сформулируем определение — слова:

Бесконечная последовательность элементов алфавита, А называется — словом или сверхсловом. Таким образом, — слово может быть отождествлено с отображением множества целых чисел в А. Очень удобным средством задания конкретных — слов являются DOL — системы.

2) Тройка G = (A, h, w), A — алфавит, — морфизм и w — слово над А, называется DOL — системой. DOL — система G определяет S (G) слов над А:

.

Рассмотрим DOL — систему G = (A, h, w), такую, что, хZ (A), т. е. w — собственное начало слова h (w) и, кроме того, h является нестирающим (т.е. h (a)= для всех, а из А). Тогда

и вообще

для всех i 0.

Последнее равенство показывает, что для всех i является собственным началом слова. Следовательно, — слово может быть определено как «предел «последовательности, i=0,1,2, …. Точнее, представляет собой — слово, начало которого, имеющее длину, есть, i=0,1,2, … .

3) Определение. Слово или — слово называется бесквадратным (бескубным), если оно не содержит подслова вида хх (соответственно х), где х — непустое слово.

Слово или — слово называется сильно бескубным, если если оно не содержит слов вида хха, где х — непустое слово, а а — первая буква слова х.

4) Может случиться, что слово w содержит два «перекрывающихся» вхождения х, т. е. подслово xy = zx, где. Если это не имеет место, то будем называть w словом без перекрытий.

II. Сформулируем основные теоремы.

Рассмотрим следующую DOL — систему G = ({a, b}, h, a), где h определяется следующим образом: h (a) =ab, h (b) = ba. Тогда последовательность S (G) начинается словами:

a, ab, abba, abba baab, abba baab baab abba, … .

Теперь есть — слово, порожденное DOL — системой G.

— слово является сильно бескубным.

Сформулируем следующее:

Существует бесквадратное — слово над алфавитом из четырех символов и cуществует бесквадратное — слово над алфавитом из трёх символов .

= где для всех j1.

Введём новые обозначения для элементов А1, положив

[aa] = 1, [ab] = 2, [ba] = 3, [bb] = 4.

Теперь начало имеет вид

2 432 312 431 232 432 302 504 059 863 040…

Рассмотрим алфавит А2 = {1, 2, 3}. Определим — слово кА результат замены в всех вхождений символа 4 символом 1.

Теперь подведём итог полному решению проблемы Туэ в следующих теоремах:

1) «Если, А состоит не менее чем из трёх символов, то над, А существует бесквадратное — слово «;

2) «Если, А имеем не менее двух символов, то, А существует сильно бескубное, а значит и бескубное — слово».

III.Сейчас рассмотрим некоторые методы доказательства.

В формулировках основных теорем показано, как строятся — слова .

Теорема 3.1.

Слово и — слово свободно от перекрытий тогда и только тогда, когда оно является сильно бескубным.

Доказательство. Пусть w не свободно от перекрытий. Тогда w найдется подслово xy = zx, такое, что имеет место. Пусть, а — первая буква слова z. По нашему предположению, x = zx, где первой буквой слова x также будет а. Следовательно, zza — подслово w и w не является сильно бескубеым.

Наоборот, предположим, что w не является сильно бескубным. Тогда в w найдётся слово z za, где, а — первая буква z. Пологая z=аz мы видим, что х = а zа, y = zа, z = а z. Тогда xy = zx — подслово w, и, кроме того, выполняется. Отсюда следует, что w не свободно от перекрытий. Ч.т.д.

Теорема 3.2.

Ни одно слово, имеющее длину более 3, над алфавитом, А из двух букв не является бесквадратным. Следовательно, над алфавиотм, А не существует бесквадратных — слов.

Доказательство. Пусть, А состоит из букв a и b. Существуют только 2 бесквадратных слова

аbа и bаb, (*)

так как все другие слова указанной длины:

содержит в качестве подслова либо, либо. С другой стороны, каким бы способом ни была приписана буква к любому слову из (*), результирующее слово в каждом случае будет содержать в качестве подслова одно из слов, , и, следовательно, не будет бесквадратным.Ч.т.д.

Теоремя 3.3.

Ни, ни не входят в качестве подслова в. Ни ababa, ни babab не входят в качестве подслова в. Следовательно, любое подслово х — слова, такое, что, содержит в качестве подслова либо, либо .

Доказательство. Докажем первое утверждение. Если слово или входит в качестве подслова в, то оно входит в качестве подслова в некоторое w. Но это не возможно, так как w = h (w) и, следовательно, w получено приписыванием слов ab и ba в некотором порядке.

Докажем второе утверждение. Предположим, что ababa входит в качестве подслова в — слова, начиная с j-й его буквы. Тогда используя = …, запишем

= ababa. (**)

Выберем настолько большое j что. Тогда вхождения (**) целиком лежит в w. Ещё раз используя соотношение w = h (w), заключаем, что в w в качестве подслова входит либо, либо в зависимости от того, является ли j в (**) нечетным или четным. Но это не возможно в силу доказанного выше первого утверждения. Аналогично и для babab не входит в .

Наконец, последнее утверждение является следствием второго, так как, за исключением слов ababa и babab, любое слово длины 5 над {a, b} содержит в качестве подслова либо, либо. Ч.т.д.

Теорема 3.4.

Предположим, что или входит в качестве подслова в, начиная с j-й; тогда j четно.

Доказательство. Используя обозначения предыдущей теоремы, предположим, что есть или. Вновь выбираем такое i, что, и применяем соотношение w = h (w). В силу этого соотношения, если j нечетно, то есть либо h (a), либо h (b). Так как ни h (a), ни h (b) не есть или .Ч.т.д.

1. Курош А. Т. Лекции по общей алгебре. — М.: Наука, 1973.

2. Лаллеман Ж. Полугруппы и комбинаторные приложения. — М.: Мир, 1985.

3. Саломаа А. Жемчужины теории формальных языков. — М.: Мир, 1986.

4. Скорняков Л. А. Элементы алгебры. — М.: Наука, 1986.