Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Особенности труда и отдыха в условиях низких температур: К работам при низких температурах на открытом воздухе и в не отапливаемых помещениях допускаются лица не моложе 18 лет, прошедшие...
Теоретическая значимость работы: Описание теоретической значимости (ценности) результатов исследования должно присутствовать во введении...
Выпускная квалификационная работа: Основная часть ВКР, как правило, состоит из двух-трех глав, каждая из которых, в свою очередь...
Интересное:
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Дисциплины:
2020-10-20 | 146 |
5.00
из
|
Заказать работу |
|
|
Содержание
Введение------------------------------------------------------------------- 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] из приведённого списка библиографии.
Понятие свободной подгруппы
Слова
Алфавит А – это непустое конечное множество. Буквы (символы)- элементы алфавита А. Слово над алфавитом А – это конечная цепочка, состоящая из нуля или более букв из А, причем одна и та же буква может входить несколько раз. Цепочка, состоящая из нулевого количества букв, называется пустым словом и обозначается . Таким образом , 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) для всех слов х,у.
Теорема.
Всякая циклическая полугруппа изоморфна или аддитивной полугруппе Р положительных чисел, или некоторому циклу с хвостом (возможно пустым).
Доказательство. Пусть В – циклическая полугруппа с образующим а. Рассмотрим отображение полугруппы Р в полугруппу В, определяемое условием .
Ввиду циклической полугруппы В, оказывается наложением. В силу теоремы: “ для всех 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.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 имеет вид . Поскольку мультипликативная полугруппа { , } изоморфны аддитивной полугруппе , то различные её элементы будут иметь различные наборы показателей. Ч.т.д.
Упражнения
Для полугруппы слов 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 = = .Ч.т.д.
Теорема 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.
Содержание
Введение------------------------------------------------------------------- 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] из приведённого списка библиографии.
Понятие свободной подгруппы
Слова
Алфавит А – это непустое конечное множество. Буквы (символы)- элементы алфавита А. Слово над алфавитом А – это конечная цепочка, состоящая из нуля или более букв из А, причем одна и та же буква может входить несколько раз. Цепочка, состоящая из нулевого количества букв, называется пустым словом и обозначается . Таким образом , 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) для всех слов х,у.
Понятие свободной полугруппы
Пусть 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. Применения
|
|
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Биохимия спиртового брожения: Основу технологии получения пива составляет спиртовое брожение, - при котором сахар превращается...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!