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

Дипломная работа - Математика и статистика

Другие дипломы по предмету Математика и статистика

Содержание

Введение------------------------------------------------------------------- 3

  1. Понятие свободной полугруппы------------------------- 4
  2. Слова------------------------------------------------------------ 4
  3. Понятие свободной полугруппы-------------------------- 5
  4. Применение--------------------------------------------------- 9
  5. Циклические (моногенные) полугруппы--------------- 9
  6. Сводные коммутативные полугруппы------------------ 12
  7. Упражнения-------------------------------------------------- 13
  8. Обзор результатов по проблеме Туэ-------------------- 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. для любого отображения

    , где Е произвольная полугруппа, существует гомоморфизм такой, что

  3. для любых х Х.

 

Теорема 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>