Диплом

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

Работа добавлена на сайт bukvasha.net: 2013-09-30

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Выберите тип работы:

Скидка 25% при заказе до 23.11.2024


Содержание
 
    Введение------------------------------------------------------------------- 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) из определения свободной полугруппы, тождественное отображение множества Х на себя продолжается до гомоморфизмов : S W и : W S, причем , для любых х принадлежащих Х. Таким образом Х  и Х .
По теореме “Если : А В – гомоморфизм полугруппы, то   - подполугруппа  В  ” и свойству (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; 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].
Факторполугруппу полугруппы Р по рассмотренному разбиению называют циклом с хвостом.    
 SHAPE  \* MERGEFORMAT
При 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. Значит, каждый элемент s S имеет вид . Поскольку мультипликативная полугруппа { , } изоморфны аддитивной полугруппе , то различные её элементы будут иметь различные наборы показателей. Ч.т.д.
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 =  - пустое слово. Пусть n m. Будем считать, что 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уществует бесквадратное  - слово  над алфавитом из трёх символов  .
   
                        =  где для всех j 1.
Введём новые обозначения для элементов А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  z a, где а – первая буква 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.

1. Сочинение на тему Литературный герой ВАМПУКА
2. Контрольная работа на тему Разработка тура выходного дня по Луганской области
3. Реферат Контроль сварки
4. Реферат на тему Militant Monks Essay Research Paper Militant Monks
5. Реферат Топография террора
6. Реферат на тему King Arthur Essay Research Paper The legends
7. Реферат Особенности движения амфибий
8. Курсовая на тему Белое движение на Юге России
9. Реферат Анализ многоугольника конкурентоспособности
10. Реферат на тему Possessing The Secret Of Joy Four Men