1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 67
Текст из файла (страница 67)
ry) Е LEq так:Пусть М1,все попарно различные классы Т/I -эквивалент•... , Mk -N =ных элементов из М. Пустьзададим навие MiNМU {ао, ... , ak}, ai 1:-М, i ~k;линейный порядок ~ так, чтобы было выполнено усло= {а I а= 1, ... , k; отношение эквива{ао, ... , ak} образует один классЕ М, ai-1 ~а~ ai},• iлентности Т/ наNзадаем так, чтоrу-эквивалентных элементов, а ограничение Т/ на М совпадает с Т/О·ПолагаемQl(x, у)=~ТJ(Х, у);SВ(х,у1,У2) =у, ~у2/\У2 ~у1;<to(x,y1,Y2)f1(x,y,,y2)= ТJ(У1,У2);= Vu(ry(x,u)-+Тогда легко проверить, что Ql, SВ,(и~ YI +-+и~ У2)).<to, '1:1 определяют 9Л в !J'l, когдав качестве значения параметра х взято ао.
ОтсюдаПредложение8.6.tt.КлассL2Eq2~REDLEq.Dвсех конечных моделей теории Т2двух линейных порядков (сигнатура (~о.~,)) имеет наследственнонеразрешимую теорию.Покажем, чтоLEq ~RED L2.по 9Л алгебраическую системуПусть М1,... , Mk -элементов из М. Пусть= (М, ~. rJ)= (N, ~о, ~1) Е L2Пусть 9Л!J1ЕLEq;определимтак:все попарно различные классы rу-эквивалентныхN= М U {ао, ... , ak},Iai 1:- М, и ~ 1-линейныйпорядок на N такой, что Mi = {а а ЕМ, ai-1 ~, а~, ai}, i = 1, ... , k.Линейный порядок ~о на N таков, что любой элемент из {ао, ... , ak}меньше любого элемента из М, а на М порядок ~о совпадает сПусть Ь-наименьший элемент в М относительно порядка~-~-ПолагаемQl(x, у)SВ(х, YI, У2)=х= YI<to(x, YI, У2)f1(x,Y1,Y2)~о у;~о У2 /\ У2 ~о YI;=YI ~о у2;= Уи((и ~ох/\ ~(х ~о и))-+ (и~,У1 +-+и~, у2)).Если в качестве значения параметра х взять элемент Ь, то Ql, SВ,<to, '1:1относительно элементарно.
определяют 9Л вИ~REDLEqL2.!J'l,следовательно,0§ 8.6. Неразрешимые теорииПредложениеКласс8.6.12.341всех конечных симметрическихSymгрупп имеет наследственно неразрешимую теорию.Докажем это, установив, чтоделим вотносительно элементарно опреECI2Sym.Пусть 9Л = (М, rJo, rJ1) Е Eq2, и предположим, что JMJ ~ 3. Пустьто, ... , mk - все различные элементы из М, а SJ1 = Sym(M) - группавсех перестановок множества М.Возьмем ао=(то, т1), а1=так, что циклы подстановок а2элементовrJoиry 1соответственно.Рассмотрим множествоа=aSи Ь=(то, m2) Е N; а2 и аз выбираем в SJ1и аз отвечают классам эквивалентных= {(а, Ь)LJсуществуета?}, Нетрудно проверить, чтоh Е N такой, чтоL состоит из всех партранспозиций, имеющих общий элемент.Сопоставим паре (а, Ь) ЕL элемент ср(а, Ь) Е М, являющийся обm2)) = то.Заметим, что отношение эквивалентности "' на L, определенное отображением ер (т.е. (а,Ь)"' (c,d) <::===} ср(а,Ь) = cp(c,d)), может бытьщим элементом транспозиции: например, ср((то, т1), (то,определено и так:(а, Ь)"' (с, d)<::===}Vh(ah =а--+ (сЬh)ЗЗаметим, что если (а, Ь) Е L, т(где zh= ср(а, Ь),= (dbh)З = е).h Е N, то cp(ah, bh)= h(m)= h- 1zh).Определим наho ~ h1Sym(M)<:====}Единица е группыVmSJ1отношение частичного порядка ~ так:Е M(ho(m)= т V ho(m) = h1 (m)).является наименьшим элементом; минимальными элементами множестваN \ { е}являются в точности циклическиеподстановки.СкаждымношениеэлементомэквивалентностиhrJhЕNможносвязатьнаМ:= {(m, m)rJhследующееJотm Е М} UU {(mo,m1) mo,m1 Е М, существует минимальный элемент hoв N \ {е} такой, что ho ~ h и ho(mo) -1- то, ho(m1) -1- m1}.Из выбора элементов а2, аз следует, что rJa 2 = rJo, rJa 3 = 'Г/1 ·JЗапишем теперь следующие формулы в языке теории групп:2t(x1, х2, Хз, Х4, У1, у2) = 3z(y1 ~ z- 1x1 z 1\ У2 ~ z- 1x2z);SВ(х, YI, У2, Уз, у4) = Vh(h- 1y1h ~ YI--+ (узh- 1 у2h)з ~ (y4h- 1 y2h)з ~ е);(ц)(х, У1, У2, Уз, у4)= 3z(z~ хз 1\ ~z ~ е 1\ Vu(u ~ z--+ (и~ еV и~ z))ЛЛ(S:В(х, YI, У2, Уз, У4) V ('S:В(х, YI, У2, Yi, УЛ(\ ~sв(х, УЗ, У4, Уз, y,f)))),342гдеГл.z8.Разрешимые и неразрешимые теории~ х означает\fy1\fy2(Qt(x, YI, у2)<!:1(х,у1,У2,Уз,у4)-t~(х, YI, У2, Yi, yz)V ~(х, Yi,Y2, Yi, У2));= 3z(z ~ Х4 Л ~z ~ е Л \fu(u ~ z - t (и~ е V и~ z))ЛЛ(~(х, YI, У2, Уз, У4)V Г~(х, YI, У2, Yi, У2) Л ~~(х, Уз, YI, Уз, y.f)))).Если «параметрам~ х1, х2, хз, Х4 приписать значения ао, а1, а2, аз соответственно, то формула Qt определит множествоотношение"', а <!:о и <!:1 определят наL/ "'L;~ задает наLотношения эквивалентности 'Р- 1 (110) и tp- 1(171) соответственно.
Проведенное рассмотрение ипоказывает, что формулы Qt, ~. <!:о,деляют классСледствиеEq2в<!:1относительно элементарно опреОSym.8.6.13.Класс конечных групп имеет наследственнонеразрешимую теорию.Следствие8.6.14.Класс всех групп имеет наследственно неразрешимую теорию.Другие примеры разрешимых и неразрешимых теорий приведеныв обзоре: Ершов Ю.
Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А.Элементарные теорииNo4.//Успехи математических наук.- 1965. -Т.20,С.37-108. В этом обзоре, в частности, отмечено, что исчислениепредикатов для сигнатуры одной одноместной функцииразрешимо,а если сигнатура а содержит по крайней мере два одноместных функциональных символа, то исчисление предикатов сигнатуры а неразрешимо.Предметный указательАГБуква алфавита317Автоморфизм95-Аксиома68330- - атомная- - всех подмножеств 68- комбинация 301, 315- сложность формулы 217Вершинаатомная- переменной- - свободное l 02- - связанное 102- подслова 15- секвенции I1 в деревеквенции I2 217- секвенции в дерево 24- символа в формулу- - отрицательное 169- - положительное 169- слова первое 15- - последнее 156868330всех подмножеств6894Алгебраическая система-и-насыщенная181165насыщенная 178ограниченная 198однородная 176универсальная 178каноническаяАлгебраические системы изоморф-ные-14ивисчисления17исчисленияG 215LG 5419Арифметикасеквенции в деревеГомоморфизмГраньнатуральных чисел9716Атом булевой алгебрыБазис для системы182525Главная формула правила21697Ассоциативность13Высказывание-исчисленияАнтецедент25 l- в ипf 136- в ИВ1 47Высота дерева-Буква144llне применимый к объекту--выше се-мулэлементарно эквивалентныеАлфавит15Вывод формулы из множества фор-95Алгоритм335Вхождение буквы в словоАлгебра булева- - -15Булева алгебра22-ИПI; 114- ипf 135- ипч 140- выбора 70, 90- исчисления 17- исчисления G 215- регулярности 81- экстенсиональности 60Аксиомы булевых алгебр14входящая в слово7818994верхняя 65- - наименьшая 65- нижняя 65- - наибольшая 66Граф 97, 335График 16Группа 97- р- делимая 32 l216Предметный указатель344Значение алгоритма на объектеГруппа абелева-97325подстановок 97базиснаяД.
н. ф.истинности формулы на наборе-отображения на элементе4035, 126Декартова п-степень множествасемейства множествсистемив1673, 95- частичный 144- - конечный 145Импликация 19Изоморфизм24- вывода 25- доказательства секвенции в ИПЕ116Диагональ 62Диаграмма алгебраической системы150Инварианты Шмелевой-си-Дизъюнктивная нормальная форма35, 126подгруппы312312Интерпретация ИВ 38- - в булевой алгебре 75- - главная 39- переменных 100- сигнатуры в сигнатуре 14119ской системе при интерпретации- элементарная 35Дистрибутивность103161561последовательности1О- в ипf 136- в ипч 140- в виде дерева 25, 245- - в ипЕ 116- закодированное парой чисел 289- из множества предложений 289- ЛИНеЙное В ИПЕ 115- - в ив 24- формулы в ИВ1 47Дополнение элемента 66Заключение21618Замена вхождения подслова- G 215-Go 54-1514Доказательство17ИсчислениеДлина абстрактного словаправила319319Истинность формулы на алгебраичеДизъюнкциякортежасовпадающиеИндекс группы в группе-- - полная 150- множества в алгебраическойстеме 150- - полная 150-19139Идемпотентность107108Деревослова16, 64100ипч61-терма61Декартово произведение множеств-251-15-ивс-J 50ивс-.v)52высказываний (ИВ)высказываний19гильбертовскоготипа (ИВ1) 46- независимое 45- непротиворечивое 38- - по отношению к семантике 44- неразрешимое 44- полное по отношению к семантике 44- предикатов гильбертовского типа135- - сигнатуры ~ 114- - чистое 139- разрешимое 44- резольвент 245Предметный указательИсчисление резольвент для исчисЛинейные порядки, имеющие одинаковые концыления предикатов247- - пропозициональное 245Матрица35Кардинал 83Квазивывод в ИВ 1 формулы из мно-жества гипотез- секвенции в ИВ- - линейный 2648в виде дерева26Квазимноrообразие157Квазитождество 157Квантор всеобщности 101- существования 101Класс 109- алгебраическихсистем:3-аксиоматизируемый 155- - V-аксиоматизируемый 155- - V:3-аксиоматизируемый 155- - и-категоричный 183- - аксиоматизируемый 152- - замкнутый 110, 153- - категоричный в мощности 183- конечно аксиоматизируемый 154- относительно элементарно определимый 333- смежности подгруппы 312- эквивалентности 63Кольцо целых чисел 97Команда 294Комбинация булева 301, 315Коммутативность 16Композиция отношений 62Конгруэнтность 172Константа 93- логическая 19- на множестве 64Континуум 327Конъюнктивная нормальная форма35-19элементарнаяКортеж15, 613598126Машина ТьюринrаК.
н. ф.Конъюнкция345294-вычисляющая функцию-преобразующая слово а в слово (Зне применимая к слову296296переводящая слово а в слово (З295295Мера сложности формулы305Местность операции-частичнойМетаязык16функции 25330Механизм совместности164- сигнатуры ~ 164- - без равенства 167Многообразие 157Множества линейно упорядоченныеизоморфные-равномощные7380Множество 13- m-сводящееся 282- аксиом для класса 153- - исчисления 17- алгебраических систем направленное 96- - элементарно направленное 149- атомно минимальное 189- бесконечное 85- вполне упорядоченное 71- выражений исчисления 17- гипотез 47, 136- доказуемых выражений 18- замкнутое относительно операции 64- кардинально упорядоченное 72- конечное 14, 84- линейно упорядоченное 65, 97- натуральных чисел 60- предложений перечислимое 283- - полное 133- регулярное 87Предметный указатель346Множество свободных переменныхсеквенции--формулысчетное-84теорем исчислениятранзитивноенепротиворечивоенесовместноепротиворечивоечастично упорядоченноефундированноеМножество-степеньтеории65, 976817Модель множества формул-112128128128совместное 128центрированное 77- в булевой алгебре 77-112176Монотонность ф(и) 196Мощности множеств равные80Мощность алгебраической системы94-множестваН.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
