1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 62
Текст из файла (страница 62)
Ао ~=/= eJ.iErИтак,(8.5)В силу (8.6) ЭТО равносильно rolrl=/= eJ,для одноэлементных Ао доказано.J,;;;i,;;;nЗаметим, что функцияiErr<:;;{l, ... ,n}аддитивна по Хо, т. е. если Ао = АЬ U А5 и АЬ n А5 = eJ, то F(Ao, А1, .... .. , Ап) = F(Ab, А1, ... , Ап) + F(A5, А1, ... , Ап). Из справедливости(8.5)для одноэлементного Ао и аддитивностиF(Ao, А1, ... , Ап) = F( Ао \FполучаемпUAi,A1, ... , Ап ).(8.7)i=lТак какF( Ао \iQI Ai, А1, ... , Ап) = IAo \ iQI Ail, то (8.5) выполне-но для любого конечного Ао.DФормула вида :3х1 ... :3хп8, гдемул,называетсяпозитивно8 -конъюнкция атомарных форпримитивной формулой.абелевых групп мы называем сигнатуру :Е+=ются двухместной и одноместной операциями, ОПредложение8.4.4.Пусть Ф(х1,ная формула сигнатуры :Е+ и А-...
, хп) -Сигнатурой(+,-,О), где-+, -являконстантой.позитивно примитивабелева группа. Тогда:а) Ф(х 1 , •.• , хп) определяет подгруппу в декартовой степени лпгруппы А, т. е. множество{ (а 1, ... , ап)1А F Ф (а 1, ... , ап), а 1, ... , ап Енепусто и замкнуто относительно операций+иА}-в системелп;б) для любогоl ~ 1 и любых а1, ... , ап Е А формула Ф(х1, .... . . , Xz-1, а1, ... , ап) либо не выполняется в А, либо определяетв л 1 - 1 смежный класс по подгруппе, определяемой в л 1 - 1 позитивно примитивной формулой Ф(х1,...
, Xz-1, О, ... , О).До к а за тел ь ст в о сразу следует из выполнимости в А свойствt(O, ... , О) =О иРазрешимые теории абелевых групп§ 8.4.315для любого терма t(x1, ... , Хп) сигнатуры Е+ и любых а1, ... , ап, Ь1, ...... ,ЬпЕ А.DЕсли Ф1 (х), Ф2(х)позитивно примитивные формулы сигнату-ры Е+, А - абелева группа, то через [Ф1: Ф2, А] будем обозначатьиндекс [Н1: Н2], где Hi - подгруппа Фi(А) определяемая в А формулойФi(х).Будем говорить, что абелева группа А имеет разрешимую проблему элементарных индексов, если существует алгоритм, который полюбым позитивно примитивным формулам Ф(х), Ф(х) сигнатуры Е+ илюбому п Е w определяет, выполняется ли условие [Ф: Ф, А] ~ п.Будем называть формулу Ф булевой комбинацией формул множества Х, если Ф получается из формул множества Х с помощью связокл,v,- и~.ЛеммаПусть8.4.5.А-абелевагруппа.Ф(х1, ...
, хп) сигнатуры Е+ эквивалентна вции Ф* (х1,ЛюбаяформулаTh(A) булевой комбина... , хп) позитивно примитивных формул. При этом еслив А разрешима проблема элементарных индексов, то существуеталгоритм, дающий по Ф формулу Ф*.До к аз ат ел ь ст в опроводитсяв Ф. В силу эквивалентностейФ= 'v'x(81 V ... V 8п),где8i, iЕ§ 4.2индукцией почислу кванторовдостаточно рассмотреть случай{ 1, ... , п }, -позитивно примитивныеформулы или их отрицания. Так как дизъюнкция отрицаний позитивнопримитивных формул эквивалентна отрицанию одной позитивно примитивной формулы, то, добавив, если нужно, тождественно ложнуюформулу ~:3х х ~ х, можно считать, что Фгде Фi,i~ п,= 'v'хСФо V Ф1 V ...
V Фп),позитивно примитивные формулы. Так как 'v'х~Фо-эквивалентна отрицанию позитивно примитивной формулы, то можносчитать п>О. Итак, достаточно рассмотреть случай, когда Ф есть'v'х(Фо(х, х1, ... , Хп)-* (Ф1 (х, Х1, ... , Хп) V ... V Фп(х,ПустьBi, i~ п,подгруппы группы А, определенные соответственно-формулами Фi(х, О,8.4.4... , О), i~ п. В силу леммыможно считать, что [Во:и предложениюXJ, ... , Хп))).8.4.4, б)Bi]8.4.2 и предложения{ 1, ... , п }. По лемме 8.4.1, в)А и а ~ { 1, ... , п} позитивно~ п!, i Едля Ь1, ...
, Ьп Епримитивная формулаФо(х, Ь1, ... , Ьп) Л Л Фi(х, Ь1, ... , Ьп)iEaГл.316Разрешимые и неразрешимые теории8.определяет в А либо пустое множество, либо множество, содержащееп( а) = [во n _П Д: В*] классов смежности по подгруппе В* = Во nn ... n Вп.iEaРассмотрим множествоV = {sls<:;;;Р({1, ... ,п}), ~)-l)lal. п(а) =О}·aESДля любогоS <:;;;Р( { 1,... , п}) определим формулуФ 8 (х1, ...
,хп) = ( Л :3х Л Фi(Х,ХJ, ... ,хп)).!\aESiEaU{O}.!\ (Л ~:3х Л Фi(Х,ХJ, ... ,хп)).aE{l, ... ,n}arf_SПолемме8.4.3илеммевалентна в Th(A) формулеV8.4.lв)iEaU{O}формулаФ(х1,... ,хп)эквиV Ф 8 (х1, ... , хп)- Заменяя в формулеSEV:3х 1\ Фi на эквивалентные им позитивноФ 8 (х1, ... , Хп) формулыSEViEaпримитивные формулы, получим требуемую Ф*.Ясно, что позитивно примитивные формулы Фо,...
, Фпэффективнонаходятся по Ф, и если в А разрешима проблема элементарных индексов, то по Фо,... , Фпэффективно находится множествоV,а значит,и формула Ф*.ОДля позитивно примитивных формул Ф(х), Ф(х) и натуральногочисла п>О через [Ф: Ф] ;;::п будем обозначать предложениеАр:3х1.,.:3хп( Л Ф(xi).i\ Л ~Ф(xi-Xj)).l,;;;i,;;;nСледствие8.4.6.l,;;;i<j,;;;nДля того чтобы элементарная теорияTh(A)абелевой группы А была разрешимой, необходимо и достаточно,чтобы в А была разрешима проблема элементарных индексов.До к аз ат ел ь ст в о.Необходимость вытекает из того, что условие [Ф: Ф, А];;:: п равносильно истинности в группе А предложения[Ф: Ф] ;;:: п.
Так как в любой абелевой группе истинно t(O, О, ... , О) ~ Одля любого терма t(x1, ... , хп) сигнатуры 1;+, то любое позитивнопримитивное предложение истинно в любой абелевой группе. ПоэтомуРазрешимые теории абелевых групп§ 8.4.317существует алгоритм, определяющий для любой булевой комбинациипозитивно примитивных предложений Ф*, истинно или ложно Ф* в А.Отсюда по лемме8.4.5вытекает достаточность.DЭлементарную теорию класса всех абелевых групп в дальнейшембудем обозначать через АГ.Лемма 8.4.7.
Любая позитивно примитивная формула Ф(v1, .... . . , vn) сигнатуры :Е+ эквивалентна относительно теории АГ конъпkЕ w и рпLюнкции формул вида :3vomivi ~ pkvo иi=ILmivi ~ О, где mi ЕZ,i=Iпростое число. При этом такая конъюнкция находится-эффективно.До к а за тел ь ст в о. Пусть даны матрицынадТогда черезZ.(N, М)будем обозначать позитивно примитивнуюформулу :3vn+I ... :3vn+k0, гдеn11Vn+Iесть конъюнкция равенств системы0+ ...
+I:n1kVn+km1sVs,1,;;;s,;;;n(8.8)nt1Vn+IПусть даны+ ... +Nи М перестановкой i-й и j-й строк или умножениемэлементов i-й строки на целое числовалентна формуле(N', М)mtsVs·l,s;;s,;;;ni,j Е {1, ... , t}. Ясно, что если N' и М' получаются соответственно изчто еслиI:ntkVn+kN'(N, М).k -1=О, то формула(N', М')Из коммутативности операцииполучается изэкви+ вытекает,перестановкой столбцов, то формулаNэквивалентна относительно АГ формуле(N, М).
Ясно также,{1, ... , t}, i -1= j, и k Е Z, то формула (N', М')эквивалентна в АГ формуле (N, М) где N' и М' получаются из N и Мзаменой элементов nil и mis (l Е {1, ... , k}, s Е {1, ... ,п}) на nil + knjlчто если даны i,j Еи mis+ kmjsиZ.kЕсоответственно. Пусть теперь даны i, j Е { 1, ... , k}, i -1= j,Рассмотрим системуS,полученную из(8.8)+заменой чиселnli, ... , nti соответственно на числа n1ikn1j, ... , пи+ kntj· Ясно,что для любой абелевой группы А, если набор (Ь1, ... , Ьk, а1, ... , ап)является решением в А системы(Ь1,...
, Ьj-1, Ьj(8.8),то набор- kbi, Ьj+I, ... , ьk, а1, ... , ап)Гл.3188.Разрешимые и неразрешимые теориибудет решением в А системыS,в А системы(Ь1,... , Ьj-1, Ьjрешение в А системы-лучается изn1iS,и если (Ь1,... , bk, а1, ... , ап) -+ kbi, Ьн1, ... , bk, а1, ... , ап)(8.8). Таким образом, если матрица N' позаменой элементов nli, ... , nti соответственно на числаN+ kn1j, . .. , nti + kntj, то формула (N', М)но теории АГ формулеэквивалентна относитель(N, М).С помощью описанных выше преобразований матрицжем эффективно найти такие матрицыэквивалентна формулеА=(D,О),решениетоD -(N*, М*),N*а матрицаN*имеет виддиагональная или пустая матрица, а Опустая матрица. Из вида матрицыN*и М мы моNи М*, что формула(N, М)( ~),где- нулевая илиполучаем, что формула(N*, М*)пэквивалентна конъюнкции формул видапZ:: mivi ::::::: kvo:3voпри k-1-О иi=IпL mivi ::::::: О.
Так как формула :3vo Z:: mivi ::::::: vo эквивалентна в АГ фopi=Iмуле О::::i=IО, то для завершения доказательства леммы достаточно замептить, что формула:3voZ:: mivi ::::::: kvoпри k (/:. {О,i=Iсительно АГ конъюнкции формулр1, ... , Pr-:3voпэквивалентна отноkZ:: mivi ::::::: р/ vo, j Е { 1, ... , r }, гдеi=Iпопарно различные простые числа,натуральные числа и kl}kj -положительные= р~' ... p~r. Для доказательства последнегоутверждения предположим, что для некоторой абелевой группы А иэлементов а1,... , ar, ЬЕ А мы имеем_ pk2a __ pkra_ ЬPk'a1 1 - 2 2 - ... r r- ·об означимчерез.
{1, ... ,r,}Следствие8.4.8.i Еk1Теориячисла р 1k,_,k;+lkтpi-l ·Рн~ ···Prr· аккак наибольший общий делитель чисел n1, ... , nr равен 1, то найдутсятакие числа l 1, ... , lr, что n1 l 1 + ... + nrlr = l. Тогда для элемента с =D= l1a1 + ... + lrar мы имеем kc = Ь.ni,Th( (Q, +,-,О))•••сложения рациональныхчисел разрешима.До к аз ат ель ст в о.
Ясно, что формулы вида :3у пх ::::::: pky опреQ = (Q, +,-,О) всю группу Q, а формулы вида пх ::::::: О -деляют внулевую подгруппу. Применяя лемму8.4.7и следствиетребуемое утверждение.Следствиеразрешима.8.4.9.Теория8.4.6,получаемDTh( (Z, +,-,О))сложения целых чисел§ 8.4.Разрешимые теории абелевых группДо к аз ат ель ст в о. Ясно, что формула :3у пх ::::::относительно То= Th( (Z, +,-,О))[п,эквивалентнаkyk:::::: -(- ) у,а конъ-п, kпу эквивалентна относительно То формулеюнкция :3у х :::::::3у хформуле :3у х319ky Л :3у х ::::::k]y, где (п, k) -наибольший общий делитель, а [п,k] n, k.
Ясно, что индекс б = [:3у х ::::::т:::::: ky: :3ух:::::: my,Z], где Z = (Z,+,-,0), равен (т,k)' если m -j. О::::::наименьшее общее кратное чиселиk -1-О. Еслиk =О, то б= 1. Если k -1- О и m = О, то б = оо.8.4.7, Z имеет разрешимую проблемуследствию 8.4.6 получаем разрешимостьСледовательно, в силу леммыэлементарных индексов. Потеории То.ОНаша следующая цель-показать разрешимость теории АГ классавсех абелевых групп (сигнатуры~+ = (+,-,О)).Важную роль в этомдоказательстве играют инварианты, введенные В.
Шмелевой. В дальнейшем под группой мы будем подразумевать абелеву группу.Пусть А{kaЕсли р-группа. Напомним, что через-I а Е А},а черезA[k]kAобозначается подгруппамы обозначаем подгруппу {а Е Апростое число и рА= О,тоdim АI ka = О}.обозначает размерностьгруппы А, рассматриваемой как векторное пространство над полем изр элементов.
В дальнейшем через р ичисла, а черезn, k, т, s -qбудут обозначаться простыенатуральные числа. Следующие числа дляпроизвольных р и п будем называть инвариантами Шмелевой группы А:ар,п(А)= min{ dim((pn A)[p]/(pn+I А)(р]), w},= min{inf{ dim(pn А)(р] 1 n Е w }, w },rp(A) = min{inf{dim((A/A(pn])/p(A/A(pn])) 1 п Е w},w},с(А)Е{О, 1} и с(А)=О {:} (nA={O} для некоторого nEw, n-f.O)./3р(А)Мы будем говорить, что у абелевых групп А1 и А2 совпадают инварианты Шмелевой (обозначаеми п выполнено ар,п(А1)и с(А1) = с(А2).Обозначим через~+,=Sh(A1) = Sh(A2)), если для любых р= /3р(А2), rp(A1) = rp(A2)ар,п(А2), /3р(А1)ap,n,k, /3p,n,k, rp,n,kи Еп предложения сигнатурыистинности которых в группе А равносильны соответственно условиям:а)б)в)dim((pn А)[р]/(рп+I А)(р]) ~ k;dim(pnA)(p] ~ k;dim((A/A[pn])/p(A/A[pn])) ~ k;г) пА={О}.Следующая теорема дает классификацию полных расширений теории АГ.Гл.320ТеоремаРазрешимые и неразрешимые теории8.8.4.10.Следующие условия для любых абелевых группА, и А2 равносильны:1)у А, и А2 совпадают элементарные индексы, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
