Свободные полугруппы
Содержание
Введение-------------------------------------------------------------------
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+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; 2) I< 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)<n, мы вступаем в противоречие
с выбором числа n. Ч.т.д.
2.2.
Свободные
коммутативные полугруппы
Свободные
коммутативные полугруппы определяются точно также, как свободные полугруппы, но
только в классе коммутативных полугрупп.
Предложение
2.1.
Если - такие элементы
полугруппы, что для
любых i и j, то
, где - произвольная подстановка
на множестве {1, 2, …,n}.
Доказательство. При n = 2 утверждение теоремы справедливо
по условию. Допустим, что теорема верна для n – 1 сомножителей. Если (n) = n, то учитывая теорему: “
Произведение нескольких элементов полугруппы не зависит от расстановки скобок”,
и индуктивное предположение, имеем
.
Если n = (k), где k<n, то
Ч.т.д.
Следствие.
Для любых элементов
коммутативной
полугруппы и любой подстановки на множестве {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 = .
(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.
Теперь начало имеет вид
2432312431232432312324312432312…
Рассмотрим
алфавит А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.