На бирже курсовых и дипломных проектов можно найти образцы готовых работ или получить помощь в написании уникальных курсовых работ, дипломов, лабораторных работ, контрольных работ, диссертаций, рефератов. Так же вы мажете самостоятельно повысить уникальность своей работы для прохождения проверки на плагиат всего за несколько минут.

ЛИЧНЫЙ КАБИНЕТ 

 

Здравствуйте гость!

 

Логин:

Пароль:

 

Запомнить

 

 

Забыли пароль? Регистрация

Повышение уникальности

Предлагаем нашим посетителям воспользоваться бесплатным программным обеспечением «StudentHelp», которое позволит вам всего за несколько минут, выполнить повышение уникальности любого файла в формате MS Word. После такого повышения уникальности, ваша работа легко пройдете проверку в системах антиплагиат вуз, antiplagiat.ru, etxt.ru или advego.ru. Программа «StudentHelp» работает по уникальной технологии и при повышении уникальности не вставляет в текст скрытых символов, и даже если препод скопирует текст в блокнот – не увидит ни каких отличий от текста в Word файле.

Результат поиска


Наименование:


Диплом Математическое понятие свободной полугруппы. Полугруппы слов над некоторым алфавитом. Комбинаторные свойства слов над произвольным алфавитом. Циклические (моногенные) полугруппы. Сводные коммутативные полугруппы. Обзор результатов по проблеме Туэ.

Информация:

Тип работы: Диплом. Предмет: Математика. Добавлен: 14.06.2007. Сдан: 2007. Уникальность по antiplagiat.ru: --.

Описание (план):


2
Содержание

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

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) I, j <d; 2) I< d, j d; 3) I d, j< d; 4) I, j d. В первом случае имеем: x=u=I и y=v=j, откуда [x+y]=[u+v], поскольку x+y=u+v. Во втором случае x=u=I, y=j+kn и v=j+Ln для подходящих k,L. Используя деление с остатком запишем
I + j - d=sn + r ,
где 0 r< n. Тогда
x + y = I + j + kn = d + (I + j - d) + kn = d + r + (s + k) n
и u + v = I + j + Ln = d + (I + j - d ) + Ln = d + r + (s + L) n,
откуда [x + y] = [d + r] = [u + v]. Третий случай рассматривается аналогично. В четвертом случае, используя определение смежных классов, можно записать
x =I + kn = d + (I - d) + kn,
u = I + Ln = d + (I - d) + Ln,
y = j + pn = d + (j - d) + pn,
v = j + qn = d + (j - d) + qn.
Тогда
x + y = d + (d + (I - d) + (j - d)) + (k + p) n
и
u + v = d + (d +(I - d) + (j - d)) + (L + q) n.
Разделив с остатком, получим
d + (I - d) + (j - d) = sn + r,
где 0 r< n. Отсюда
x + y = d + r + (k + p + s) n
и
u + v = d + r + (L + q + s) n,
т.е. [x + y] = [d + r] = [u + v].
Факторполугруппу полугруппы Р по рассмотренному разбиению называют циклом с хвостом.
2
При d = 1 хвост оказывается пустым. Такую полугруппу называют циклом.
Теорема.
Всякая циклическая полугруппа изоморфна или аддитивной полугруппе Р положительных чисел, или некоторому циклу с хвостом (возможно пустым).
Доказательство. Пусть В - циклическая полугруппа с образующим а. Рассмотрим отображение полугруппы Р в полугруп и т.д.................


Перейти к полному тексту работы



Смотреть похожие работы


* Примечание. Уникальность работы указана на дату публикации, текущее значение может отличаться от указанного.