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

Содержание

Введение------------------------------------------------------------------- 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.

 Скачать реферат