Свободные полугруппы
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
?ажение : 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. Применения
- Циклические (моногенные) полугруппы
Полугруппа В называется циклической (моногенной), если в ней содержится такой элемент а, что всякий элемент х из В может быть записан в форме для некоторого 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].
Факторполугруппу полугруппы Р по рассмотренному разбиению называют циклом с хвостом.
При d = 1 хвост оказывается пустым. Такую полугруппу называют циклом.
Теорема.
Всякая циклическая полугруппа изоморфна или аддитивной полугруппе Р положительных чисел, или некоторому циклу с хвостом (возможно пустым).
Доказательство. Пусть В циклическая полугруппа с образующим а. Рассмотрим отображение полугруппы Р в полугруппу В, определяемое условием .
Ввиду циклической полугруппы В, оказывается наложением. В силу теоремы: “ для всех m, n > 0.”
,
т.е. является гомоморфизмом. Из следующей теоремы:
Если - гомоморфное наложение полугрупп и - естественный гомоморфизм, то существует изоморфизм такой, что , вытекает, что В изоморфна факторполугруппе Р/, где = . Если все классы разбиения одноэлементны, то В изоморфна Р. В противном случае обозначим через d наименьшее целое число, входящее в неодноэлементный класс, а число n выберем так, чтобы d + n было наименьшим числом, отличным от d, но входящим в один класс с d. Тогда имеем классы [1], [2],…, [d 1], [d], [d + 1],…, [d + n 1], среди которых первые d 1 одноэлементн?/p>