Свободные полугруппы
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
Содержание
Введение------------------------------------------------------------------- 3
- Понятие свободной полугруппы------------------------- 4
- Слова------------------------------------------------------------ 4
- Понятие свободной полугруппы-------------------------- 5
- Применение--------------------------------------------------- 9
- Циклические (моногенные) полугруппы--------------- 9
- Сводные коммутативные полугруппы------------------ 12
- Упражнения-------------------------------------------------- 13
- Обзор результатов по проблеме Туэ-------------------- 15
Литература-----------------------------------------------------------
Введение
Дипломная работа посвящена теории свободных полугрупп. Свободные алгебраические объекты играют важную роль в общей алгебре, поскольку любая алгебраическая структура является гомоморфным образом свободной алгебраической структуры того же типа.
В теории полугрупп свободные объекты описываются конструктивно, именно как полугруппы слов над некоторым алфавитом. Поэтому большое место в работе уделено рассмотрению свойств полугрупп слов. Эти свойства носят, как правило, комбинаторный характер.
Кроме того, в работе изучаются и абстрактные свойства свободных полугрупп и некоторых связанных с ним полугрупп.
В первом параграфе вводятся основные понятия и доказательства теорем о существовании и единственности свободных полугрупп с множеством образующих данной мощности.
Второй параграф посвящён двум применениям свободных полугрупп:
- описание циклических полугрупп;
- свободной коммутативной полугруппе.
Там же доказываются некоторые комбинаторные свойства слов над произвольным алфавитом.
В третьем параграфе даётся обзор проблематики Туэ о существовании бесквадратных и бескубных слов произвольной длины над различными алфавитами.
В дипломной работе используются книги [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(Х) называется свободной полугруппой со свободным порождающим множеством Х, если:
- S порождается множеством Х;
- для любого отображения
, где Е произвольная полугруппа, существует гомоморфизм такой, что
для любых х Х.
Теорема 1.1. (существование свободной полугруппы).
W=W(x) свободная полугруппа со свободно порождающим множеством Х.
Доказательство. Оба свойства (1) и (2) свободной полугруппы проверим индукцией по длине слов W.
(1) Пусть Т подполугруппа полугруппы W, порожденная множеством Х. Тогда любое слово w принадлежащее W, лежит в Т. Действительно, если =1, то w принадлежит Х и подмножество Т. Если >1, то w=wx, где < и х принадлежит Х. следовательно, w, x принадлежит Т по предположению индукции. Так как Т - подполугруппа, а w произведение двух элементов w и х , то w принадлежит Т. Поэтому W подмножество Т. Обратное включение очевидно. Итак, T=W.
(2). Пусть - произвольное отображение множества Х в некоторую полугруппу Е с операцией . Определим элемент полугруппы Е индукцией по . Если =1,w принадлежит Х и мы положим
(*)
Если >1, то w=wx где < и х принадлежит Х. Тогда и уже определены. Положим
(**)
Покажем, что отоб?/p>