Дискретно-непрерывная математика (стр. 93 )

следующим образом:

где

и

где операция * есть операция, взятая из замечания 2.13;

Очевидно, что βi, — комбинаторный автомат, т. е. βiS — комбина­торная полугруппа.

Определим теперь автомат Mi. Пусть отображение i : S → {1, ..., п} задается соотношениемтогда и только тогда, когдаи соотношением i(s)= n тогда и только тогда, когда

s К, где К — идеал. Тогда положим

и по определению

Это эквивалентно равенству

(Отметим, что βi не участвует в определении Mi). Автомат Mi является комбина­торным.

2.17. Лемма.

Пусть

Тогда автомат Mi обладает следующими свойствами (положим для удобства обозначений К = Jn):

а)тогда и только тогда, когда б) если при i = 2, ..., п, то

для некоторого

в) если для i = 2, ...,n, тo

и

Если, в частности, для i = 1, ..., п, то Fi (αr) удовлет-

воряет случаю 1 (см. уравнение 2). Если, то Fi (αr) удов-

летворяет случаю 2. Если то Fi (αr) удовлет-

воряет случаю 3.

Доказательство.

а) Этот пункт вытекает из определения автомата Mi.

Сперва исследуем . Пусть ji — такое наиболь-

шее целое число, что в последовательности (Mi (α1),

— последний членв последовательности (нет члена не совпадающий с I. Условимся считать ji = 0, если такой автомат не существует. Тогда, рассмотрев определение автомата Mi i = 2, ..., п, приходим к следующей формуле:

Заметим, что пункты б) и в) легко доказываются, когда αr есть по­следовательность длины 1. Поэтому предположим, что r ≥ 2. Будем вести доказательство по индукции относительно i, где i — индекс для Mi, доказав сперва пункты б) и в) для M2 (αr).

б) Если поскольку не может быть равен I. Следовательно, sr J1.

в) Если

Положим

Поскольку j1 = п— 1, имеем два случая:

Случай 1. sr Jk, поэтому так как

поэтому

Случай 2. sr Jk′, поэтому так как

поэтому

Следовательно, утверждения пунктов б) и в) справедливы для

Предположим, что утверждения пунктов б) и в) верны для целых чисел, меньших i, и рассмотрим , Mi (αr).

б) Если или I. По предположе­нию индукции из равенства Mi-1 (αr) = i—1 следует, что

и из равенства вытекает, что

для некоторого k < i— 1. В обоих случаях утверждение для доказано.

в) Если Пусть

Теперь имеются три возможности:

Случай 1. Если ji-1 = 0, то для каждого По предположению индукции из этого следует, что удовлетворяет случаю 1 для каждого откуда в свою очередь следует, что Теперь по предположению индукции из равенства вытекает, что

Но тогда

и пункт в) в этом случае выполняется.

Случай 2. Если то

oткуда следует равенство Тогда мы находимся

в ситуации случая 1. Поскольку

поэтому снова пункт в) выполняется.

Случай 3. Если По предпо -

ложению индукциипоэтому

Так как мы имеем

и по индукции Тогда

Теперь продолжим доказательство теоремы. Если Fi (αr) будет та­ким, как в случае 1, мы знаем, что изменений не произошло, т. е. Если будет таким, как в случае 2, то мы