Помогите, пожалуйста! Показать индукцией по длине слова $%U (a, b, c, …)$%, что $%UU^{-1}$% выводимо из множества слов, тривиально равных $%1$%, и поэтому соотношение $%U = U$% выводимо из любого множества соотношений. [Указание. Если $%U = Va^ε$%, где $%ε = 1$% или $%-1$%, то $%UU^{-1} = Va^εa^{-ε}V^{-1}$%] Заранее благодарен!

задан 23 Сен '13 22:23

изменен 23 Сен '13 22:27

10|600 символов нужно символов осталось
0

Прочитайте внимательно определение выводимости на стр. 15 книги, из которой взято это упраженение. Обратите внимание на то, что в процессе вывода разрешается как вычёркивать, так и вписывать (в любое место) слова вида $%aa^{-1}$% или $%a^{-1}a$%, где $%a$% -- один из образующих. Тогда понятно, что слово вида $%UU^{-1}$% приводится к $%1$% при помощи серии таких вычёркиваний. В частности, если воспользоваться указанием, то на первом шаге слово $%UU^{-1}$%, оно же $%Va^{\varepsilon}a^{-\varepsilon}V^{-1}$%, превратится в $%VV^{-1}$%, где слово $%V$% стало на одну букву короче по сравнению с $%U$%. После $%n$% шагов получится слово $%1$%, где $%n=L(U)$% есть длина слова $%U$%, то есть количество букв слова $%U$%.

ссылка

отвечен 23 Сен '13 23:00

10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×631

задан
23 Сен '13 22:23

показан
349 раз

обновлен
23 Сен '13 23:00

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru