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

Введение------------------------------------------------------------------- 3 Понятие свободной полугруппы------------------------- 4 Слова------------------------------------------------------------ 4 Понятие свободной полугруппы-------------------------- 5 Применение--------------------------------------------------- 9 Циклические (моногенные) полугруппы--------------- 9 Сводные

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

Дипломная работа

Математика и статистика

Другие дипломы по предмету

Математика и статистика

Сдать работу со 100% гаранией

Содержание

Введение------------------------------------------------------------------- 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 где < и х принадлежит Х. Тогда и уже определены. Положим

 

(**)

 

Покажем, что отображение : WЕ является гомоморфизмом, то есть что для любых .

Проведем индукцию по длине второго сомножителя . Если =1, то доказываемое следует из равенства (**). Если >1, то = х, где < и х принадлежит Х. Поэтому, учитывая (**) и индуктивное предположение получаем:

Кроме того, если х принадлежит Х, то в силу равенства (*). Итак, условия (1) и (2) выполнены. Ч.т.д.

Теорема 1.2. (свойство универсальности свободной полугруппы).

Для всякой полугруппы Е найдутся свободная полугруппа S и гомоморфное наложение : SЕ.

 

Доказательство. Пусть S свободная полугруппа со свободно порождающим множеством Е. В силу свойства (2) из определения свободной полугруппы, тождественное отображение множества Е на себя продолжается до гомоморфизма : SЕ, который в данном случае оказался наложением. Ч.т.д.

 

Теорема 1.3. (о единственности свободной полугруппы).

Если S=S(x) свободная полугруппа со свободно порождающим множеством Х, то существует изоморфизм полугруппы S на полугруппу W=W(x) слов в алфавите Х, причем , для всех х принадлежащих Х.

Доказательство. По Т1. и свойству (2) из определения свободной полугруппы, тождественное отображение множества Х на себя продолжается до гомоморфизмов : SW и: WS, причем , для любых х принадлежащих Х. Таким образом Х и Х.

По теореме “Если : АВ гомоморфизм полугруппы, то - подполугруппа В ”и свойству (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. Применения

 

  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 2 3 > >>