Ионсоновские теории тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Т5 О"

, .. ■" НАЦИОНАЛЬНАЯ АКАДЕМИЯ КАУК РЕСПУБЛИКИ КАЗАХСТАН

Институт теоретической и прикладной математики

На правах рукописи УДК 510.67

ЕШКЕЕВ АШЗАТ РАФХАТОВИЧ

ИОНСОНОВСКИЕ ТЕОРИИ

специальность 01.01.06. - математическая логика, алгебра и теория чу ~> п

АВТ ОРЕФЕРаТ диссертации на соискание ученой степени кандидата физико-математических наук.

Научный руководитель -доктор физико-математических наук,

профессор Мустафин Т.Г.

А Л М А Т И - 1995

Работа выполнена в Карагандинском государственном университете им. Е.А.Букетова.

Научный руководитель - доктор.' физико-математических наук, . . профессор

Т.Г.Мустафин

Официальные оппоненты доктор физико-математических наук,

профессор Е.А.Палютин, кандидат физико-математйческих наук, доцент Б.С.Байжанов

Ведущее учерввдение - .Восточно-Казахстанский государственный университет.

Защита состоится

Ч 1995 г. в

часов на

заседании специализированного совета-Д. 53.04.02' при Институте теоретической и прикладной математики HAH PK по адресу : Алматы, ул. Пушкина 125. . -

С .диссертацией мокно ознакомиться в библиотеке HAH PK по адресу : 480021 г. Алматы, ул. Пушкина, 125. Автореферат разослан " " ^ötÜ^/LJ, 1995г.

Ученый секретарь -специализированного ■ совета Д 53.04.02

доктор технических наук

.А.Н.Кэзангапов.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ _Акт'£альность_темыл_

Мы выделим два исторических направления в развитии теории моделей. В северной Америке их часто называют западной и восточной теорией моделей, тан как Тарский жил на западном побережье с -1940 г., а Робинсон - на восточном с 1967 г. до преждевременной смерти в 1975 г. Это различие давно утратило' свое географическое значение, однако полезно с математической точки зрения.

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

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

Многие специалисты в теории моделей колеблются' между восточной и западной теориями моделей. В действительности Тарский и Робинсон сделали большой вклад в оба направления. (Работы Тарского о вещественно замкнутых полях и эквациональяых классах относятся к восточной теории моделей, в то время как теорема Робинсона о непротиворечивости и его анализ бесконечно малых - к западной теории моделей.)

Как показывает история развития теории моделей оба направления развивались по разному, каждый имея свои особые понятия и методы. Несмотря на наличие некоторой традиционной

параллели, не сразу и не всегда удавалось найти общую идейную основу для переноса результатов из одного направления в другое. Особые трудности вызывают переносы из западного направления в восточное. Например, метод констант Генкина разработан в 1949г., в его восточный вариант - конечный форсинг Робинсона - лишь в 1970 г. теорема Воота, Генкина, Ори об опускании типов была доказана в 1954 - 60 годах , а ее восточный аналог - теорема Макинтайра - в 1972 г. Таким образом актуальность изучения "восточной " теории моделей становится понятной. Данная работа относится к "восточной " теории моделей, название "Ионсоновские теории" в целом отражает содержание диссертации, хотя результаты Главы 3 относятся к произвольным теориям, не обязательно йонсоновским.

__Ц§^ь_работы_1_

Описать совершенные йонсоновские теории. Получить

описание йонсоновских универсалов унаров. Найти синтаксический критерий алгебраически простой модели.

.___На^чная_новизна_1_

Все основные результаты диссертации являются новыми.

Мето2Ы_иссле5ования В работе использовались общие методы исследования теории моделей.

__Практэтеская_и_теоретэтеская_цетость_работа

Диссертация - носит теоретический характер. Полученные

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

__Апробация диссертации.

Результата докладывались на следующих конференциях : "VIII - Всесоюзная конференция по математической логике." (Новосибирск, 1984г.)

"XI - Межреспубликанская конференция по математической логике." (Казань, 1992 г.)

"Третья международная конференция по алгебре." (Красноярск, 1993 г.)

"Третий Казахско-Французский ~ коллоквиум по теории моделей." (Алматы, 1994г.)

А также результаты диссертации докладывались на научных семинарах городов Алматы и Караганда.

Публикации.

Основные результаты диссертации опубликованы в восьми работах, список которых приводится в конце автореферата.' Из них пять работ в соавторстве. Научный вклад, внесенный автором диссертации в совместные работа заключается в следующем : равное участие в получение полного описания йонсоновскшс универсалов унаров, критерия алгебраически простой модели.

Структура и обьем диссертации. Работа состоит из введения, трех глав и списка литературы, •содержащего 25 наименований. Обьем диссертации- 57 машинописных страниц.

Содержание диссертации.

Диссертация состоит из введения и трех глав. В введении дана историческая справка, а также показана' актуальность, темы рассмотренной диссертации.

Остановимся на содержании глав диссертации. ' Первая глава \ посвя'щена понятию совершенности йонсоновской теории. Введем необходимые определения. -

.Определение I.I. Теория Т называется йонсоновской, если:

1) Теория Т имеет бесконечные модели;

2) Теория Г индуктивна;

3) Теория Т обладает свойством совместного вложения (JEP)

4) Теория Т обладает свойством амальгамы.-(АР) _ ' •

Теория индуктивна, если она V 3 - аксиоматизируема. Теория Т обладает свойством совместного вложения, " если любых моделей V, В теории Т существует модель Ш теории Т и изоморфные вложения i: .41 - Ш , g: В - ТО.

Теория Т обладает свойством" амальгамы, если для . любых моделей У, !81, 32 теории Т и изоморфных вложений ft: У - St, t2: II -> !В2 существуют такие Л |- Т и изоморфные вложения g,: -» ТО,-g^: -> ТО, такие что gto fj= g^ гг.

Определение 1.2 Модель И теории Т называется Т-универса"льной, если любая модель 55 теории Т, для которой IBI ^ !А1, изоморфно вложима в II.

Определение 1.3 Модель II теории Г называется Т-однородной, если для любых моделей Ж, (Гттеории Т, для которых 35, Ет 'подмодели И, IBI = ICI < IAI , любого изоморфизма ср : !В -*®т , существует

б

автоморфизм И, продолжающий <р.

Все эти определения принадлежат йонсону. Известен следующий результат

Теорема (Морли, Boot. ) Пусть х- сильно недостижимый ■ кардинал. Т - йонсоновская теория. Тогда в мощности существует единственная с точностью до изоморфизма Т' - универсальная, Т -однородная модель.

Для произвольной йонсоновской теории Т ее Т - универсальную, Т - однородную модель, следуя Мустафину Т.Г., назовем семантичес- -кой моделью. Обозначим эту модель через . Рассмотрим элементарную теорию Th(ET). Обозначим ее через Т* , т.е. Т*= Th(®T). По определению (Мустафин Т.Г.) Г*- есть центральное пополнение (центр) йонсоновской теории Т.

Пусть *И - бесконечная алгебраическая система, Yc(H|. Система II называется насыщенной над Y, если каждый тип р € S^ ((It, реализуется в ((К, у • Система U называется насыщенной, если It насыщенна над каждым Yc It, таким, что !Y! < |1t|-

В "западном" варианте теории моделей, когда изоморфное вложение в определениях универсальной и однородной модели меняется на элементарное вложение, а также меняется определение однородной модели, верна следующая теорема:

Теорема (Морли, Boot)

Система It является насыщенной тогда и только тогда, когда она однородна и универсальна.

К сожалению в '"восточном" варианте, теории моделей Т -универсальная , Т - однородная модель не обязательно должна быть насыщенной моделью.

Следупцее определение принадлежит Мустафину Т.Г.'

Определение 1.4

Ионсоновская теория Т называется совершенной теорией, если ее семантическая модель £т , является насыщенной.

Мустафиным Т.Г. был поставлен следующий вопрос:

Описать совершенные йонсоновские теории ?

Основным результом первой главы диссертации является следующая теорема.

Теорема (Критерий совершенности )

Пусть Т - произвольная йонсоновская теория, тогда следующие условия эквивалентны:

1) Теория Т - совершенна ;

Z) Т* - является модельным пополнением

(т.е. D(T*) - модельным пополнением) теории Т.

Вторая глава посвящена йонсоновским универсалам и примитивам унаров. Дадим следующие необходимые определения.

Обозначения 2.1. 1) Если Г - семейство или вид предложений, то Тр есть следующее множество формул (ф е Т: i<p ç Г: Т >- ср) t- ф>.

2) ? есть П4и то есть v - семейство всех универсальных или экзистенциональных формул.

Определение 2.1. 1) Если Т=Ту, то Tv назовем универсалом;

2) Если T=TV, то теорию Т назовем примитивом.'

Определение 2.2. 1) Если А = а е £*, то [А,а1 обозначает подунар, порожденный подмножеством A U ta).

2) Будем писать tp^t (a,Л) = t^l(.b,A), если существует такой изоморфизм <р: 1А,а] * 1А,Ь1, что ср(с) = с, VctA, и ср(а) = Ъ.

Определение 2.3. 1 ) Если H - подунар £*, /n(a)=/i ç H, /k(a) t И для всех fe < п, то элемент h назовем входным от a в H элементом,

а число п назовем расстоянием от а до Я. В этом случае используем обозначения Л=вход{а,Н), п=р(а,Н). Будем писать р(а,Н)=ос, если /"(а) Ц Н, Уп<и.

и, если /п(а) ^ /^(а), Уп<к<ш <п,л>, эсли <я,т>=»п£п{<а1ш>: /П(а)=/п+ш(а)>

2) х(а) =

Определение 2,4. Если аеЕ*, го

А(а) ({Ьей*: /(Ь) = а)!

Определение 2.5. Множество {а, ...,а } элементов £* назовем т-петлей, если а ¿а., /(а)=а+1 для всех 1 ^ I < ] < т и /(а )=£!,.

Определение 2.6. Четверку ) назовем характеристи-

кой а* и обозначим через с Лаг (Л*), если: _

П* = (.%(а): а €

V*: о) ч (О) - ш и (оо) такое, что Чт>О,

Г й, если количество т-ивтвлъ в Я* равно й<ш, у*(я) = {

I оо, в противном случае;

ц*: П* -* ш и {оо> такое, что если аеП* и а=%(а), то р.''(а)=й(а), если й(а)<ы и ц*(а)=о>, если &(а)=!Л*'■; , (* 0, если ' (аей*: х(а)=«}! = О,

■Г'

I

s

в противном случае

Определение 2.7. Под характеристикой Char(Т) будем понимать Char(Z*).

Определение 2.8. Произвольную четверку (П,1>,ц,е) назовем ха-♦

рактэристикой, если выполнены следующие условия:

1) ¡2 t П с (ш) U (ш « ш); v

2) v. ок{0} ш и Coo};'

11) in: = ш

3) \x: О - to U Ca>};

4) s e CO,»};

5) w € П «-» £=«;

6) (n,m) (Oil (ш • ш) & 0 $ k < n *> (k,m) € П';

7) v(m) > 0 (0,m) i П;

8) :n:= ш =• w e fi;

9) (n,m) еПЛ (0) » ш) (ц(п,т)= О «=» (n+1 ,m) jf 0);

10) со X Q & !fi! < ш =» Э жи <v(m) = ®) v 3 ткш.лкш ((n,m) e 0 & & ц(га,Я!) =oo);

" если 3 £,Z<u (k=max(p.(n,m): (n,m){Q,n+m2l})

. ц(ы) = о», в противном случае;

12) ц(ш) > 0.

Основнш результатом второй главы является следующая теорема. ТЕОРЕМА 1) Каждый йонсоновский универсал унаров имеет характеристику .

2) Для любой характеристики х существует йонсоновский универсал унаров, имеющий характеристику тс.

3) Два йонсоновских универсала унаров равны тогда и только тогда, когда их характеристики равны.

Во второй главе получены также результаты о свойствах центра йонсоновских универсалов унаров.

ТЕОРЕМА Пусть Т - йонсоновский универсал унаров, Т* - ее центр. Тогда

1) Т* - модельное пополнение Т.

2) Т* - допускает элиминацию кванторов ( то есть подмоделью полна).

3) Т* и-стабильна.

Следувдий результат описывает некоторые свойства примитивов и

универсалов унаров.

ТЕОРЕМА 1) Количество попарно различных йонсоновских универсалов унаров равно 2Ш.

2) Количество попарно различных максимальных йонсоновских примитивов унаров равно 2Ш.

3) Количество попарно различных максимальных йонсоновских универсалов унаров равно ш. Более того, таковыми являются в точности теории, имеющие следующие характеристики: т:ш, 1 С <т < ш ), : 1 ^ п, ш < ш ), где

1СЫ: П = {и), у(т))= 0 Упкш, ц(ш)=Г, е=«>;

V«.-- 0 = с<о»я>}- = { 2; ^

0-МО.п).....<*.»>>. V»)

' 1, если &<п-1,

если &=п-1, е = О. . О, если

4) Максимальным "/-полным йонсоновским универсалом унаров является единственная теория, имеющая характеристику % .

Третья глава диссертации посвящена изучению понятия алгебраической простоты. В "западной" теории моделей хорошо известна теорема, связанная с понятием простой модели, а именно : модель И теории Т проста тогда и только тогда, когда модель II счегна и агомна. Естественным обобщением понятия простой модели является понятие алгебраически простой модели. Напомним, -что модель теории Т называется алгебраически простой, если она изоморфно вкладывается в любую модель теории Т. Болдуин и Куекер сформулировали вопрос о наховдении подходящего понятия атомности для алгебраически простой модели. В этой главе предлагается

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

Определения 3.1 - 3.2 .принадлежат Болдуину, Куекеру.

Определение 3.1.Модель 11 теории Т называется (Г1(Г2) -атомной моделью Т , если для любого а е А существует формула cp(x)€rt такая, что:

а) Vh <р(а);

б) Tf- V х(ф(х) - ф(х)) или Г)- V х(ф(х) - ~ф(х)) для любой-формулы ф(х)?Г2 .

Определение 3.2. Модель V теории Г называется слабо (Г .Г )

- атомной моделью Т , если для любого а е А существует формула ф(х)" е Г( такая, что:

а) 1Х|- ф(а);

б) Г|- х(ф(х) - ф(х)) , ф(х)е Г2, Щ ф(а).

Легко заметить следующий факт. Пусть И - модель Т, тогда И-(Г1,Г2)

- атомная модель Т тогда и только тогда, если для любого а е А существует такая формула ф(х)еГ1 , что верно:

а) 111- ф(а);

б) ф(х) порождает • (а) .

Аналогично, если Ч1(- Т , то И - слабо (1^,1^) - атомная модель Т тогда и только тогда, если для любого аеА существует такая формула ф(х)€Г( , что верно:

а) «UJ- ф(а);

б) ф(х) порождает t^J (а).

Эти понятия, естественно, обобщаются следующим путам.

Определение' 3.3. Модель И теории Т назовем почти (Г .Г2) -атомной моделью Т , если для любого аеА существует формула

Ф(х) € Г4 такая, что:

а) <р(х) и Т совместно;

б) <р(х) порождает ^ • (а).

2 2

Определение 3.4. Модель II теории Т назовем поЗти - слабо (Г4|Г2) - атомной моделью Т , если для любого а е А существует формула ф(х) í Г4 такая, что:

а) ф(х) и Т совместно ;- .

— чг -

б) ф(х) порождает (а).

"Для удобства выражения - (Г , Г2) - атомная модель Т", "1Г

- слабо (Г>, Г2) - атомная модель Т", "К - почти - слабо (Г(, Г2)

- атомная модель Т" обозначим через (I), (2), (3), (4) соответственно. Нетрудно заметить, что справедлива следующая импликация:

Определение 3.5 I) а - типом называется любое совместное с Т множество формул, свободные переменные которых встречаются в Xй

2). а - тип р называется Г - а - типом, если реГ.

3). Г -ш - тип р называется Г4 - главным, если существует такая последовательность < (|>п(зГ): К п< ш > Г .- формул, что:

а). Т и ф(хп) совместно, 1 < п < ш;

б). Фп(хп) порождает р/ , где р/ х" -множество всех формул из р , свободжные переменные которых находятся среди (х4,... ,хп),

1 < п < ш

в). Г (- фп(Г) 3 1 < п < ы

Определение 3.6 Модель И теории Т называется хорошей последовательность элементов 11 реализует Г -главный Г2 - ш ттип.

Определение 3.7 Пусть ИЛ- модели языка первого

порядка. Тогда отображение 1: И -В называется а - вложением, если для любой формулы ср(х)еПа и любого кортежа а е А из того, что II <р(а) , следует В(- <р(Г(а). Модель II теории Т назовем а - алгебраически простой, если На- вложима в любую модель теории Т.

Нетрудно заметить, что понятия алгебраически простой модели и простой модели получаются из понятия а - алгебраически простой модели при а=0 я а=щ соответственно. Основным результатом третьей главы является следующая теорема.

Теорема Пусть Т полна для П^ [ - предложений и имеет хорошую почти-слабо 2а+1) -атомную модель. Тогда следующие

условия эквивалентны.

1). 11 - а - алгебраически простая модель Т.

2). II - хорошая почти-слабо 1, -атомная модель Т.

Определение 3.8 Модель II теории Т называется финитно почти-слабо атомной моделью Т, если для любого

а е А выполняется одно из следующих условий:

1) существует ф(х) £ Еа<.4 такая, что И |- ф(а) и ф(х) пороздает

$ (а); ^1

2) существуют к<и , ф^х), ф2(х).....Фк(х)б такие, что:

.41 -

а) каждая ф.(х) порождает 1;? (а), К1<к;

си

б) Т совместна фс(х), К1<к;

в) если ф(х)«2~ , ф(х) совместна с Т и ф(х)

41 - - -

порождает х.^ (а) , го Г|- ф(х) <-<• фь(х) для некоторого

(х)\ К1<к. ^

В связи с этим определением представляет интерес следующий результат.

Лемма . Если р^а , К - счетная финитно почти-слабо )-атомная модель Т, то II является хорошей почти-слабо - атомной моделью Т.

Полученные результаты третьей главы можно обьеденить в виде теоремы.

Теорема Для произвольной теории верно:

1) (а) » (в) - (г) ~ (д) = (е)..

2) Если Т Па^э - аксиоматизируема, то (к) => (е).

3) Если Т аксиоматизируема и полна для Па>з предложений, то (к) =» (д).

4) Если Т полна для Па^2.-предложений , то (г) => (к).

5) Если Т полна для Па<2 -предложений и имеет хорошую почти-слабо - атомную модель Т, то (г) » (к).

6) Если Т полна для Па<1- предложений и а=ш , то

(а) •» (в) <= (г) « (д) ~ (е) ® (к) где (а) - И - ) атомная модель Т.

(б) - И - слабо ) - атомная модель Т.

(в) - И - финитно почти-слабо ) -атомная модель Т.

(г) ~ II - хорошая почти-слабо 1, -атомная модель Т. >

(д) - И - почти-слабо ) -атомная модель Т.

(е) - И - почти-слабо ) -атомная модель Т.

(к) - и - а - алгебраически простая модель Т.

СПИСОК__РАБОТ__АВТОРА__ПО__ТЕМЕ__®ССЕРТАЩИ

!. Ешкеев А.Р. Совершенные йонсоновские теории. Третья Международная конференция по алгебре. Тез. докл. - Красноярск. 1993 г. .

2. Ешкеев А.Р. Алгебраически простые модельные расширения. XI-Межреспубликанская конференция по математической логике. Тез. докл. Казань 1992г.

3. Ешкеев А.Р.- О йонсоновских теориях унаров. Вторые математические чтения памяти М.Я. Суслина. Тез. докл. Саратов 1991г.

4. Ешкеев'А.Р. Мустафин Т.Г. Об а- алгебраически простых моделях. VIII- Всесоюзная конференция по математич. логике. Тез. докл. Новосибирск , 1984г.

5. Ешкеев А.Р. Мустафин Т.Г. а- Алгебраические ■ модели и некоторые виды атомных моделей теорий. В сборнике научных трудов // "Теория алгебраических структур.' Караганда. 1985г.

6. Ешкеев A.F. Мустафин Т.Г. Описание йонсоновских универсалов унаров. Сборник научных трудов // "Структурные свойства алгебраических систем". Караганда, (в печати).

7. Ешкеев А.Р., Мустафин Т.Г. Замечание к йонсоновским унарам. Международная конференция по математической логике, посвящ. 85-летию со дня рождения Мальцева А.И. Новосибирск, 1Э94 г. с. 106.

8. Ешкеев А.Р., Мустафин Т.Г. Некоторые свойства ионсоновских примитивов унаров. Сборник научных трудов //"Структурные свойства алгебраических систем". Караганда.(в печати)

Ешкеев Айбат Рафх.атулы. "Ионсондык теориялар" такырыбынан 01.01.06 "Математикалык логика, алгебра жене сандар теориясы" мамандагы бойынша физика-математика гылымдарынын кандидаты дэрежэсш коргау диссэртациясы.

Бул жумыс "шыгыс" модельдер теориясынын кейб1р сурактарын жып - уйренуге арналады. Жумыстын Heri3ri максатн: ) Жет1лд1р1лген ионсондык теорияларды сипаттау; !) Эмбебап йонсондык унарлардын сипаттамасын алу; ) Алгебралык жэй модельдерд1н синтаксист^ критериш аныктау олып табылады.

Eshkeev Aibat Rafhatovich issertation on the theme "Jonson's teories" submitted ior mdidate's degree ol physics-mathematics sciences on speci-Lity 01.01.06 "mathematical logics, algebra and theory of лпЬегз ".

The present work Is devoted to the some questions of ¡astern" model theory. In particular, the following questions ¡re solved :

It have been found criterion oi notion oi the Jonson's theory rfectness. The Jonson universal of unars were described. In case

some additional conditions criterion of algebraically prime del was given.