Алгоритмические проблемы теории групп и полугрупп. 1994 г.

я выполняется утверждение 4 теоремы 2 (с заменой X на У , а У на X ) . Если X, ? / . т о Х в < , а ото противоречит предположению, сделанному в самом начале доказательства тео­ рем. В дальнейшем можно считать, что X, , У, - непустые слова, для завершения доказательства теоремы 2 мы должны рас - смотреть 4 , возможности, которые^по предположению индукции мо­ гут иметь место для слов X, , У, . Но сказы вается, что утвер­ ждения 3 й 4 теоремы 2 на самом деле не могут выполняться для этих слов. ПРЕДЛОЖЕНИЕ 9 . 1) Левый^остаток хотя бы одного из слов Х4 , У пу ст; 2 ) для слов X, , У, не могут выполняться ут­ верждения 3 ,4 теоремы 2 ; 3 ) в формулировке теоремы 2 дал слов х / , % слова Р , (3 , Я , Т , и / пусты. ДОКАЗАТЕЛЬСТВО. Надо доказать только первый пункт пред­ ложения (второй следует из первого и формулировки теоремы, а третий из замечания 1 ) . Исследуем сначала подробнее, как у ст ­ роены слова X , У .И з ( 1 0 ,1 1 ,3 6 ) получаем Хг е В И, , где _ собственное начало Н , Н в И, Нг . Тогда (см . (9 ,1 0 ,3 9 ,3 0 )) . * £ АН, А с , . . . Ас$_< А в ь В;г , ••■4/, * ) ( 3 9 ^ У в &Н, . . . А^.,МА = 6 Н ё с ^ - - . В с , УХ л А . (4 0 ) Для доказательства предложения 9 понадобится несколько вспо­ могательных утверждений. ПРЕДЛОЖИ! 1 0 . Н , = X . ДОКАЗАТЕЛЬСТВО. Предположим, что Н , $ / . Возможны два случая: в равенствах (3 9 ,4 0 ) р > X или р ~ 1 • 1 . Р > У . Пусть Щ, I * /4^| ,тогда из (3 9 ) иглеем И ,в В ^ Р при некотором Г . Слово 4>-* является непустым началом опре­ деляющего слова АМ й и концом определяющего слова А ^ 4/ -/■ По лемме 1 /4^., * РНг АВ. Но т о гд а , подставив выражение для Л/, , п ( 4 0 ) , получаем противоречие с неприводимостью слова У (см . ( 3 1 ) ) . Пусть теперь /АУ,Н /в^_Д откуда ¿ к < непустое начало слова Л*", . Й 1 'г_( .4 . Но лемме 2 Р в А /, . Значит, су ­ ществуют определяющие олова Р /(с, 'и Р*ч Р ■ По лемме 1 А*\ В с , - А^ ., Н, и то гд а А с,В г,= при неко­ тором 0 . Итак, /V/ - непустое двустороннее слоео . П о след­ ствию 1 слове Р ,V - определяющее, причем 0 - начало слова А ,, Вс, . Однако .это противоречит тому, что сокращения прово- 121