Главные нумерации вычислимых функционалов на допустимых множествах тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

АКАДЕМИЯ НАУК СССР СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

На правах рукописи

ВАЙЦНШЗИЧШ Римантас КЬзас Витаутович

УДК 510.5

ГЛАВНЫЕ КУМЕРАЦЖ ВЬГСИСЛКШХ ФУНКЦИОНАЛОВ ' - НА ДОПУСТИМЫХ МНОЖЕСТВАХ

01.01.06 - математическая логика, алгебра и гооряя чисел '

• а

Автореферат'

дассэртации на соисклшю ученой степени кандидата физико-математических наук

Диссертация' выполнена в Ш.^титута математики и шторма-тики Литовской Академии наук.

Научицй руководитель - член-корреспондент АН СССР,

доктор физикочлатсштических наук Ю.Д.Ераов,

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

В.Л.Селивацрв,

кавдидат физико-ютематическшс наук В.А.Рудаов.

Ведуцая организация - Казанский государственный

университет ш. В. И. Ульянова -Легши.

• q<? « • ... п.--. -/./ — Защита состоится "if^L.™ с л 1991 г. в ___ча-

■ v

сов на заседании спэцшшшгоосашюго соцзта Д 002.23.01 ори Институте математики СО АН СССР по адросу: г.Новосибирск, 90, Университетский проспект, 4. •

С диссертацией гэзю ознакомиться в библиотеке Института глатешткг : СО /Л СССР.

Авторофарат разослан ". " jggj Г>

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

к.ф.-м.н.

ßC^---

В.Г.Скосырсх^ай

Б диссертационной работе исоледуругся достаточные условия' существования главных вычислимых нумераций вычислимых функционалов конечных типов на долус-татех шок&ствах. Изучоиие данного вопроса важно; так как суцсствовзипа глав:шх нумераций функционалов-на некоторой- структуре озпач&е? возкокность по- , строония для нее универсального языка прог'рш-мироваккя, а также важно для развит.:* теории ^-лрогрьюафованшг [X» 5] . . Главные нумерации фудкэдоколов- п случаэ нумераций натуральными числами построена Ю.Л.Краоки'м [ 2. 3] .. '

IIли различных классов допустимые шожэотв вычислимые иу-мерзции итолшиг $ушщий строилась Еарвайсом 9'] н В.А,Руд- г квит [ о, в] . З.А.Руднов [ о, ?] построил допустмммо множества, в .которых на .существуют зч'юслчмм. нумерации всех рвкурся-кшх функций. ЮЛ. Ьриов I 4 построил глав,чне'.нумэрация предикатов конечных типов. Настолаая работ« продолжает упомянутые взае хослодов&ьия.

Цела» работа является дс-кэгательстьо достаточных уолоакй-существования главных нумераций до&охл&х '$ужс*лоналов «а до- 1 • ) нултлстх шихоствах « построение таких "укораилй, эелн оии су- '

цвСТЗу-СТ. ' .' . - ' ' г)-" \ .' /. -■ ' -'','

• йое.сеяо:аяг» речульп-агы-.дисоэрта1да»нао^ ра.йот«*- тлОкоя .3 '

новыми и состой'? а охадфЯДО*» На осзоккод: шюде.>вашзых нумерационных рзойста рэзгк'м.-лс хэаустазкас иаэжзотв даккозчз, что главные нумерации вычкс.г:;£к«х ^'кявдоаааов конечных тапоз существуют.

I) на резольвентном доцустимом множестве, . 2) на наименьшем допустимом миогестве над моделью, содержащем модель б качестве элемента, допустимого множеотвд,

3) на допустимом множество, обладаюцем элементарной подмоделью, являющейся внутрирезольвектшм допустимым множеством с 2-характврниацией автоморфизмов,

4) на множество наследственно конечных множеств над а томно! моделью разрешимой теории, оелк множество атомных' формул юории рекурсивно, причем каздда атомная фзрмуда акаавасеатна

-формуле с этама элгке^года*

5) на ююжвсгсш лвкечкиа: эгашосхв взд; подал ыз отнжйЕа ¡шша^кт^сг^гш».

6) ка- ежйййт&с? та^адзяЁксза кокг-чизх инодвезв кэд РЗй/йа с «гжйлзгзю -одздрсашйя высо-гн из и с коьечкни чнояои

В даагжгедмтгах испол:>зуэтся категорный подход к нумз-ргхзчЛЕаэг ггэгкгеждам, а также представление множества морфизмов; об&здят затагорик нумерованных множеств Ю.Л.Ершова.

юста в. основном теоретический характер. Результат©

ты ра¡&ша кдарг Синь иадальзованы б теории допустимых, мноа&сш к в обл£№&г X-Ерэй^а^жжаа»

Осшвша дою^теадея дакявдгкатхь ва 9-31

Всесоюзной шгф^зшда №. жшша'отшэа! »та Рк^ишадад» ; 33), на 2-й за зшклэдтЙ .дкгзта

(Ноюсисжрск, ЗЭ&Йк йя 'гаашзраж '"Эасэдта: щчщт&ЗГ ж '"¿дге-

■■'А

бра и логика" при Нозэсибирскон государственно»-; университете, на ежегодных конференциях Литовского матемзтпчоекгл'о 6с(!Г,оот-38. (1387, 1958, 1Э6Э, 1990).

Основано результаты диссертации опу&такозэик » работах , [ТО - IV] . •

Диссертация состоит из введения,' трех тля в, рэгдолонннх на 16 параграф в, заключения -I списка литературы, сохегжацо-го 21 наименование. Обдай осъем. работы ВО страниц магсонэаис- ■ него текста. , .

Первая глаза цэевяиона изучение нумерационных свой.отз до-пустаакх «некветп к начинается' с определения осиошнх пенящий теории допустимых: множеств я с пзлояакия :основшюг теорем теории допуатанах множеств. 3 § 1.2- доказывается одно нумерационное свойство резольвентных допустшгых множеств.

ЛЕША 1.Х. Пусть Д ''резольвомтков допустимое мио«в««~ во, В>~*5 - шчисушзя иушряция, <^(Х .X ) - Д-форму-и и, если ^ о ^Х.^/--^ , то

$ . Тогда сокэйотао 'мМх^^-^(х^х^ ^

зола дает зычиглнкой нумерацией.'Если . - главная нумерация, со Б обладает главней нумерацией.'' ^

Как следствие г-гого утвзрадеиия получена главная нумерация Х-Фуккдай на резольвентных множествах.

В § 1,3 вводится понятие резольвентно нредстаэдалого до-[устимого множества и в § 1.4 дия этих г.т'ожестз и их эломек-•арных расширений доказаны нушрациокнал тосрема 1'.5 ацади- . ■ичкая лелие 1.1.

'В § 1.5 вводится понятий внутрярозольввнтяого множества, опустимоо гянонество А ' набивается кг/трурвгюлььштнш, ес-•л на резольвентной части С ынскаства .могаю А-одре-

долить модель С — С}... изоморфную структура А и бинарно о отношение от X и ц- "существует изоморфизм ■ су моделей /\ п С. , что ^ " является Д-предикатом.

1.2. Каждое внутрирозольвонтное допустимое множество является резольвентно кродставимым.

Там жэ приводится- пример резольвентно- представимого не знутрарезольвентного допустимого множества. Далее вводится понятие 2-харзктаркзашш автоморфизмов анутрирезольвенткс— щэедставленкя, помогавшее болоэ удобно сформулировать те-ор.аад 1,5 в случае вцутрирозольвонтких допустимых множеств".

В § 1.6 доказывается, что если И1 - счетная атомная модель. Т К1Ш.) - разрешимая теория с рекурсивным множеством атомных формул Яг* и каждая атомная формула % ^ эквивалентна г!-формуле, то множество Н Р IГРЛ наследственно конечных множеств-над медалью является вдутрщзезольвент-нш.1, а в § 1.7 установлено, что НгЧУОЛ над такой моделью обладает ^-характэрп.заццай автоморфизмов внутрирезольвент-кого представления.

Если - формула и ё-Ъ X, ^ , то

множество 5 называется с^ -согласованным.

В § 1.8 формулируются заключительны о нумерационные теоремы главы. В частности, доказаны

ТЕОРЕМА 1.6. Пусть А^ - допустимое множество и дяя

некоторого О. еД. многие гь<} (Я^д1^) является элемен -

¿и ¿и

тарным райшрением допустимого. множества с А. -характериза-

цией азтоморфазмээ кнутрирезольвентното представления. Пусть ^Сх^") - /\ -формула без параметров устойчива относи -тэлыю перестановок на Ш. . Тогда на существует гла-

вная нумерация семейства всех ^»-согласованных 2-множеств.

ТьОРЙЛА 1.7« Цусть А'1 - атомная модель, теория Т К разрешима, множество атомшх формул Я"5 теории I Н(№0 рекурсивно, иричом для Некоторых ггц,...^^ Ш-' каглая формула кз Я> эквивалентна З-фэрмуло с параметрами . Пусть ИР I ЛЯ) - допустимое множество и X, ) - Д-фор-мула без параметров устойчива относительна перестановок на ГЛ. . Тогда на Н1"(ГР-) существует главная вычисд'-жая нумерация семейства ^»-согласованных 2 -множеств.

Глава 2 посвящена исследованию вопроса, когда нумэраци- ■ онные свойства допустимого множества Д-^А,--.^ сохраняется при переходе на его подмодель допустимое множестзо В=\6>,...7-¿-формула с параметрами из Р> называется

&-замкнутой, еали V У и^'Ф ЕК У

•Мшжостйо X назьииотся ¿^^«ЯродоЛжимк^ на до множества У , если с>«остауот ^ -формула с Йарамёт-рами из В> , что X = I г 1 & И 61 гЛ \ , У - ЫАЬ В( 2)}.

ТЕОРгМА '¿. I. Пусть допустимое множество 1В — ^й»,... ^ -подмодель модели'< А ; X, - До~фэрмула

с. uapav.eTpat.ui из- р> , \)д - вычислимая нумерация семейства всех «^-согласошшшх 2 -множеств определима В -замкнутой формулой VI х,^") . Пусть каждое «^-согласованное

-мкожэство 2^-лродс.ткпмо на А- до (^-согласованного божества "У причем "Уд ( Л В Р . Тогда :я существует вычислимая нумерация семейства всох ц>-со-'лэсовэшшх -множеств.-

В § 2.2 исслэдуются достаточные условия, когда ^-согла-¡овгнноо ^ (|Е>)-множество ^'^-прододаимо до -согласованного {Я") -множества. В § 2.3 доказана ' ТгЮРН.'.ч 2.2. Пусть -<> _ модель отношения' зк-

«

зиваяеитноотк ¡г X ,улч; ■• Л0-фэрмула без параметров сигнатуры , { = , "и.-*! • Тогда на . Н Р Iсуществует . вычислимая нумерация семейства всех . ф -ссх'лзсованных /

В § 2.4 определен класс деревьев с отношением

следования высоты СО и с конечны:/.- числом ветвлений. ТИСРЕМА 2.3. Пусть дерево <ГП — < И £ I) > НР (Ш -допустимое множество, " ' .без парамет-

ров сигнатуры 1 ~, ; Ц \ . Тогда на НР (¡Г^) существует вычислимая нумерация семейства всех с^ -согласованных ^-ютахсоств. -

Глава 3 ¡гюеввдена непосредственно построению главных ну--глераций фунирюаалов. Посла краткого изложения определений и результатов Ю.Л.Ерысьа [4] о категории нумерованных множеств доказывается теорема 3.2 и 3.3, позволяицае определить главный вычислимые нумерации мков.ества 'шрфызмов Мог ^¿^ из нумерованного множества ^ ^ в нумерованное множество ^ * В § Л.З определяются вычислимые функционалы рд (б) типа на допустимом маояеетве А вместо с главными нумерациями, а з § 3.4 формулируются к доказывается теоремы, ка-лягаадае достаточные условия на допустимое множество, чтобы существовали главные нумерации фушадаокадов.

Т'КОРЖА 3.4. Пусть Я - резольвентное допустимое 'мно-тастЕо. Тогда дагя каждого типа ^ множество вычислимых

функционалов обладает главной вычислимой нумерацией,

ТЕОРЖч 3,5. Пусть Я = <САГ'..> - допустимое множество и 'для некоторого элемента О. £ А обогащение (/^сО обладает элементарной подмоделью, явяшадайея внутрирззользентным допу-

стиа/ш множеством с 21-характвриэациеЛ 'автоморфизмов -вну-триреэольвентного представления. Тогда для каждого В а Л" множество функционалов 'ГЛвУ обладает главной вычйслзаазй нумерацией. ' ..

ТЕОРЕМА 3.6. Пусть Ш- - атомная модель, теория К1Ш) разреши™, множество атомных формуя теории Г К 1сТ0 рекурсивно, причем дДя "некоторых каадая формула из <р.. эквивалентна 3 -формуле с параметрами №1Л. .

V > к.

Тогда для каждого типа б € 1 множество функционалов обладает главней вычислимой нумерацией.

11 г •»> и

'ГЕОРЫЛА 3.7. Пусть <5Т1 - произвольная модель. Тогда дяя каадого Т множество функцконалоз обладает главной вцчислимой нударавдей.-

ТЕОРЕМА 3.8. Пусть Ш. - модель- отношения яка^валентное та. Тогда для каадого тина £ €.~Г класс вычислимых функционалов ^рцчО^^ ! обладает главной вычислимой нумерацией. ,

. ТЕОРИИ 3.9. Пусть Ш. дерево из . Тогда для

каждого . еТ класс вычислимых функционалов ^ р^ обладает главной вычислимой нумерацией.

В конце главы 3.доказано предложение о естественности предлагаемого определения вычислимых функционалов.

Автор внраяаот глубокую благодарность своему научному руководителя члвну-корресисяденту АК СССР Юрш. Леонидовичу Ершову. '

ЛИТЕРАТУРА

т. Гончаров 1?.С., Сьириденко Д.К. ¿^ -лрограммироьянио //Логико-яатэматичоскиэ проблем« НОУ. Бичислптольнке системы. 107. - Новосибирск: ИМ СО АН СССР, 1985. - С. 3-29.

2. Ериоь У.Л. Теория нумераций. - !/..: Наука, ЮТ.

3. Ершв У.Л. Вычислимое нумерации мор£измоп //Алгебра и логика, 1571. -- Т. 10, .та. - С. 2-17-308.

4. Ерщов 1;.Л. 2 -предикаты конечных типов над допустимом множеством //Алгебра и логика, 1УУ5. - Т.24, ¡¡6. -

С. 49Э-336.

, 5. Ершов Ю.Л. Язык 2-выражений //Логические теории гипоз данных. Зычу.сл/л-сльнке сиетоин, 114. - Новосибирск, ИМ СО АН СССР, И'ОС. - С. 3-Ю.

6. Руднев В.А. 0(5 универсальной рекурсивной функции на допустимых .".пшествах //Алгебра к логика, 1986. - Т.25, №. - С. 425-435.

7. Руд ко в В. л. О существовании неотделимой дару а рсисур-сивлой теории допустимых множеств //Алгебра и лотка, 19Вй.-•Г.27,'й I. - С. 4У-56.

8.. Руднев В.А. Рехурсивн;-л теория керэгользонтных до-пуотжых ¡¿нолестз. Кандидатская диссертация. -- Новосибирск, 1938.

9. В>од'\л; Т, /1с

Вег'иа-- Ьрпл^ег В4 5.

Публикации авт;. ра по теме диссертации

10. Вайценавичюе Р.Ю. Ба!» '¡слише нумерации вучислнь'ых" функционалов на К \_-дспуст;ц ^х множествах /Д'.атам,лог;!кг .

и ее применения. - Вилы их: 'Д,!К ЛитССР, 1387. - Ньгл. 5. -С. 123-132.

11. Байцснзвячюс Р.Ю. 0 ыгутркрэзолььентшх дспустп-мых множествах //Жатем, логика к ее применения, - Бплькюс: ИМК АН ЛитССР. 1580. - Вып. 6, С. 5-20.

12. Байценаншчюс Р.Ю. О главных нумерациях функционалов над допустимыми множествами .//Алгебра и логика, 1590, - Т.23, ¡54. - С. 358-420.

13. 1'айценавичхе Р.Ю. О главных нумерациях функционалов над допустимыми множествами /ДлХХ конф. Литовского математического общества. Тез. -докл. II. - Еилънюс, 1538. - С. 67.

'14. Вайценаэичис Р.Ю. С главных нумерациях вычислимых функционалов в допустимых множествах над произвольной моделью //9-я Бсэсошн. конф. по .".атем. лотке: Тез. докл. -Ленинград: Наука,.1888. - С. 24.

15. Вэйцвнаничюс Р.Ю. О главных нумерациях морфдзкоз над допустимыми множествами //2-я Всосоюзн. конф. по прикл. логике: Тез. докл.Новосибирск: ИМ СО АН СССР, 1Э88. -

С. 41.

16. Вайцеиавичюс Р.Ю. О выразимости ¿С -формул //30-я конф. Литовского матем. об-ва: Тез. докл. - Вильнюс: ИМК АН ЛитССР, 1985. - С. 152-153.

17. Уолсег\<хч услиъ лл\*>\4г-лЛил\. ргср^г-

1л1;к и и. Л|«л.п, тлЛк £ т ¡дЛ I с «А УЛлх^ь :

ЗМ1 , МО.