Geum.ru

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

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

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

?е и [d][d + I] при I= 1,2,…, n 1. Докажем, что

[d + I] = [d + I + kn] (*)

при любых I и k. В силу определения разбиения , для этого достаточно установить, что

. (**)

При k = 0 это очевидно. Допустим, что (**) доказано при всех I и

k = 0,1,…, t 1. Тогда, вспоминая, что , получаем

Тем самым равенство (**), а значит (*), доказано. Остаётся убедится, что разбиение совпадает с разбиением (d +n). С этой целью заметим, что одноэлементные классы этих разбиений совпадают. Ввиду равенства (*), для доказательства совпадения бесконечных классов достаточно установить, что смежные классы [d + I] и [d + j] разбиения , где , различны. Но если [d + I] = = [d + j], то

[d] = [d + n] = [d + j] + [n j] = [d + I] + [n j] = [d + (n (j I))]

и, поскольку 0< n (j I)<n, мы вступаем в противоречие с выбором числа n. Ч.т.д.

 

 

  1. Свободные коммутативные полугруппы

 

Свободные коммутативные полугруппы определяются точно также, как свободные полугруппы, но только в классе коммутативных полугрупп.

Предложение 2.1.

Если - такие элементы полугруппы, что для любых i и j, то

, где - произвольная подстановка на множестве {1, 2, …,n}.

 

Доказательство. При n = 2 утверждение теоремы справедливо по условию. Допустим, что теорема верна для n 1 сомножителей. Если (n) = n, то учитывая теорему: “ Произведение нескольких элементов полугруппы не зависит от расстановки скобок”, и индуктивное предположение, имеем

.

Если n = (k), где k<n, то

Ч.т.д.

 

Следствие.

Для любых элементов коммутативной полугруппы и любой подстановки на множестве {1, 2, …,n} справедливо равенство

.

Теорема 2. 2.

Если А = {} множество свободных образующих коммутативной полугруппы S, то S = {, - неотрицательные целые числа, одновременно не равные нулю}, причём различные наборы показателей () дают различные элементы S.

Доказательство. По теореме 1.2. существует гомоморфное наложение , при котором для всех =1, 2, …,n. Значит, каждый элемент sS имеет вид . Поскольку мультипликативная полугруппа {, } изоморфны аддитивной полугруппе , то различные её элементы будут иметь различные наборы показателей. Ч.т.д.

 

 

2.3.Упражнения

 

Для полугруппы слов W(X) верны следующие утверждения.

  1. ef = gh

    e = gu и h = uf либо g = eu и f = uh, для некоторого слова u (возможно непустое).

  2. Из ef = fe

    e = fk = kf для некоторого слова u либо f=eu=ue для некоторого слова u.

  3. Если ef = fe,то следует слово h, для которого e =

    и f=, где k, m натуральные числа.

    4. Докажем эти утверждения.

    (1). Пусть , и - слова в алфавите Х. По условию ef = gh. Если , то очевидно: e = g и f = h; в этом случае u = - пустое слово. Пусть nm. Будем считать, что n>m (случай m>n симметричен рассматриваемому). Имеем

=

=

 

откуда e = gu и h = uf для слова u = .

. Пусть для определённости и e = gu и h = uf. Тогда ef=(gu)f=g(uf)=gh. Ч.т.д.

(2) Это частный случай (1) при g = e и g = f.

  1. Пусть ef = fe. При

    ясно, что e = f, то имеем e=f=h=. Далее доказательство проведём индукцией по числу n=max (). Можно считать, что n = 2 имеем и =1, то есть е=ab и f=c, где a, b, c X. Тогда ef = abc и fe = cab. Поскольку ef = fe, то a = c, b = a, c = b, или a = b = c. Значит, e = и f = .

    2. Предположим, что для всех натуральных чисел < n утверждение верно. Поскольку ef = fe, то в силу (2) e = fu = uf, где max ()< n. По индуктивному предположению существует слово h, для которого f = и u = . Получаем f = и e = f = = .Ч.т.д.

Обзор результатов по проблеме Туэ

 

Аксель Туэ (1863 1922) норвежский математик. Хотя он был специалистом по теории чисел, но остался в истории, как родоначальник теории формальных языков, связанные с решёнными им задачами о формальных словах известных теперь, как проблемы Туэ. Задачи решены в 1912 1914г.

I. Введём следующие определения.

  1. Сформулируем определение

    - слова:

    2. Бесконечная последовательность элементов алфавита А называется - словом или сверхсловом. Таким образом, - слово может быть отождествлено с отображением множества целых чисел в А. Очень удобным средством задания конкретных - слов являются DOL системы.

2) Тройка G = (A, h, w), A алфавит, - морфизм и w слово над А, называется DOL системой. DOL система G определяет S(G) слов над А:

.

Рассмотрим DOL систему G = (A, h, w), такую, что , хZ(A), т.е. w собственное начало слова h(w) и, кроме того, h является нестирающим (т.е. h(a)= для всех а из А). Тогда

и вообще

для всех i 0.

Последнее равенство показывает, что для всех i является собственным началом слова . Следовательно, - слово может быть определено как “ предел ” последовательности , i=0,1,2, … . Точнее, представляет собой - слово, начало которого, имеющее длину , есть , i=0,1,2, … .

3) Определение. Слово или - слово называется бесквадратным (бескубным), если оно не содержит подслова вида хх (соответственно х), где х непустое слово.

Слово или - слово называется сильно бескубным, если если оно не содержит слов вида хха, где х непустое слово, а а первая буква слова х.

4) Может случиться, что слово w содержит два “перекрывающихся” вхождения х, т.е. подслово xy = zx, где . Если это не имеет место, то будем называть w словом без перекрытий.

 

II. Сформулируем основные теоремы.

Рассмотрим следующую DOL систему G = ({a, b}, h, a), где h определяется следующим образом: h(a) =ab, h(b) = ba. Тогда последовательность S(G) начинается словами:

a, ab, ab