Научная литература
booksshare.net -> Добавить материал -> Математика -> Линдон Р. -> "Комбинаторная теория групп" -> 130

Комбинаторная теория групп - Линдон Р.

Линдон Р., Шупп П. Комбинаторная теория групп. Под редакцией Ремесленникова В.Н. — М.: Мир, 1980. — 447 c.
Скачать (прямая ссылка): kombinatornteor1980.djvu
Предыдущая << 1 .. 124 125 126 127 128 129 < 130 > 131 132 133 134 135 136 .. 202 >> Следующая

6. Биполярные структуры
¦ пикш-, 291
с разложением нужного типа имеет разложение такого же типа. -гем самым теорема доказана. ?
Мы завершим этот раздел, указав, что биполярные структуры могут оказаться полезными при доказательстве того, что различные группы имеют хорошее разложение в свободное произведение с объединенной подгруппой или представление в виде HNN-расши-рения. Следующая теорема принадлежит Нагао [1959]. (См. III.12.)
Теорема 6.9. Пусть Kh] — кольцо многочленов от одной переменной над полем К. Тогда
GL1(/C[je]) = <GLi(/C)#T; U = Uy,
где U — группа верхних треугольных матриц над К, a T — группа матриц вида ?'*'), где kx и k2 — ненулевые элементы из К и f{x) ZKhI
Обобщение результата Нагао можно найти у Серра [1974]. Самый легкий путь доказательства результата Нагао —прямое доказательство. В то же время оказывается, что QiL2[KhX) обладает весьма естественной биполярной структурой, которую мы и собираемся описать.
? Пусть F=U, и пусть все матрицы GLj(ZC) — U лежат в ЕЕ. Если fZK[x], то пусть б (/) —степень многочлена f. Рассмотрим
теперь произвольную матрицу M = ff ^ fi*\ , где по меньшей мере
V/21 /22/
одно вхождение имеет степень, большую нуля. Положим
M Z ЕЕ тогда и только тогда, когда б (/12Х б (^11) и б (/12) ^
M Z ЕЕ* тогда и только тогда, когда б (/12)=^ 6 {flt) и б (/12) >
M Z Е*Е тогда и только тогда, когда б (/12)> 6 (/ц) и б (/i2) ^ <б(/22),
M Z Е*Е* тогда и только тогда, когда б (/12)> б (/п) и б (f12) > >б(/22).
Короче говоря, степень элемента /\2 сравнивается со степенями элементов на главной диагонали. Аксиома об обратном является непосредственным следствием формулы для обращения 2 X 2-матриц:
¦М-1=:^! ~ff")- Для проверки аксиомы о произведении и ак-
сиом для склеиваемой части, кажется, достаточно проделать несколько умножений. Аксиома ограниченности справедлива, поскольку эти умножения показывают, что если M Z XY и N Z Y*Z, то максимум степеней элементов матрицы MN строго больше степеней элементов из M или N. О
ю*
292 Гл. IV. Свободные произведения и HNN-расширения
7. Теорема Хигмана о вложении
Алгоритмы для решения многих конкретных задач были най-дены задолго до того момента, когда появилось точное определение понятия «алгоритм». В каждом случае положительного решения алгоритмической проблемы, например проблемы равенства слов для групп с одним определяющим соотношением, алгоритм бывал фактически найден, и все соглашались с тем, что получена эффективная разрешающая процедура. В то же время понятно, что отри-цательные результаты о разрешимости можно получить только после выработки точного определения «алгоритма», поскольку доказательство несуществования требует обозрения всех возможных алгоритмов. Такое точное определение появилось в 30-х годах. После его появления стало возможным заменить интуитивные понятия «эффективной разрешимости» и «эффективной перечислимости» точными понятиями «рекурсивное™» и «рекурсивной перечислимости».
В 50-х годах П. С. Новиков [1952, 1955] и Бун [1959] независимо доказали, что существуют конечно представленные группы с неразрешимой проблемой равенства. В 1961 году Г. Хигман доказал замечательную теорему, в которой твердо устанавливается тот факт, что связь между логическим понятием рекурсивности и вопросами о конечно представленных группах не только не случайна, но весьма глубока. Напомним, что представление называется рекурсивным, если оно имеет конечное число порождающих и рекурсивно перечислимое множество определяющих соотношений.
Теорема 7.1. (Теорема Хигмана о вложении.) Конечно порожденная группа G может быть вложена в некоторую конечно представленную группу в том и только том случае, когда G рекурсивно представлена.
Наша цель в настоящем разделе — доказательство теоремь Хигмана о вложении и некоторых ее следствий.
Перед доказательством теоремы Хигмана о вложении рассмот рим некоторые ее следствия, при формулировке которых будем придерживаться интуитивного понятия «рекурсивности». Когдг мы рассмотрим точное определение понятия «рекурсивности», нами будет доказано существование рекурсивно перечислимого нерекурсивного множества S положительных целых чисел. С помощью этого факта из теоремы Хигмана о вложении без труда получается пример конечно представленной группы без алгоритма равенства. Такой пример будет дан прямо сейчас. На самом деле все факты, необходимые для построения примера конечно представленной группы с неразрешимой проблемой равенства слов, получаются уже где-то на середине доказательства теоремы о вложении. в этом
I
7. Теорема Хигмана о вложении
293
месте доказательства мы снова вернемся к неразрешимости проблемы равенства слов.
Теорема 7.2. Существует конечно представленная группа Я с неразрешимой проблемой равенства слов.
P Пусть S — рекурсивно перечислимое нерекурсивное множество натуральных чисел. Положим
G=<a, b, с, а; а~'Ьа'= с~1ас1', i?S>.
Понятно, что проблема равенства в G неразрешима, так как
a-"ba" = c~ndc"
выполняется в G в том и только том случае, когда п ? S. Поскольку множество определяющих соотношений группы G рекурсивно перечислимо, она может быть вложена в конечно представленную группу Н. Из того, что G — конечно порожденная группа с неразрешимой проблемой равенства слов, следует, что проблема равенства слов должна быть неразрешимой и в Я. ?
Предыдущая << 1 .. 124 125 126 127 128 129 < 130 > 131 132 133 134 135 136 .. 202 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed