Ученые записки математических кафедр вып. 1970 г.

Доказательство. Допустим, что кроме С \л/ * ■ содержит дополнительное определяющее слово Ст. Если Ст содеряится в каком-нибудь С / , то очевидно, что содержится я в С ; в поэтому является интервалом,1 что противоречит условию ¿) - По той же причине^-СТ/г не может содержаться в С Аналогично С и<< не может содержаться в С / , . Если С , * содержится в О, г, но не является левой частью Ст то С" будет интервалом. Но это противоречит условию 1 ),; т .к .' из * условия леммы ясноу что С ;" V также является интервалом. Еслж же C¿J <$ = С /;, и Л И — г ТО« условия 2) следует; что Сс. Ф Ст .Следовательно'; ь. является интервалом; что противоречит условию I) т.к, О также является интервалом. Лемма I доказана; Лемма 2.' Пусть Ц - элемент полугруппы _/) и Vе (У тогда а только тогда‘; когда I /=Ы Тогда И л конечное мно­ жество и существует алгоритм-; позволяющий найти для любого. Ц яз СД все элементы из Ы ; Доказательство.Примени« индукциюпо длине элемента Ц * I.Пусть С (и.) = / . По условию3) Ц — { Ц} ¿.Предположим; что лемма справедлива для всех элементов полугруппы А * длина которых меньяе некоторого натурального П Докажем справедливость леммыдля элемента (У*г длина которого равна И ( П > 1 ) ' г £ ( и ) * ’П. где Тогда ¿./ можно записать так: и —йЦ к 1 ( Ц ) = П - I . Множество всех элементов; равных элемеату ( / в полугруппе (Л. конечно и его можно элективно пайти.