Алгебра и логика, 39, N 4 (2000), 480-504
УДК 510.665:512.54
О РАЗРЕШИМОСТИ ТЕОРИЙ ПЕРВОГО ПОРЯДКА ГРУПП И МОНОИДОВ ЦЕЛОЧИСЛЕННЫХ МАТРИЦ Ю. В. Н А Г Р Е Б Е Ц К А Я
А. И. Мальцев в [1] установил, что кольцо Z целых чисел в полной ли нейной группе GL(n,Z) целочисленных матриц порядка п ^ 3 формульно определимо. Отсюда и из алгоритмической неразрешимости 10-й пробле мы Гильберта (см. [2]) легко следует неразрешимость элементарной теории группы GL(n,Z)
при п ^ 3. В [3] А. М.Слободской доказал, что универ
сальная теория группы G£(3,Z) неразрешима. В настоящей работе эти результаты существенно усиливаются и дополняются. Более того, теперь становится достаточно реальным решение вопроса о нахождении в некото рых рамках всех разрешимых теорий группы C?L(3,Z) и тесно связанного с ней полного линейного моноида MX(3,Z). Для этого можно воспользо ваться схемно-альтернативной иерархией, и указанный вопрос рассматри вать в русле концепции критических теорий, развитой Ю. М.Важениным в работах [4—7]. Основной результат настоящей работы — Т Е О Р Е М А . Теории V-nVGL(3,Z), 3-iAGL(3,Z), VnVML(3,Z) и 3-i A MX(3,Z) являются
критическими,
а теории 3VA V<7L(ft,Z),
3V A VML(n, Z) — разрешимыми при любом п ^ 3. Таким образом, неразрешима, в частности, подтеория V-i VG\L(3,Z) универсальной теории V-i A VGL(3, Z), a 3V -фрагмент позитивной теории группы GL{n, Z) разрешим для любого п ^ 3. В связи с этим возникает естественный ВОПРОС. Разрешима ли позитивная теория группы G£(3,Z)? ©
Сибирский фонд алгебры и логики, 2000
481
О разрешимости теорий первого порядка При положительном ответе на него будет справедлива
ГИПОТЕЗА. Границей разрешимости группы GL(3,Z) является множество {V-iV, З-1Л}. В этом случае I-теория GL(3,Z) для языка L из схемно-альтерна тивной иерархии будет разрешима тогда и только тогда, когда L 2 V-»V и L 2 3-чЛ. Напомним кратко необходимые определения из [4—7]. Пусть £ — множество всех формул логики первого порядка некоторой сигнату ры сг, записанных в предваренной нормальной форме. Обозначим через СХ...СР
V А8 V' (где С,- 6 {V,3}, С, ф Сг+1 для t € { 1 , . . . , р - 1},
г, s,t E {0,1}) язык из £, состоящий из всех формул, которые имеют в качестве блочной схемы кванторной приставки подслово слова С\... Ср и не содержат в своей записи связок ~>, Л, V, если соответственно г = 0, s = 0, £ = 0. Иными словами,
{
d+lc(t)+l t=i
(/ = P H Q X
(I < р или
i=i
= Ci)), s g n ] P m ( i , j ) ^ r, sgn^Tc(i) ^ s, s g n d < t >.
Здесь, z 1 •= 2, z° — пустой символ, sgnfc — знак натурального числа fc, ipij — атомарная сг-формула. Обозначим через -i r Л* V* и ш~|г Л5 V* соот ветственно бескванторный подъязык языка V-«r Л5 V* и объединение всех языков вида С\ . . . Ср~»гЛв V*. Заметим, в частности, что vo-\t\\l = £. Семей ство SA всех языков трех указанных видов упорядочивается по включе нию и называется схемно-альтернативной
иерархией языков. Для языка
L E SA класса К алгебраических систем сигнатуры а через LK обозначим Х-теорию или теорию языка L класса К, т. е. совокупность всех предло жений из L, истинных на К. Схемно-альтернативной
иерархией теорий
класса К называется частично упорядоченное множество
SAK^±({LK\L£SA};C). Теорию называют критической, если она является минимальной в иерар хии SAK среди неразрешимых теорий класса. Границей разрешимости
482
Ю. В. Н&гребецкая
класса К называется множество Ъ(К) ^ {L G SA | LK — критическая
теория}.
Описание критических теорий или, что равносильно, нахождение границы разрешимости класса К означает установление полной в рамках иерархии SAK алгоритмической картины для Л', поскольку теория LK € SAK бу дет разрешимой тогда и только тогда, когда L 2 L\ для любого языка
I i Е Ъ(К). Пусть даны языки L\, L2 6 SA сигнатур <7i, о2 и алгебраические системы А\_ т± (Ai;<72), Ag ^± (-Аг?^)- Будем говорить, что теория Ь\А\ интерпретируется
в теории £2^2 (обозначается: LiA± •< £2^2)?
если
су
ществует алгоритм, который по каждому предложению и сигнатуры &\ языка L\ строит предложение и* сигнатуры а2 языка L2 так, что А± (= v тогда и только тогда, когда А^ (= z/*. Легко понять, что если теория -EiAi интерпретируется в теории LiA^
то из неразрешимости первой следует
неразрешимость последней. Всюду в настоящей работе используются следующие обозначе f
ния: J(x) — свободная группа над алфавитом { # i , . . . , ж п }, 3\М(ж) — свободный моноид над алфавитом {х%,..., ж„}. Обозначим через Е и €fj единичную матрицу и соответственно матричную (г,^-единицу порядка 3. G ^
Хт, (х) ^ <
если х £ Ти
I 0, если a; G Т\ТХ
для каждого х £ Т. Для доказательства первого утверждения теоремы установим, что справедлива
483
О разрешимости теорий первого порядка Л Е М М А 1. Теории V Л VG, 3 Л VG разрешимы.
ДОКАЗАТЕЛЬСТВО. В силу полноты элементарной теории £G до статочно показать разрешимость теорий V v G и 3 Л G, ибо можно вос пользоваться дистрибутивностью квантора V относительно конъюнкции и квантора 3 относительно дизъюнкции. Пусть v и /л — произвольные пред ложения языков W и ЗЛ, а именно:
(
<*+1
\
/<*+1
\
Y од (ж) = 1 I , /i ^ Зж ( Д од (ж) = 1 1 , где од (ж) 6 Э^ж), г Е { 1 , . . . ,d}, ж ^ a?i .. .ж п , d Е u>. Тогда (1) (G (= t/) <^4> (существует г € { 1 , . . . , d}, что од (ж) = 1 в Зг{х))\ (2) G h A*. Поскольку проблема равенства слов в свободной группе конечного ранга разрешима (см. [8]), то из утверждений (1) и (2) будет следовать заключение леммы 1. Утверждение (2) очевидно, ибо w(E,.. .,JE7) = E. В утверждении (1) импликация (<=) очевидна. Докажем (=>). Известно (см. [9]), что матрицы £7 + 2ei 2 и Е + 2e2i свободно порождают свобод ную подгруппу в G, Кроме того, в свободной группе ранга 2 существует подгруппа, изоморфная свободной группе счетного ранга (см. [8]). Следо вательно, в G имеется подгруппа, свободно порожденная счетным множе ством {£, | % Е N}. Значит, для любого слова w(x) из ЗГ(ж)
Мб,
. . . , W = £ B G ) «
(U.(X)
= 1 в 3-(f)).
Отсюда следует истинность импликации (=>)• Лемма 1 доказана. Дока жем, что теории V-i V G, З-i Л G являются критическими. Согласно [2], теория V-i Л VG неразрешима. Поскольку элементарная теория £G пол на, можно воспользоваться дистрибутивностью квантора V относительно конъюнкции. Теория V-i Л VG оказалась бы разрешимой, если разрешимой являлась бы теория V-i V G. Стало быть, последняя теория неразрешима. В силу упомянутой полноты и двойственная теория 3-> Л G будет неразре шимой. В иерархии SAG теории V-* V G и Э-i Л G покрывают теории V V G, 3 Л G, 3~iG, V~iG, -i V G, -i Л G. Разрешимость первых двух из них выте кает из леммы 1 благодаря включениям V V G С V Л VG, 3 Л G С 3 Л VG.
484
Ю. В.
Нагребецк&я
Примененяя отрицание, третью и четвертую теории сводим к теориям VG и 3G соответственно, которые разрешимы в силу включений VG С V V G, 3G С 3 Л G. Бескванторная теория -iVG разрешима в силу того, что лю бое предложение <р языка -iV сигнатуры (•,~ 1 ,1) очевидным образом ал горитмически перерабатывается в равносильное ему предложение одного из трех видов: (1 = 1), (1 = 1 V 1 ф 1), ( 1 ^ 1 ) . Ясно, что <р Е -«V G тогда и только тогда, когда <р равносильно предложению (1 = 1) или <р равно сильно предложению (1 = 1 V I ^ 1). По этой же причине разрешима и теория -«AG. Таким образом, коль скоро все теории, покрываемые в иерар хии SAG теориями V-i V G и З-i Л G, являются разрешимыми, получаем V-.VG, 3 n A G e B ( G ) . Покажем теперь, что теории V-i V М, 3~i Л М являются критически ми. Для этого докажем, что V-i V G •< V-i Л VM, тогда теория V-i Л УМ будет неразрешимой. Пусть z/ ;= Vx ( V ~|Г* ^(ж) = 11— произвольное пред ложение языка V-iV сигнатуры {•,
_1
, 1 ) , где r,- E {0,1}, w t (x) E vF(x),
х =i х\ . . . х п . Слово w(x) — w ( x i , . . . , х п ) можно рассматривать как сло во w(xi,..
. , х п , х ь . . . ,х п ) € 3\М(х I , . . . , x n , x i , . . . , х п ). Построим предло
жение /п+1 I/* ;= V^i . . . ХПХХ • • • ^n ( Л #t Xi — 1 \t = l
fc+1
\
• У V'w.'^i,...,^,*!,...,^) = 1 I . t=l
/
Во-первых, и* E V~i Л V, а во-вторых, и* является предложением сигнату ры (•, 1). Утверждается, что М \= и* тогда и только тогда, когда G \= и. Действительно, если М (= И , то, взяв для любых x i , . . . , x n Е GL(3,Z) в качестве х ь х 2 , . . . , х п матрицы xj*1, х^" 1 ,..., х" 1 , получаем истинность предложения \ / V ' w a ( x i , . . . , хгг, х ~ \ . . . , х" 1 ) = 1. г= 1
Следовательно, G [= гл Обратно, пусть G \^ v. Возьмем произвольный набор матриц х\,...,
x n , x i , . . . , хп Е ML(3,Z) таких, что х, х,- = Е для
каждого г Е { 1 , . . . , к}. Тогда det xg x, = det X{ det xt = 1, и поскольку det х,-,
485
О разрешимости теорий первого порядка
detXi E Z, то detxi £ {±1}. Следовательно, ж,- £ GL(3,Z) и я* = х" 1 . Таким образом, М (= v*. Теория V~i Л VM, а в силу теоремы из [4] и теория Э-i Л УМ нераз решимы. Используя рассуждения, приведенные при доказательстве того, что теории V~iVG и 3-> Л G являются критическими, заключаем: V-Л/, З-iA е В(М). Доказательство второго утверждения теоремы будем проводить для п = 3, ибо для п > 3 разрешимость теорий языка 3V Л V группы GL(n, Ъ) и моноида ML(n, Z) доказывается аналогично. Сначала сформулируем и докажем ряд лемм, в силу которых теория 3VG будет разрешимой. А затем покажем, как, видоизменив формулировки и доказательства этих лемм, можно будет доказать разрешимость теории 3\/Л VG. Тогда и теория ЗУЛ УМ будет разрешимой. Введем обозначения, которыми всюду ниже будем пользоваться:
{(
о-\ а 2
{\ 0
ЛЕММА €
{±1}, о
a,-,6j,c 3 €Z} n G I ( 3 , Z ) ,
Ь 2 Ь3
&i
X,!/г
а3 \
0
с3 /
# + У ei3 + zе23, 2.
w(a,x) ^=t aixeia2xe2
Пусть
?=i a i . . . a n .
такая,
что
G\£y>(A,X)
где .4
— кортеж, длины
f/уг ^ Е + у e3i + z е 32 . . ..anxe",
Тогда найдется матрица т
и Х
ф
п матриц
X
Е
для
из
множества
где Si £
любого т
€
GL(3,Z) £
N,
GL(3, Z)\S,
¥ > ( А , Х ) ^ (w(i4L,X) = £?Vu;(i4!,А") = - £ ? ) . ДОКАЗАТЕЛЬСТВО. Предположим противное. Тогда G \= (р(Л, X) для любой матрицы X 6 GL(3, Z) такой, что Хт ф Е при любом т € N. Подставим в равенства w(A,X) € Z \ { 0 } , А^±АХ...АП
= ±Е вместо X матрицу XyiZ, где y,z E
и
/ а? а? 4° \ Ai
4° 4° 41)
W(О
„(О
>')
7
г€ {!,...п}.
Ю. В. Нагребецк&я
486
Учитывая, что Ху; — X-V}-z и
/ 0 0 а? \ Ai e 13 =
О О Ь®
/ О О af М 623 =
\
О О bf
\ о о 4° /
\ О О 4° ) получаем равенство
п
Ai+Ei
( О О «<•> \ ( о о а? (О У + Si 0 0 6!2 О О Ь\
\ = ±Е.
(1)
V о о 4° / J
V о о cw у
Равенство (1) справедливо для всех у, z Е Z, следовательно, левая и правая части равенства равны как многочлены от у, z над кольцом Z 3 x 3 . Таким образом, все коэффициенты а (к), к Е {0,...,гс}, при одночленах yn~fc zk являются нулевыми матрицами. Из равенства (1) следует, что
( 0 0 ар>ft4" ^ «=2
а(0)
о о ь г Г Ы(') k(i)
где е
«'=2
1=1
1)
V о о 4 х-2п4°
•*п«<-
/
Поскольку detAi ^ 0, имеем ТТс^ — 0 и, следовательно, найдется номер h € { 2 , . . . , п} такой, что q 1 ' = 0, Применяя аналогичные рассуждения к формуле ф(АуХ)
^ ( Л ^ Х ^ Л ч + 1 ^ ^ 1 ...А„-У е М1Л: в1 . . . Л ^ Л ^ -
1
=±£7),
вытекающей из формулы у?(А,Х), убеждаемся в том, что для некоторого г*2 € { 1 , . . . , п} верно q 2 ' = 0 и «2 7^ *i- Более того, в силу равносильности формул w(A, X) = ±J5 и ^(А, X) в G можно считать, что, г*2 = 1, %\ > 1. Теперь докажем справедливость А^ Е § для некоторого & Е {!»••• . . . , п}. Тем самым получим противоречие с предположением. Пусть / ;=± ^
I i Е { 2 , . . . , п} | С} = 0 >. Заметим, что н Е / , и поэтому / ф 0 .
Обозначим | / | = /. Если J — произвольное подмножество множества { 1 , . . . , п}, то под Sj будем понимать отображение из { 1 , . . . , п} в {1, 2,3},
487
О разрешимости теорий первого порядка,
определенное равенством Sj(i) = 2xj(i) + X{i,...,n}\jW Д л я каждого % 6 6 { 1 , . . . , п}, где XJ> X{i,...,n}\J ~~ характеристические функции для мно жеств J, { l , . . . , n } \ J соответственно. Исходя из равенства (1), вычис лим ot{l):
«(')=*
п( ° о «а« ^
Е
П
7С{1,...,т»}, \J\ = J / 0
-
t=l
о о bg(0 0
,(») » ° «MD.nCd
° с8(о / \
Е
(1) (О о о #.',„ п с4/(1) 'Mi) H
JC{l,...,n},
,(1) ^о о ^ ч П й j
£
«=2 ГГ>)
JC{1,...,«},
И =/ / 0 0 а (1)
\
Sj(l)
«
U
где Aj =i e
Si) П j6{2,...,n}\J
JJ <€J\{1}
Аь
U
a
0
о *$i
0
° c$i> У
Пусть J С {!,•.., п}, |«7| = / и J ф / , тогда Aj — нулевая матрица. Действительно, поскольку \J\ = |/| = /, то I\J jfo G { 2 , . . . , n}\ J имеем с ^ '
ф 0 и для некоторого
0. Следовательно,
Д
с (xj) = 0, и
j€{2,...,n}\J
поэтому Aj = 0. Поскольку 1 £ J, то
\i€/
п
>е{2,...,п}\/
/0
„ш
0
af>\
0 0 Ь?>
V 0 0 ci x ) У
ЛЛ ф 0, Коль скоро det Ai / 0 и для всех j £ { 2 , . . . , п}\1 выполняется с\' то найдется к Е / , при котором 4
— 0, и, следовательно, Ak E S; что и
требовалось показать. Лемма 2 доказана. Назовем замыканием произвольного множества А множество А
^
^ Л и {а"1 | a 6 Л} групповых слов над алфавитом Л. Множество Л назовем замкнутым, если Л = Л. Введем следующее семейство множеств групповых слов над алфавитом Л U {b,b~1} U {с, с""1}, где Л — замкну то: И^(Л,Ь) т=± ЛЬ U ЛЬ" 1 , ИЪ(Л,Ь) ^ Л ь и Л ь ~ \ И^з(Л,Ь) ^
И^(Л,Ь)и
Ю. В. Нагребецкая
488 UW2(A,b),
ТУ(Л,Ь,с)
W2{A,b)
U Widbb-1}^)
U W2{A,c)
U
Л Е М М А 3. Для любого конечного замкнутого множества А ма триц из GL(3, Z)\{±JB} существуют матрицы Дд, С л € GL(3, Z) такие, 4moW(A,BA,CA)f)S
= 0.
ДОКАЗАТЕЛЬСТВО. Покажем сначала, что для любого конечного замкнутого множества Л матриц из GL(3, Z)\{±1?} существует матрица Вл
Е GL(3,Z)\{±E}
такая, что W3(A, BA)f)S
тивное: W3(A,X)C\8
= 0 . Предположим про
ф 0 для любой матрицы X Е GL(3,1)\{±E}.
По
скольку J7y^ 0 { ± ^ } Д л « всех у, 2 Е Z\{0}, то И^СЛ, t/^) f]§ ф 0 для любых у, z £ Z\{0}. Заметим, что U~zl == U-Vi-Z для любых t/, г Е Z. Пусть А — произвольная матрица из GZ(3,Z) и пусть А имеет вид: / ai
а2
а3 \
\ bi
b2
b3
\ ci
c2
c3 J
.
(2)
Тогда a\ + a3 у a2 + a3z AUyz =
&i + &3 У ^2 + b3 z c\ + c3 у
Uy* AUyz =
b3 c3 J
I &i + a3 у
a2 + a3z
a3 \
b\ + b3 у
b2 + b3z
b3
-a2 у - b2z + c2 + zt
t
\ -ax y-hz где t
c2 + c3 z
a3 \
+ ci+yt
)
-a3y — b3z + c3. Заметим, что (AUyzeB)
(c 3 = ± l , У = ТСь 2 = q=c2), -(ai ^ l)y - biz + ci
(u-lAUvxe&)
-a2y-{b2^l)z - a 3 y - b3z + c 3
(3)
=
0,
+ C2 -
0,
=
±1.
(4)
Легко проверить, что множество В является замкнутым. Для этого доста точно показать, что А - 1 б S для произвольной матрицы А 6 S. Действи тельно, пусть матрица А имеет вид (2) и А 6 S, т.е. С\ = с2 = 0, с 3 = ± 1
489
О разрешимости теорий первого порядка Тогда 1
А- ^
а
СЗ&2
- ^ 2
-c 3 6i
c 3 ai
a3&i - ахбз
0
d
0
2 ^ 3 ~ «3^2
\
» )
1
где d ?=± csdetA.
Таким образом, Л" Е S. В силу нашего предположения
истинно утверждение Vy, * Е Z\{0} ( Л ^ и Л С 7 . ~ П 8 ^ 0 V (Л^* U Л*7-*-*) n S / 0 ) . Поскольку множество § замкнуто, справедливо \/y,z£
Z\{0}
(ЛС/у2 ПcS ф 0 V АЕЛ.У,-, П S ф 0 V Л ^ г VAu-y>~z Г\§ф0)
П$ф0
.
В силу конечности множества Л имеет место хотя бы одно из двух утвер ждений; 1) найдется матрица А Е Л, бесконечное множество целых чисел К} бесконечные множества целых чисел Ку для каждого у € К такие, что A Uyz Е S для любых у Е Я", z Е А у ; 2) существуют матрица i E Л, бесконечное множество целых чисел L, бесконечные множества целых чисел Ly для каждого у £ L такие, что для любых у Е £, z Е Ly. Первое невозможно в силу (3) и бесконечности множеств К и Jfy. Второе, в силу (4) и бесконечности множества Ly для любого у £ L, вы полняется только в том случае, если Ьг = 0, Ь2 ^F 1 = 0 и &з = 0. Таким образом, для любого ?/ Е L i -{ахц--1)у + сх
=
0,
Я - а 2 у + с2
=
0,
V ~-а 3 у4-с 3
=
±1.
Поскольку множество L бесконечно, то ах ~-f 1 = 0, с\ = а 2 = с2 = -• а 3 = 0, с 3 = ± 1 . Следовательно, А £ { ± # } , что неверно, ибо А € Л иЛССЬ(3,2)\{±4 Итак, существует матрица Дд ИЪ(Л,ДА)П8
=
0 . Множества Л,
£
GL(3, Z)\{±j£} такая, что
{ДА,^1},
И^(Л,В Л )
конечны
Ю. В. Нагребецкая
490
и замкнуты, следовательно, таким же является и множество Л\ ^
Л и {Вл,Вд1}
U WX(A,BA).
поэтому ТУ^Л, Дд) П {±-£7} = =
Кроме того, WX{A,BA)
П S =
^ 0,
0 и, следовательно, Лх П {±£7}
=
0 . Из доказанного выше вытекает существование матрицы BAl
€
£ GL(3,Z) такой, что И ^ О Л ь Д ^ ) П § = 0 . Имеют место включения
^ ( { Б л , ^ 1 } , ^ ) С WMuBAl),
Wl{Wl{A,BA),BAl)
С ТУ^ЛьВ^),
И ^ Л , Дд,) С Т72(Л1, ДА, ) и ИЪ(Л, В л ) С Ж 3 (Л, Дд). Отсюда следует, что И'(Л, Д А , Д*,) С И^3(Ль Дд,) U ^ 3 ( Л , Дд) и, значит, W(A, BA, BAl)nS — 0 . Таким образом, в качестве матрицы Сд можно взять матрицу
= ВАх.
Лемма 3 доказана. Сформулируем два полезных замечания. ЗАМЕЧАНИЕ 1. Пусть P(t/, z) G Z 3x3 [y, z] и пусть Z - бесконечное множество целых чисел, {Zy | у 6 Z} — некоторое семейство бесконечных множеств целых чисел. Тогда справедлива следующая импликация: если истинно утверждение Vy € ZVz £ Zy Р(у, z) — О, то Р(у, z) — 0 в Z 3x3 [t/, z], т. е. коэффициенты при всех одночленах в P(y,z)
являются нулевыми
матрицами. Замечание 1 непосредственно следует из теоремы о числе корней мно гочлена над полем комплексных чисел [10]. ЗАМЕЧАНИЕ 2. Пусть для некоторого набора А матриц из GL(3, Z)\S в G истинно утверждение k+i
VX \ / (wi{A,X)
= EV
Wi{A,X)
= -E) ,
2= 1
где Wi(a, x) £ if(ai, a 2 , . . . , а п ,ж). Тогда найдутся бесконечное множество целых чисел Z, бесконечные множества целых чисел Zy для каждого у £ Z такие, что в G истинна дизъюнкция к +1
\J (yyezvze
zy К(А,ху2) = я v wt(A,xyz) = -£?)) .
ДОКАЗАТЕЛЬСТВО. Очевидно, что для любых у, z £Ъ найдется qyz £ {!,...,&}, при котором выполняется равенство wqyz{A,Xyz)
= ±2£.
491
О разрешимости теорий первого порядка
Зафиксируем у0 £ Z. Поскольку {qVQZ | 2 € Z} С { 1 , . . .,&}, существуют номер qyo £ { 1 , . . . , к} и бесконечное подмножество целых чисел Z^ такие, что истинно утверждение V* 6 Zyo (wqyQ (А, Х Л ,,) = Е V ^
о
(А, Хуо>2) =
-Е).
Аналогично, найдутся номер д* и бесконечное множество Z целых чисел, для которых выполняется VyeZVzeZy
(wq.{A,Xyz)
= EVwq.(A,Xyx)
= -£?),
что и требовалось доказать. Л Е М М А 4. Пусть u>i(a, х) ;=± a^a^'i а{2хе{* ... а{пх€(п , где ег Е {±l},ai- Е { a b . . . , a n } . Пусть также А Е [G£(3, Z)\S] n . Тогда найдется матрица X Е GL(3, Z) такая, что G ^= <£>(А, X), где Jk+1
^(А, X) ^ \ / (wt{A,X)
= EVwi(A,X)
-
-S)
tt Jfm ^ f? для любого т Е N. ДОКАЗАТЕЛЬСТВО. Предположим противное. Тогда С? (=
Vy E Z Уг Е Z V (wi(A, Хух) = # V t^(A, Xyz) = - t f ) . Согласно замечанию 2 существуют номер г* Е {1,...,&} и бесконечное множество Z целых чисел такие, что для каждого у Е Z найдется беско нечное множество целых чисел Zy, для которого Vy£Z\/z£Zy
(wim(A,Xyz)
= EV wim(A,Xyz)
= -E)
.
Доказывая лемму 2, мы приравнивали коэффициенты при соответ ствующих одночленах в многочленах от у, z. Рассуждая подобным обра зом и используя замечание 1, приходим, как и при доказательстве леммы
Ю. В. Нагребецкая
492
k+l
( \ 2, к противоречию. Следовательно, G (= Д (Wi(A,X yz ) ф ±Е) для некоторых y,z G Z\{0}. Ясно, что X™z ф Е для любого т G N. Лемма 4 доказана. Л Е М М А 5. Пусть Wi(a, х) ^=± a^ xmii а^хт{1 ,.. а{к.хт%к*, где rrtij G Z\{0} и {ц,...,
г^.} С { 1 , . . . , тг}. Пусть, далее, т0 G N и А ~
набор матриц из GL(3,Z)\{±I?}. Тогда найдется матрица X G GL(3,Z) такая, что А:+1
G)£
где<р(А,Х)?±
\J (v>i(A,X) = EV Wi{A,X) = ~Е) , i=i
и X™ ф ±Е для любого т G N такого, что т ^ то. ДОКАЗАТЕЛЬСТВО. Пусть А ^ Аг...
Ап и Л ^ {Аи...,Ап}.
По
лемме 3 найдутся такие матрицы В, С 6 GL(3, Z), что W(A, В, С) П§ = 0 . Равенства WJ(A, БУС) = ±JE равносильны в G равенствам и)\(А*, Y) = ±2?, где г^(Л',У) ^ А^У^А^У*»* . ..A( v У£'"< для некоторых е^ G {±1} и А!{. G GX(3, Z)\{±i7}. Причем для каждой из матриц верно А!{. е {CB,B^C^l}D{CAB,CAC^\B^lAC"l,B^lAB Поскольку CB,B-lC~l В^АВ
G Wi({B,B'l},C)
G W2(AB), С А Б ^ - М С "
1
\ А € А}. и САС"1
G Wi{Wi{A,B),C)
G
^2Й,С),
для любой ма
трицы A G Л, то каждая матрица А^. G W(A, В, С) и, значит, по лемме 3,
^ * s. Если Хт ф Е для любого т G N, то, очевидно, Х г а ^ ± Е для любого т £ N. Равенства Хт = ±Е равносильны в G равенствам um(A",Y), um(A",Y)
где
?=± (А"У) га = ±Е, А" ?± СВ. Мы уже доказали, что С В <£ §,
поэтому по лемме 4 существует матрица У £ GL(3, Z) такая, что G ^ fi
( V т'{(А', Y) = EV < ( А ' , У) = -Е \
7 т° v
->
\
V «m(A",y) = £;vUm(A",y) = -£; . \т=Х
/
493
О разрешимости теорий первого порядка
Следовательно, G ф v?(A, X) и X™ ф ±Е для любого га Е N такого, что га ^ гао. Лемма 5 доказана. Л Е М М А 6. Пусть w(B,X)
^ B1v1(X)B2v2(X)
...Bmvm(X),
где Bi Е G?£(3,Z), Vj(f) £ У (ж), г Е { 1 , . . . , г а } , причем V\{x) . ..vm(x)
ф 1
в £Г(аГ) и Vi(x) несократимы в ЗГ(ж). И пусть в G истинна формула <р{В) ^ («;(В, X) = EV w(B, X) ^ -Е^ . 2Ъг
- -S) , (
причем, wi(x) . ..Wk{x) ф 1 в
J(x).
ДОКАЗАТЕЛЬСТВО. Опишем некоторую последовательность пре образований слова w(b} х) € 3^(6, х). На первом шаге заменим в слове w(b, x) вхождение всех букв Ь, на пустое слово, если и только если Д 6 {d:E} для каждого г 6 { 1 , . . . , г а } . Полученное слово заменим циклически равным ему циклически несократимым (см. [8]) в J(ft, x) словом: wW(S, х) ^ и?{Ь)ь^\х)и^\Ъ)уЧ\х)...
<)(?)<)(х),
где IT- (ж) 6 3*(ж),?г ^(6) Е 3^(6). Заметим, что, во-первых, из истинности формулы (р(В) в G, очевидно, следует истинность формулы Vl
(В) ?± VX (v>W(B, X) = EV wW(B, X) = - я ) ,
а, во-вторых, слово г;} (ж)и2 (ж) .. .г;^(ж) является циклической переста новкой (см. [8]) слова Vi(x)v2(x) .. .vm(x) ф 1 в Зг(£). Если существует j 0 Е { 1 , . . . , rai} такое, что uyj(b) E { ± # } , то пере ходим ко второму шагу: в слове и/ 1 ) (6, £) заменяем вхождение всех подслов Uj (6) пустым словом, в том и только в том случае, если vS \В)
Е {±2?}.
Ю. В. Нагребецкая
494
Произведя, если потребуется, циклические сокращения в группе jF(b, #), получаем слово аД2)(Ь, х) ^ u?\b)v[2\x)u
u%\(b)v%l(Z),
циклически несократимое в ~Г(Ь, х). Из справедливости в G формулы (pi (В) следует справедливость в G и формулы (р2(3) — VX (wW(B,X)
= ЕУ wW{B,X)
=
-EY
где слово v\ {x)v\ \x) . . . и ^ (я) является циклической перестановкой сло ва v[ {x)v\
(x) .. .г;^! (ж), а значит, и слова Vi(#)t>2(a0.. .vm(x),
и т.д.
Ясно, что на каком-то шаге d мы получим циклически несократимое в ;У(Ь, х) слово
wW(b, х) ^ ьР(Ы*&*Р(М*(2) • • • «Ц®»й(*) такое, что истинна формула ipd(3) ч=± V-Y ( w ^ ( B , X) = £7 V w ^ ( B , X) = -Ь 1 ) , причем wj[ (-^)> • • • > ^ d ( - ^ ) ^ {^^Ь клической перестановкой слова v\(x)...
а
слово г;} (ж) .. . Vm (#) является ци vm(x). Действительно, если это не
так, то на некотором шаге / получили бы истинность в G утверждения Vx(v«\x)v$)(X)...v«\(x') Wvll)(X)v?(X)...vg\(X)
= E =
-E),
откуда следовала бы истинность утверждения
А
это
возможно
только
при
[v[\x)v2(x)...v^}l(x)j
= 1 в fJ(x), что равносильно v['(x)vy(x)
...
. ..VTOI(^)
С другой стороны, v\\x)v2
=
(см.
1 В 3{Х).
доказательство
леммы
1)
(х) ...vfrSiix)
циклическая перестановка слова V\(x)v2(x).. .vm(x) ф 1 в Итак, формула
—
f
J(x).
и\ ( 5 ) ,
Wi(x) ;=± v\ (x) для каждого i £ {1,...,га^} получаем истинность фор мулы ф{С)« Лемма 6 доказана.
495
О разрешимости теорий первого порядка, Покажем разрешимость теории dVG. Л Е М М А 7. Пусть v ^=± ЗЗУхф(а,х)
— произвольное
предложение
1
языка 3V сигнатуры {•,~ ,1), где ф(а,х) ?± (ui(a)v1(x)..
.uk(3)vk(x)
= 1),
щ(а) £ (${а), Vj(x) G 3*(х), х ;=ь х\ . . . # П; а ч=± а\... ап. Тогда (G (= Р) <=Ф> <=> (щ(%) • • -Vk(x) = 1 в ЗГ(ж)).
ДОКАЗАТЕЛЬСТВО. Пусть сначала vi{x)v2(S)..
. v*(f) = 1 в J ( f ) .
Тогда G \= и, для этого достаточно положить а ?=± Е...Е.
Обратно,
пусть G |= I/, т. е. существует кортеж Л е [GL(3,Z)] n , для которого G [= MX ф{А,Х).
Предположим противное: Vi(x)v2(x)..
.vk(x) ф 1 в fJ(x).
Обозначим через В,- матрицу щ{А) для каждого г Е { 1 , . . . , к}. Поскольку условия леммы 6 предполагаются выполненными, без ограничения общно сти можно считать, что все В,- £ {±Е} и Vi(x) несократимы в 5{х). Итак, G И VX ( ^ ^ ( Х ) . ..Bkvk(X)
= ±я)
(5)
для некоторых Б х , . . . , Вк £ GX(3,Z)\{±£'}, причем и/(ж)г;2(х).. .vk(x) ф 1 в ЗГ(ж). Пусть гу(Ь, ж) ;=± biVi(s) • • -bkvk(x). Слово w(b,x) будет несократимым в 'J(b, x). Пусть слово w(b, x) графически равно слову Ь1х?1...х11Ь2х?>...х?'...Ькх?к...х/1к, где ai,...,/Si,Qf2,...,/32,---,Offc > .-Mi s ife
£
Z \ { 0 } , и если /
^
{п,...
• • м Л » * 2 , . - - , 7 2 , - . . , ^ , - м ^ } » ТО / С { 1 , . . . , п } .
Опишем алгоритм, который путем последовательного применения леммы 5 с использованием утверждения (5) строит цепочку вытекающих друг из друга следствий, последнее из них будет противоречить лемме 5. На первом шаге фиксируем х\. Заметим, что |/| > 2, иначе мы получили бы противоречие с леммой 5. Кроме того, без ограничения общности мож но считать, что j k ф 1, ибо существует циклическая перестановка w(b,x) слова w(b} х) такая, что равенства w(6, х) = 1 и й)(6, х) — 1 равносильны в
Ю, В. Яагребедкая
496
G. Просматриваем слово w(6, x) слева направо и выписываем так называ емые х\-чередующиеся слова, т. е. слова вида fm,d(b,:ri) ^ c1xsl1c2xs12 .
..cdx\dcd+i,
где т е { l , . . . , f c } , de {О,..., к - тп}, <$,- € {±1}, е.- = Ь то+1 -- Ь * € { 2 , . . . , d } ; Ci G {1,ЬТО}, c<*+i 6 {l,bm+rf}- Будем рассматривать только те слова ука занного вида, которые являются максимальными подсловами слова го(Ь, х). Заменим в слове £m,d(b, &i) буквы Q + I на Ь^1, если J3m+d = i B ^ 1 , c^ — на b
m\-V
еСЛИ
#гп+<*-1 = ± В ш + 1 >
С
^"1 ~
Н аЬ
т+2>
е с Л И
#m+d-2 = ±-Вт+2
ИТ
'
д. Наконец, заменим Q _ P на Ь^+р+1, если J3 m + d- p -i = ± В ~ + р + 1 . Ясно, что Р ^ [f] • Обозначим через £^ d (b, x\) слово, полученное из слова £т,<*(&> х{) в результате этих преобразований. Пусть £ m d (b, a?i) — циклически несократимое слово, циклически рав ное слову £ т сДЬ, х{). Для слова £ т d(b, x\) возможен один из трех случаев: (а) €md&xi)
— xi
б
ж
(в)
^ ^ ( Ь , жх)
( ) С,<Д aiX°la2Xi2
в
^(Ь, »i) для некоторого а £ Z\{0};
b
0 = m+g в У(Ь, жх) для некоторого q Е {О,..., d}; является
циклической
перестановкой
слова
.. .щх*1, где o?i, .. .,<*/ Е Z\{0},
а ь . . . , а / е {Ьп ЬГ1 l * e {l,...,fc}}u{bibi \BiBj£±E,
ije
{1,...,*}}.
В каждом из случаев мы находимся в условиях леммы 5. Следователь но, существует матрица X £ GL(3,Z) такая, что £ т ^ ( В , Х ) ф ±Е в G для любого х 1 -чередующегося слова £m,<*(b, #i). Значит, в силу сделанного предположения в G истинна формула Vx2 ...xn (wW(B{1\y) для
некоторого
набора
= ЕУт^(В^\у)
= -£?)
В ( 1 ) £ [GL{Z,Z)\{±E}fl
, кг 6 N,
где
€ 2Г(у)\{1}, У — ^2 ...ж п . Таким образом, нам удалось избавиться от переменной х\ в исход ной формуле. Если п > 2, переходим ко второму шагу алгоритма, а имен но: фиксируем Х2 и выделяем x
497
О разрешимости теорий первого порядка
гу(1)(б(1), у) и т. д. Продолжаем до тех пор, пока не дойдем до переменной х„. Тогда получим, что в силу сделанного предположения в G истинна формула Vxn ( V " ) ( B ( " \ z n ) = £ V № ' n ' ( B » , ^ = для
некоторого
набора
-Е)
В ( п ) € [GL(3,Z)\{±E}]kn
, kn € N,
где
А это противоречит лемме 5. Следовательно, предположение о том, что v\(x) . . . Vk(x) ^ 1 в У(х), неверно. Лемма 7 доказана. Поскольку проблема равенства слов в свободной группе конечного ранга разрешима, то из леммы 7 следует разрешимость теории 3VG. Для доказательства второго утверждения теоремы в случае группы G видоизменяем формулировку и доказательство вспомогательной леммы 7. Для этого мы используем ЗАМЕЧАНИЕ 3. Пусть для некоторого набора А матриц из <7L(3, Z) истинно в G утверждение W I У (w(A, х) = Е) V (w(A, x) = - £ ) ) • Тогда найдутся бесконечное множество целых чисел Z, а также совокуп ности бесконечных множеств целых чисел {Zyi
| ух G Z} ,
{ZyiZl
1^/1*12/2*2 I Z 2 G ZyiZly2}
\zx G Zyi } ,
{£ У1 * 1У2 | y 2 G ZyiZl } ,
, . . . , {^s/!*!...^*,, I ^n 6 ^ y i Z! ...?/„}
такие, что в G истинна дизъюнкция fc+i
V*„ e ^...*„-, y„ И Д*) = яvw(A,x) = -E), rAeX^XyuZl...Xyn,Zn. ДОКАЗАТЕЛЬСТВО замечания З практически повторяет доказа тельство замечания 2. Замечания 2 и 3 выражают некоторое подобие
498
Ю. В. Нагребецкая
"дистрибутивностимквантора V относительно дизъюнкции. Сформулиру ем обобщение леммы 7 в контексте замечания 3. Л Е М М А 8. Пусть А G [GjL(3,Z)]n, Z — бесконечное множество целых чисел, izvi
I Vi € Z} ,
{ZyxZl | zx G Zyi} ,
{ZyiZlU2 | г/2 €
ZVlZl},...,
l ^ i / l * l — ! / n - i * n - i i / n I У" £ ^ y i 2 i . . . y n - l * n - l J ' 1^/1*1—Уп-1*п-1Уп2п
I г « ^ ^y\Z\'~yn)
~~
совокупности бесконечных множеств целых чисел, ф(а,х) ^ (ui(a)vi{x) .. .uk(a)vk(x)
= 1),
u; G ^(a), г^ G ^(ж), ж = «i .. .ж„. Тогда [G h Vyx G ZV^x € Z w .. ,Vy n G 2T wai ...,„., V Zn G ^у121...г„_гуп
г
n+l mt + l где ф(а,х) ^ Д V w tJ (a, ж) = 1, г=1 j - i
«,<,•(*, 5) ^ ^(ФГЧ*) . . . О Я ) ! » * ) . Покажем, что G |= i/ тогда и только тогда, когда для любого i G G { 1 , . . . , п} существует ji G { 1 , . . . , га,}, для которого в £Г(х) выполняется
v^\g)...v^f{g)
= l.
(6)
499
О разрешимости теорий первого порядка, Заметим вначале, что в силу полноты элементарной теории EG n-j-1
[G \= и] <=>
m; + l
За Д V£ \l
Wij(a, х) — 1
Пусть G |= */, т. е. существует кортеж Л Е [GL(3,Z)] n такой, что для любого i истинно в G предложение т.Ч-1
Vf \ / Wij(A,x) = 1. Применяя последовательно сначала замечание 3, а затем лемму 8, прихо дим к выводу, что найдется ji £ { 1 , . . . , га}, для которого в 'J(x) справедли во равенство (6). Обратно, пусть для любого i £ { 1 , . . . , п) при некотором ji £ { ! , . . . , г а J в *J(x) истинно равенство (б). Взяв в качестве а кортеж (JE7, . . . , £ ' ) , имеем G (= v. Поскольку проблема равенства слов в свободной группе Э'(х) разрешима, то разрешима и теория 3V Л VG. Для доказательства теоремы осталось показать разрешимость тео рии 3V Л VM. Установим сначала разрешимость теории 3V Л М. Пусть _ /r+1 ^ ^ \ IX ^± За Уж I Д ф8(а, х) I — предложение языка 3VA сигнатуры (-,1), где
= fia)(5)wis\x).. . / ^ ( ^ ( ^ / ^ ( а ) , а ~- a.i . . . а „ , ж = #1...ж п , иу, f>s) £ Э\М(а), v;3\wi' в)
вЭТУС(а)имеем «} ф 1, / / имеем v>*' ^ !» ^
7^ *»
£ 3\М(ж), причем
s)
/ 1, i € { 2 , . . . , k8}, j * E { 2 , . . . , / J , в ЭЖ(х)
г
6 {ij---»**}? J € { 1 , . . . , / , } . Для каждого
s £ { 1 , . . . , г} введем подмножества L5 и i?5 множества { 1 , . . . , п} следую щим способом: L8 — множество тех и только тех индексов i £ { 1 , . . . , п}, для которых буква щ присутствует в слове и^ (а) .. . u£/ + 1 (a), Rs — мно жество тех и только тех индексов j £ { 1 , . . . , п } , для которых буква dj присутствует в слове / j W ( a ) . . • ///+! (2). Ясно, что L e и Д 5 строятся по предложению // алгоритмически. Теперь
опишем
некоторую
рекуррентную
последовательность
500
Ю. В. Нагребецшя
{Qd}d=zo подмножеств множества { 1 , . . . , п}, возрастающую по включению:
£о^0,
*?
(J
L,)u(
(J
se {l,...,r},
s€ {l,...,r},
R s С Qd
Ls С £d
Rs).
Заметим, что если Qd+i = Qd для некоторого d, то Qd = £ d ' для любого d ^ d. Поскольку ^ С £^+1 и | ^ | ^ ?г для любого d Е u>, то {#
<р -
Л
( ^ (*)••• 4s? (*) = *!в) (*)... Ч 8 ) (*))
s€{l,...,r}, Х5 С X), л 5 С Е
равенств в свободном моноиде fJM(x). Действительно, пусть М (= /i, т. е. существует набор А Е [M£(3,Z)] n , для которого
Сначала покажем индукцией по d, что {Ai \ г Е Qd} С GL(3, Z). Б а з а и н д у к ц и и (d = 0) выполняется очевидным образом. Ш а г и н д у к ц и и . Если г 0 Qd, то по определению множества g<j без ограничения общности можно считать, что i £ Ls для некоторого s Е { 1 , . . . , п } и при этом Rs С ^ - Подсчитаем определители матриц, представляющих собою левую и правую части равенства ^>S(A, Е,...,
Е).
Поскольку Rs С Qd и Qd С Т>^ то по определению множества R8 и матриц A i , . . . , Ап определитель справа равен 1, и, значит, det Aa Е {±1}- Мы до казали, что А{ Е GL(3,Z), следовательно, {А;|г Е Qd+i} С GL(3,Z). Мы выбрали do E CJ так, что ^ 0 — Е, поэтому {А,- | г Е Е} С GL(3, Z). Возьмем произвольное s Е { 1 , . . . , п}. Если L s С Е , Л в С Е, то для любого
501
О разрешимости теорий первого порядка
% G { 1 , . . . , п}, если буква а; входит в левую часть равенства ф8(3, х) или в правую его часть, выполняется А{ G C?L(3,Z). Следовательно,
*€{1,...,г}, Х5 С S, Л5 С Е
х O&w)" 1 («?>(*>)"' (ji->M)"'... (-i-'й)"1 х (4"ю)" = i) • Из доказательства разрешимости теории 3V Л УС следует, что 1
V\*\x)...v^(x)(w\?(x)y\..(w[*\x)y
=l
в ?(*)
для всех тех s G { 1 , . . . , г } , для которых L8 С Е, J?s С Е. Отсюда v\s\x)
. . . v£ (а?) = w[*\x) .. . г^*j (#) в ЗГМ(ж). Пусть теперь М (= <р. По
ложим Лг ^=± ХЕ(г') Д л я каждого г 6 { 1 , . . . , п } . Зафиксируем некоторое 5 G { 1 , . . . , п} и рассмотрим три возможных случая. (а) Пусть Ls £ Е, Rs £ E, тогда существуют г0 G 1 Д Е , j
0
€ ЯДЕ.
По определению L s и Д 5 , а также в силу выбора А,-, г €• { 1 , . . . , п}, левая и правая части равенства являются нулевыми матрицами. Получается, что
М^\/хф3(А}х) (б) Пусть теперь Ls С Е, тогда Rs С £^+1 = 2 . В силу выбора А для любых i е { 1 , . . . , А?в + 1}, i G { 1 , . . . , / , + 1} имеем u\s)(A) = w f ^ A ) . В 3\М(ж) справедливо t , W ( f ) . . . t , W ( f ) = u,S*> ( Я ) . . . « , « ( * ) .
Следовательно, М f= Чхф8(А, ж). (в) Пусть наконец й в С Е. Тогда аналогично случаю (б) получаем требуемое. Таким образом, теория 3V Л М разрешима, ибо проблема равенства слов в свободном моноиде конечного ранга разрешима. Завершим доказательство разрешимости теории 3V Л VM.
(
Я+1 r , + l
\
V Л ^*»*(^»^0 1 "~ произвольное предложение языка 3V Л V сигнатуры (-,!), где a = a i . . . a n , ж = xx .. ,хп и -0* t ~
502
Ю. В. Нагребецкая
атомарная формула. Значит, ^.,«(3,2) ^ «(1',f)(S)«[e,*)(f) .
..u(ks^(a)v(ks^(x)u[s]t+1(a)
= /}^)(3)^)(^..j,(;f)(3)
t£{l,...,q}
S
алгоритмически построим множества L« , й« и ЕМ так, как при доказа тельстве разрешимости теории 3V Л М. После этого покажем, что M | = / i тогда и только тогда, когда истинно предложение
V^ytt,
б^
где
(S(8,t) (*) • • • «£? («) = «1',е) (*)-. «ft? (*)) •
Л s € {1,...,г*}, £
, д<'> с Е<*>
Конъюнкты предложений £ ь t е { 1 , . . . , д}, представляют собой ра венства в 3~М(х). Тем самым разрешимость теории 3V Л VM будет доказа на, ибо, как уже отмечалось, проблема равенства слов в свободном моноиде конечного ранга разрешима. Пусть истинно предложение rj. Это значит, что для некоторого t* истинно £**• Используя доказательство разрешимости теории 3V Л М, по лучаем rt.+l
М \=3а\/х
Д
ip9}U(a,x),
5= 1
следовательно, М \= /х. Пусть теперь М \= /л. Отметим вначале, что для моноида М справед лив аналог замечания 3, демонстрирующий некоторую "дистрибутивность"
О разрешимости теорий первого порядка
503
квантора V относительно дизъюнкции: существуют бесконечное множество Z целых чисел, а также совокупности бесконечных множеств целых чисел {Zm | yi € Z} ,
{Zyi Zl | z\ E Zyi} ,
{ZyiZl
такие, что в М истинна дизъюнкция Ф^У^Ухе
7Nzx 6Zyi..
.Vyn Е ^ . . . ^
rt + l
Л ^е(АД),
V*„E
где X ;=± XyiiZl .. -XyrifZn. Из истинности в М формулы У> следует истин ность в М формулы q+l Ф' ^
\ / f=l
V2/l
G Z V
V^EZyi2l..,n„iyn
^
G
^ W • ' 'V ^ *
G
Д
#Vi*i...*n-l
ф9М^У
se { i , . . . , r t } , #i° С Е(<) Повторяя рассуждения, приводимые при доказательстве разреши мости теории 3V Л М, получаем, что найдется t* E { 1 , . . . , # } такое, что {А{ | i G S<**>} C G I ( 3 , Z ) . Значит, имеют место условия леммы 8. Поэто му для каждого $ E { l , . . . , r u } такого, что L^
С Е<**) и Д ^ С Е(£*),
выполняется равенство
v\^(x)..4t}w H'i^*))"1 • • • К,м(-))_1=i в ад. которое равносильно равенству
Тогда предложение г) истинно. Разрешимость теории 3V Л VM, а вместе с ней и теорема доказаны.
504
Ю. В. Н&гребецкая Автор) искренне благодарит Ю. М. Важенина за постановку задачи
и большую помощь при подготовке статьи.
ЛИТЕРАТУРА 1. А. И. Мальцев, Об элементарных свойствах линейных групп, в кн. "Неко торые проблемы математики и механики", Новосибирск, АН СССР, Сиб. отделение, 1961, 110—132. 2. Ю. В. Матиясевии,
Диофантовость перечислимых множеств, Докл. АН
СССР, 191, N 2 (1970), 279-282. 3. А. И. Слободской, Универсальная теория группы GZ(3,Z), в кн. "Алгорит мические вопросы алгебраических систем и ЭВМ", Иркутск, Иркутск, гос. ун-т, 1979, 200-217. 4. Ю. М.Важенин,
Критические теории, Сиб. матем. ж., 29, N 1 (1996), 23—
31. 5. Ю. М. Ваоюенин, В. Ю. Попов, Критические теории свободных нильпотентных колец некоторых типов, Изв. вузов. Математика, 1991, N 3, 74—76. 6. Ю. М. Ваоюенин, Алгоритмические проблемы и иерархии языков первого порядка, Алгебра и логика, 26, N 4 (1987), 419—434. 7. Ю. М. Ваоюенин, Ю. В. Нагребецкая, О границах разрешимости колец це лочисленных матриц, в кн. "Международная алгебраическая конференция, посвященная памяти Д. К. Фаддеева", тезисы, СПб., 1997, 178. 8. В. Магнус, А.Каррас, Д. Солитэр. Комбинаторная теория групп, М., Нау ка, 1974. 9. М. И. Каргаполов, Ю. М. Мерзляков. Основы теории групп, М., Наука, 1982. 10. А. Г. Курош, Курс высшей алгебры, М., Наука, 1968. Адрес автора: НАГРЕБЕЦКАЯ Юлия Вацлавовна, РОССИЯ, 620075, г. Екатеринбург, Уральский государственный университет, кафедра алгебры и дискретной математики. e-mail: [email protected]
Поступило 19 ноября 1997 г. Окончательный вариант 27 августа 1999 г.
