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

.

Если 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 – натуральные числа.

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

(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.

(3) Пусть 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 = .

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

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

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

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

1) Сформулируем определение - слова:

Бесконечная последовательность элементов алфавита А называется - словом или сверхсловом. Таким образом, - слово может быть отождествлено с отображением множества целых чисел в А. Очень удобным средством задания конкретных - слов являются 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)=для всех а из А). Тогда

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