Update site in the process

   Главная  | О журнале  | Авторы  | Новости  | Вопросы / Ответы


К содержанию номера журнала: Вестник КАСУ №6 - 2011

Автор: Зубенко Олеся Владимировна

Современное развитие математики и электронно-вычислительной техники приводит к тому, что понятие алгоритма становится одним из важнейших понятий современной математики. Развитие и совершенствование вычислительной техники ставит перед математической теорией многочисленные задачи, появляются новые направления. Одним из таких направлений является теория конструктивных моделей. Бурное развитие теории моделей, одного из разделов математической логики, приходится на последние два десятилетия. Становление теории конструктивных моделей как интересного самостоятельного направления современной математической логики обязано появлению статьи А.И. Мальцева «Конструктивные алгебры». А.И. Мальцеву принадлежит и ряд важнейших результатов, как по разрешимости элементарных теорий, так и по конструктивным моделям. Наиболее свежей проблематикой обладает теория конструктивных моделей – теория, которая возникла на стыке теории моделей и теории нумераций. За этот период теория обогатилась новыми идеями, методами и конструкциями. Конструктивные абелевы группы изучались в работах А.И. Мальцева, Ю.Л. Ершова, С.С. Гончарова, В.П. Добрица, А.Т. Нуртазина, Н.Г. Хисамиева Дж. Найт и других авторов. Конструктивные нильпотентные группы исследованы мало. Ю.Л. Ершов [1] доказал, что конструктивизация локально нильпотентной группы без кручения продолжается естественным образом до ее пополнения. В работе С.С. Гончарова, А.В. Молокова, Н.С. Романовского [2] построена нильпотентная группа, алгоритмическая размерность которой конечна. И.В. Латкин [3] построил пример позитивно нумерованной нильпотентной группы без кручения, которая неконструктивизируема.

Теория групп относится к одному из важнейших разделов современной алгебры. Она имеет богатую и содержательную историю. К настоящему времени эта часть математики превратилась в широкую и богатую содержанием науку, имеющую многочисленные применения, как в самой математике, так и за ее пределами – в топологии, теории функций, кристаллографии, квантовой механике, теории кодирования, криптографии и других областях математики и естествознания. Одним из важнейших классов групп являются нильпотентные группы, промежуточные между абелевыми и разрешимыми группами.

Работа посвящена исследованию вопросов вычислимости центра конструктивной нильпотентной группы.

Пусть G – группа. Отображение множества всех натуральных чисел на G называется нумерацией группы G. Если существует алгоритм, который по любым числам n, m и s определяет справедливость равенства , то пара называется конструктивной группой.

Группа G называется конструктивизируемой, если существует такая ее нумерация ν, что – конструктивная группа. Подгруппа называется вычислимо перечислимой (вычислимой) в , если множество вычислимо перечислимо (вычислимо). Максимальная система линейно независимых элементов абелевой группы без кручения А называется базисом группы А, а число элементов базиса – размерностью группы А.

Пусть М – подмножество группы G. Множество называется централизатором M в группе G. Централизатор всей группы называется ее центром и обозначается через Z.

Пусть в группе G дан инвариантный ряд

(1)

Этот ряд называется центральным рядом, если при фактор-группа лежит в центре фактор-группы ; иными словами, если взаимный коммутант лежит в ,

(2)

Заметим, что инвариантности ряда (1)можно было бы и не требовать, так как из (2) вытекает для всех i включение равносильное тому, что нормально в G.

Группа G, обладающая хотя бы одним центральным рядом, называется нильпотентной [5].

Всякая подгруппа и вcякая фактор-группа нильпотентной группы сами нильпотентны.

Действительно, пусть в нильпотентной группе G с центральным рядом (1) дана подгруппа Н. Если

(3)

то ввиду (2) при будет

Подгруппы (3) составят, следовательно, после удаления повторений центральный ряд для подгруппы Н.

Пусть, с другой стороны, дано гомоморфное отображение нильпотентной группы G с центральным рядом (1) на группу . Обозначим через образ подгруппы при этом гомоморфизме, . Пусть и – элементы соответственно из и , а и g – некоторые их прообразы при гомоморфизме в и G,

Так как, по (2), то

Подгруппы , составят, следовательно, после удаления повторений центральный ряд группы .

Прямое произведение конечного числа нильпотентных групп нильпотентно.

В самом деле, пусть

Причем, все группы нильпотентны. Выбираем в этих группах по одному центральному ряду, причем считаем, что длины этих рядов совпадают, допуская, если нужно, ряды с повторениями. Пусть

будет центральный ряд группы . Тогда подгруппы

будут составлять центральный ряд группы G.

Заметим, что расширение нильпотентной группы при помощи нильпотентной не обязано быть нильпотентным, так как иначе все разрешимые группы оказались бы нильпотентными.

Цепь подгрупп

где

называется нижней центральной цепью.

Построим эту цепь в нильпотентной группе G с центральным рядом (1). По (2)

Пусть уже доказано, что Тогда

Отсюда следует, что

т.е. .

Этим доказано, что в нильпотентной группе нижняя центральная цепь в конечное число шагов доходит до единицы, т.е. превращается в нижний центральный ряд, причем длина этого ряда больше длины любого центрального ряда группы. Нижний центральный ряд удовлетворяет данному выше определению центрального ряда и поэтому существование конечного нижнего центрального ряда можно принять в качестве одного из определений нильпотентной группы.

Во всякой группе G можно построить также верхнюю центральную цепь: это будет такая последовательность подгрупп

что есть центр группы – центр группы , вообще – центр группы . Эту цепь, состоящую из характеристических подгрупп, в общем случае можно продолжать трансфинитно, причем она стабилизируется, не обязательно доходя до самой группы G.

Построим верхнюю центральную цепь в нильпотентной группе G с центральным рядом (1). Так как, по (2), то . Пусть уже доказано, что . Тогда, по (2),

Это показывает, что при естественном гомоморфном отображении группы G на фактор-группу подгруппа будет отображаться в центр этой фактор-группы, а поэтому . Отсюда следует, что

т.е. .

Этим доказано, что в нильпотентной группе верхняя центральная цепь в конечное число шагов доходит до самой группы, т.е. превращается в верхний центральный ряд, причем длина этого ряда не превосходит длину любого центрального ряда группы. Существование верхнего центрального ряда также может быть принято в качестве определения нильпотентной группы.

В G определим возрастающие и убывающие ряды

следующим образом: и если подгруппы , и уже определены, то

и , здесь [A,B] – взаимный коммутант подгрупп А и В. Полученные ряды подгрупп называются соответственно верхним и нижним центральным рядом, а и – n - м гиперцентром и n – м централом группы G.

Группа G называется нильпотентной ступени n, если справедливо равенство (или, что равносильно, ).

Теория конструктивных моделей - один из разделов математики, возникший на границе моделей теории, алгебры и теории рекурсивных функций и связанный с изучением вопросов эффективности в моделях и алгебрах.

Статья А.И. Мальцева «Конструктивные алгебры» явилась первой обзорной работой по конструктивным моделям, в которой были выработаны и систематизированы основные понятия и намечены дальнейшие пути развития этой теории. Большую роль в становлении и развитии этого раздела математики сыграли работы Ю.Л. Ершова и его учеников, в которых был решен ряд основных проблем, выработаны новые понятия и определены новые направления в исследовании конструктивных моделей.

Все общие рассмотрения будут вестись обычно в некоторой фиксированной сигнатуре , содержащей только предикатные символы и такой, что функция общерекурсивна [4]. Рассмотрим следующие сигнатуры:

которые получаются присоединением к сигнатуре символов для констант. Будем предполагать, что и предикат на любой модели определен как равенство (вместо будем писать ).

Пусть – совокупность всех формул языка узкого исчисления предикатов с равенством сигнатуры . Имеют место следующие соотношения:

Предположим еще, что задана какая-нибудь фиксированная геделева нумерация g множества . Под геделевой нумерацией множества понимаем любую нумерацию g этого множества такую, что по g–номеру можно эффективно построить саму формулу, а по формуле из можно эффективно найти ее g–номер.

С каждым подмножеством связывается множество всех номеров формул S. Назовем S разрешимым множеством, если рекурсивно. Так, множества и разрешимы.

Введем несколько определений, относящихся к нумерованным множествам и моделям.

Пусть S – произвольное множество. Нумерацией множества S назовем отображение множества всех натуральных чисел на множество S. Пара , где S – множество, а – его нумерация, называется нумерованным множеством; морфизмом одного нумерованного множества в другое назовем всякое отображение , для которого существует общерекурсивная функция h такая, что .

Нумерованной моделью (сигнатуры ) назовем пару , где – модель (сигнатуры ), а – нумерация основного множества M модели . Гомоморфизмом нумерованной модели в нумерованную модель назовем всякое отображение основного множества модели в основное множество модели , которое является как гомоморфизмом модели в модель , так и морфизмом из в .

Гомоморфизм нумерованной модели в нумерованную модель назовем эквивалентностью, если – изоморфизм на , а обратное отображение есть морфизм из в . Если существует эквивалентность из в , то эти нумерованные модели назовем эквивалентными и будем обозначать это так: .

По каждой нумерованной модели можно каноническим образом построить некоторое – обогащение модели (т.е. модель сигнатуры , основное множество которой есть основное множество модели , а предикаты из в совпадают с соответствующими предикатами ) следующим образом: в качестве значения константы , берем элемент .

- элементарная теория модели , т.е. множество всех замкнутых формул сигнатуры , истинных на модели ; - элементарная теория модели , т.е. множество всех замкнутых формул сигнатуры , истинных на модели ; - теория сигнатуры , системой аксиом которой является множество формул

.

Нумерованная модель называется конструктивной моделью, если множество

рекурсивно.

Секцией группы G называется всякая факторгруппа , где В, А – подгруппы из G, причем А – нормальная подгруппа в В.

Если G – нильпотентная группа без кручения и все секции ее верхнего центрального ряда имеют конечную размерность, то будем говорить, что группа G имеет конечную размерность.

Абелева подгруппа А группы G называется максимально абелевой, если А не содержится ни в какой большей абелевой подгруппе.

В работе Н.Г. Хисамиева, А.А. Конырхановой «О конструктивных нильпотентных группах» доказана следующая теорема 1. [6]

Теорема 1. Если в конструктивной нильпотентной группе без кручения существует вычислимо перечислимая абелева нормальная подгруппа А, содержащая центр Z, и такая, что факторгруппа без кручения и имеет конечную размерность, то центр Z является вычислимой подгруппой в .

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

гиперцентры группы , и – естественный гомоморфизм, а . Так как факторгруппа изоморфна , то группа имеет конечную размерность. Пусть – база факторгруппы . Докажем, что тогда справедлива эквивалентность:

.

Действительно, пусть для справедлива правая часть эквивалентности и – произвольный элемент группы G. Тогда существуют числа и элемент такие, что верно равенство

Отсюда и из предположения о справедливости правой части эквивалентности имеем . Отсюда и из того, что в любой нильпотентной группе без кручения верна импликация:

1) если , то

имеем равенство , т.е. принадлежит центру группы G. Эквивалентность доказана. Отсюда и из условия теоремы получаем, что центр Z является вычислимо перечислимой подгруппой в G. Так как дополнение центра в любой конструктивной группе вычислимо перечислим, то по теореме Поста центр Z вычислимая подгруппа в . Теорема доказана.

Следствие 1. Если в конструктивной нильпотентной группе без кручения ступени 2 существует вычислимо перечислимая максимальная абелева подгруппа А такая, что факторгруппа

имеет конечную размерность, то центр Z является вычислимой подгруппой в .

Доказательство. Покажем, что все условия теоремы 1 выполнены. Очевидно, что центр группы G содержится в А. Подгруппа А является нормальной в G. Действительно, пусть даны элемент и произвольный элемент . Покажем, что элемент перестановочен с любым элементом из А.

Так как коммутант содержится в центре нильпотентной группы без кручения ступени 2, то справедливы равенства:

Отсюда и из того, что А является максимальной абелевой подгруппой в G следует, что А является нормальной в G. Отсюда в силу максимальности подгруппы А и импликации 1) получим, что факторгруппа не имеет кручения. Таким образом, все условия теоремы 1, а следовательно и следствия, доказаны.

Теорема 2. Если в конструктивизируемой двухступенно нильпотентной группе G без кручения существует конечное множество

такое, что централизатор абелев и имеет конечную размерность, то центр Z является вычислим при любой конструктивизации ν группы G.

Доказательство. Докажем, что для подгруппы А справедливо условие теоремы 1. Для этого нужно показать, что А – нормальна в G. Пусть даны произвольные элементы и . Нам нужно доказать, что , т.е.

.

Действительно,

Следовательно , т.е. .

Докажем, что - без кручения. Действительно, пусть . Тогда . Отсюда по свойству нильпотентных групп без кручения имеем , т.е. .

Вычислимая перечислимость подгруппы А очевидно. Отсюда получаем требуемое.

Теорема 3. Пусть - конструктивная нильпотентная группа. Тогда существует вычислимая последовательность вычислимых подгрупп

такая, что центр .

Доказательство. Пусть и – централизатор множества . Тогда подгруппа вычислима и . Легко проверить, что последовательность вычислима и .

Следствие. Если в конструктивизируемой нильпотентной группе G существует конечное множество

такое, что для любого верно , то центр Z вычислим при любой конструктивизации ν группы G.

ЛИТЕРАТУРА

1. Ершов Ю.Л. Существование конструктивизаций. // Доклады АН СССР.- 1972.- №5(204) -С. 1041-1044.

2. Гончаров С.С., Молоков А.В., Романовский А.С. Нильпотентные группы конечной алгоритмической размерности // Сиб. мат. журнал.-1989.-№1(30)-С.82-88.

3. Латкин И.В. Арифметическая иерархия нильпотентных групп без кручения. // Алгебра и логика. - 1996.-№3(35)-С. 308-313

4. Гончаров С.С., Ершов Ю.Л. Конструктивные модели, серия: школа алгебры и логики, Новосибирск, Научная книга, 1999.

5. Каргаполов М.И., Мерзляков Ю.И. Основы теории групп. - М.: Наука, 1996.

6. Хисамиев Н.Г. О конструктивных нильпотентных группах. // Сиб. мат. журнал.-2007.-№1(48) - С. 214-223.



К содержанию номера журнала: Вестник КАСУ №6 - 2011


 © 2017 - Вестник КАСУ