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

Работа посвящена обобщённой вычислимости моделей, а именно, их представимости в допустимых множествах: А} - конст-руктивизируемости и £ - определимости и существованию различных неэквивалентных эффективных представлений модели (в смысле обобщённой вычислимости).

Существуют различные подходы к обобщению понятия вычислимости. Одни возникли из попыток решать алгоритмические проблемы, относящиеся к объектам, отличным от натуральных чисел (ординалы, вещественные числа и т.д.) Другие — из построений более сложных машин Тьюринга или вычислений при условии возможности использовать информацию о принадлежности числа определенному множеству (вычисления на обобщённых машинах, вычисления с оракулом). В данной работе рассматривается два подхода к обощению понятия вычислимости (оба, в конечном итоге, приводят к рассмотрению допустимых множеств).

Допустимые множества были введены Крипке [19] и Пла-теком [20]. Они перенесли обычную теорию рекурсии на ординалы, меньшие некоторого допустимого ординала. Первоначально допустимые ординалы были определены в терминах теории рекурсии, изложенной в стиле исчисления равенств Эрбрана-Гёделя. Позднее условия допустимости ординала были преобразованы в систему аксиом Крипке- Платека (КР), и произошёл переход от допустимых ординалов к допустимым множествам.

Результаты о том, что: a) наименьшее нетривиальное допустимое множество есть ШНУР (и;) = Ьшск , то есть множество всех подмножеств, конструируемых до уровня ординала Чёрча-Клини (наименьший нерекурсивный ординал) tJ(K, и b) а С ш является гиперарифметическим тогда и только тогда, когда a Е НYР(и) были получены Крипке и Платеком. Таким образом, существует нетривиальная связь между гиперарифметической вычислимостью и вычислимостью в допустимом множестве МУР (си)

Клини и Чёрч являются создателями общей теории систем обозначений для ординалов. Определение ниже принадлежит Клини.

ОПРЕДЕЛЕНИЕ 1 Система обозначений S есть отображение us множества натуральных чисел на отрезок ординальных чисел, удовлетворяющее условиям: г) существует частичнорекурсивная функция ks такая, что us(x) = О ks(x) = О vs(x) есть предельный ординал —> ks(x) = 2, и) существует частичнорекурсивная функция ps такая, что vs(x) есть последователь (ps{%) определена & vs(x) = VS{ps{X)) + 1), iii) существует частичнорекурсивная функция qs такая, что vs{x) есть предельный ординал —> (qs{x) определена & l's((fqs(x)ip})}'^Lo есть возрастающая последовательность, имеющая qs(x) своим пределом).

В [11] определяется универсальная (клиниевская) система обозначений О вместе с порядком .

Определение по индукции: О получает обозначение 1, предположим, что все ординалы меньше 7 получили обозначения и что упорядочение <о определено на этих обозначениях. i) если 7 = (3 + 1, то для каждого х такого, что [3 имеет х в качестве обозначения, 7 получает обозначение 2х, и пары (z, 2х) добавляются к <о для всех z таких, что z = х или (z, х) уже лежит в <о. ii) если 7 — предельный ординал,то для каждого у такого, что суть обозначения возрастающей последовательности ординалов с пределом 7 и такой, что

Vi)(Vj)(i < j {<Py(i),ipy(j)) уже принадлежат <о),

7 получает 3*5^ в качестве обозначения, и (z, 3*5У) добавляется к <о для всех z, для которых существует п такое, что (z, <ру(п)) уже лежит в <о .

Тьюринг обобщил понятие вычислимости [23], введя понятие оракула. Из сравнения различных оракулов возникла теория степеней неразрешимости и строились различные иерархии.

Через |ж| обозначим ординал, сопоставленный х системой обозначений О.

В [11] по системе обозначений О строится система оракулов:

Я(1) = 0,

Я(2х) = (.Н(х))' при хеО, Н{ 3 * 5У) = {{и, v) | v 3 * G Я(и)} при х GO. Известно, что ж G Оку G ОЗД = \у\ = а) Я(®) =г для любого предельного ординала а, получившего обозначение в системе О, и

Be А} Зф g ОкВ <! #(ж)) для любого В, и обозначения в О получают все конструктивные ординалы и только они.

Пусть х G О и |ж| = а. Тогда Н(х) будем обозначать На. (Ясно, что На определяется не однозначно. Но все На дают один и тот же класс вычислимых множеств и функций при вычислении с оракулом для одного и того же а).

ОПРЕДЕЛЕНИЕ 2 Пусть /3 = а+п, где а - предельный ординал, получивший обозначение в О, и п < ш. И пусть у Е О и \у\ = а. Положим vH(y) — 2~'п+1

П? = пй'

Для (3 = п < ш положим уЪ -Y п£ = пп

Д» = Е»ПП°.

По аналогии с арифметической данная иерархия называется гиперарифметической . Известно, что В — гиперарифметическое множество тогда и только тогда, когда В Е А® для некоторого а, получившего обозначение в системе О.

Одной из центральных задач математики является характеристика алгебраических систем с точностью до изоморфизма. К сожаленью, с помощью формул (и даже семейств фромул) обычной логики первого порядка в общем случае нельзя охарактеризовать счётные модели с точностью до изоморфизма. Если допустить рассмотрение бесконечных формул, ситуация меняется. Появление бесконечной логики связано с созданием теории моделей в логике приблизительно в 1962г. Впервые бесконечная логика была систематически изучена Карп [17].

Связь между допустимыми множествами и бесконечной логикой была установлена Барвайсом [15]. Он ввёл понятие "допустимых фрагментов" логики (и Lqo^), рассматривая только формулы, принадлежащие данному допустимому множеству.

Особый интерес представляют предложения и семейства Скотта. Теорема Скотта об изоморфизме [22] даёт, что для каждой счётной модели существует предложение Скотта, характеризующее её с точностью до изоморфизма. Впервые эта теорема доказана в дескриптивной теории множеств [21]. В данной работе предложения Скотта используются в том виде, в каком они появились в доказательстве Чэна теоремы Скотта [16]. Семейства Скотта являются некоторой аппроксимацией предложений Скотта и вводятся для доказательства теоремы Скотта.

ОПРЕДЕЛЕНИЕ 3 Семейством Скотта для счётной модели 21 называется счётное семейство формул Ф (возможно, с параметрами из некоторого фиксированного конечного множества), удовлетворяющее условиям: a) для каждого кортежа а элементов из А существует ср Е Ф такая, что 21 |= <р(А), и для каждой ср Е Ф существует кортеж а элементов из А такой, что 21 \= <р(А); b) если а и Ь удовлетворяют одной и той же формуле из Ф, то существует автоморфизм f 21 переводящий а в Ъ.

В теории конструктивных моделей ставились задачи харак-теризации моделей с точностью до рекурсивных изоморфизмов. Семейства Скотта оказались полезными для получения результатов об автоустойчивости в теории конструктивных моделей.

Различными авторами (В. А. Успенский, A. JI. Семёнов, С.С. Гончаров, О.В. Кудинов и др.) изучались различные сводимости и эквивалентности конструктивизируемых моделей. С.С. Гончаровым [2] были изучены понятия автоустойчивой модели и вычислимого класса конструктивизаций и получены условия неавтоустойчивости конструктивизируемой модели с разрешимой 3V- диаграммой в терминах существования 3-плотных семейств 3- формул (семейств Скотта). Им же построены примеры моделей конечной алгоритмической размерности (имеющие лишь конечное число неавтоэквивалентных конструктивизаций) и автоустойчивой модели, имеющей ровно две неавтоэквивалентных конструктивизации в некотором конечном константном обогащении.

Эшем [13] были введены понятия А® - устойчивости и А^-категоричности и ШУР- устойчивости и HYP- категоричности для рекурсивных моделей и получен ряд интересных результатов. В частности показано, что рекурсивная модель, имеющая семейство Скотта, А® - категорична (обратное не всегда верно) и доказано обратное утверждение при некоторых дополнительных ограничениях на модель.

О. В. Кудинов [10] ввёл понятие автоустойчивости в d для произвольной степени d и получил критерий d' - автоустойчивости для б?-1-разрешимых моделей.

В данной работе вводится родственное понятию ШУР- категоричности (но отличное) понятие Aj- автоустойчивости для гиперарифметических моделей и изучается его связь со значением ранга Скотта модели.

Основные результаты:

ТЕОРЕМА 1 Пусть Ш — А} - конструктивизируемая модель и sr(®T) < id(K. Тогда Ш — А} - автоустойчива.

ТЕОРЕМА 2 Пусть ЯЛ — Aj - конструктивизируемая модель. Пусть sr(9K) = , и v — её конструктивиза-ция. Тогда

1. Существуют конечное константное обогащение модели Ш и конечный набор с G M<UJ такой, что класс 5R всех (с точностью до А*- автоэквивалентности) А* -конструктивизаций (Я#, с) не является А} - вычислимым.

2. Существует ординал а < id(K такой, что Ш не автоустойчива ни в какой степени для всех 7 > а.

Так же усилен результат Эша и доказана невычислимость (в смысле принадлежности НУР(о;)) класса А]; - конструктивизаций булевой алгебры

Барвайс ввёл в теорию допустимых множеств праэлементы, и система аксиом Крипке-Платека (КР) была преобразована в систему аксиом Крипке-Платека с праэлементами (KPU). В этой теории наименьшим допустимым множеством, содержащим 9Я, является HF($T) — множество наследственно конечных множеств (или наследственно конечная надстройка) над Ш1.

В последнее время широкое распространение получили исследования вычислимости для абстрактных типов данных. С этой точки зрения особый интерес представляет понятие определимости в наследственно-конечных надстройках, поскольку в них хорошо интерпретируются все известные способы построения новых данных.

Ю.Л. Ершов [4] ввёл понятие Е-определимости и А- конст-руктивизируемости моделей в допустимом множестве и показал их эквивалентность. А.Н. Хисамиев изучал однозначную Е-определимость, ввёл понятие В -модели (модели, имеющей "достаточно" автоморфизмов) и получил критерий А- определимости жёсткой модели в наследственно конечной надстройке над В -моделью [12].

В рамках подхода Е - определимости, введенного Ершовым, изучалась определимость булевых алгебр и их рангов Фреше в наследственно-конечных надстройках. Построены примеры суператомной булевой алгебры, ранг Фреше которой не является Е- определимым в наследственно конечной надстройке над ней, и допустимого множества, в котором безатомная булева алгебра не является автоустойчивой.

В работе рассматриваются только счётные модели конечной предикатной сигнатуры.

Хорошо известны следующие факты:

- из существования конструктивизации модели следует существование однозначной конструктивизации [6];

- безатомная булева алгебра автоустойчива [1];

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

Предварительные сведения.

Пусть имеется кортеж натуральных чисел п = (щ,П1,. .щ) и нумерация v. Через v{n) обозначим (^(no), v(ni),., v(rik)). Множество всех кортежей натуральных чисел обзначается си<ш . Известно, что ш<ш G ШУР (со).

ОПРЕДЕЛЕНИЕ 4 Модель Ж = (М; Р^) называется А} - конструктивизируемой, если существуют нумерация и : uj —У М такая, что х,у) I 1/(х) = v(y)} G А\ и х\РМх))} G А\.

При этом v называется Д} - конструктивизацией 9Я, а пара (ШТ, v) называется Д* - конструктивной моделью.

ОПРЕДЕЛЕНИЕ 5 Две Д* - конструктивизации vq и v^ Д} - конструктивизируемой модели 9R называются Д} - автоэквивалентными, если существует гиперарифметическая функция f : и —> и и автоморфизм ip модели ШТ такие, что

Ух) (<p(y0(x)) = v1 (f{x))).

А\ - конструктивизируемая модель называется Д]; - автоустойчивой, если любые две ее Д} - конструктивизации Д* -автоэквивалентны.

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

ОПРЕДЕЛЕНИЕ 6 Пусть т = (N; ff4) - модель, такая что N С ш . называется гиперарифметической, если множества

N, Хщ) | Щ Pi(x 1, . . . , Хщ)} гиперарифметические.

Заметим, что модель Д^- конструктивизируема тогда и только тогда, когда она изоморфна гиперарифметической модели, и любая гиперарифметическая модель является элементом МУР(ш).

Определим, следуя Ершову [6], А\- вычислимые классы.

ОПРЕДЕЛЕНИЕ 7 Пусть и — нумерация семейства гиперарифметических множеств. Назовём её Д} - вычислимой, если х,у) |у G v(x)} — гиперарифметическое множество.

ОПРЕДЕЛЕНИЕ 8 Пусть $ - семейство Д} - конст-руктивизаций vn моделей Шп одинаковой сигнатуры а = {Р^ | г < к}.

Назовём 3R А\- вычислимым, если существует Д} - вычислимая нумерация семейства множеств

ОПРЕДЕЛЕНИЕ 9 Пусть Ш - семейство Д} - конст-руктивизаций.

Назовём Ji слабо А} - вычислимым, если существует Aj -вычислимый класс конструктивизаций того же семейства моделей, что и такой, что любая А} - конструктиви-зация из А\ - автоэквивалептна некоторой конструкти-визации из и любая А} - конструктивизация из А* -автоэквивалентна некоторой конструктивизации из .

В дальнейшем, если не оговорено противное, слово слабо в названии слабо А}- вычислимых классов будем опускать и называть их А} - вычислимыми.

Напомним несколько определений, следуя Барвайсу [14].

ОПРЕДЕЛЕНИЕ 10 Определим по индукции кванторный ранг формул языка '•

1. если <р — бескванторная, то qr(<p) = 0,

2. если (р = = а, то qr(ip) ~ а,

3. если ip = Qxi/>(x), где Q — квантор, qr(ip) = а, то qr((p) = а + 1,

4- если ip = УгФг или ср = А 1фг, то qr(ip) = sup{qr{^i)) (конъюнкции и дизъюнкции могут быть как конечными, так и бесконечными).

ОПРЕДЕЛЕНИЕ 11 Будем говорить, что Ж =а УХ, если для всех формул кванторного ранга < а

ОПРЕДЕЛЕНИЕ 12 Пусть дан кортеэ/с х G M<w.

Рангом кортежа х в модели Ш (г(х)) назовём первый ординал а такой, что

Ух' <Е М<и((Щ,х) =а (Ш,х') -»> {Ш,х) =а +1 (Ш,х')).

ОПРЕДЕЛЕНИЕ 13 Рангом Скотта модели Ш (sr(ffl)) назовём первый ординал а не меньше ранга любого из кортежей из М<ш sr(VR) — sup{r(x) | х G M<UJ}.

Свяжем с каждой моделью каноническое предложение Скотта:

Пусть дана модель Ш нашей сигнатуры.

ОПРЕДЕЛЕНИЕ 14 Для каждого ординала а и для каждого кортежа s = (xi,.,xn) определим а- характеристику s в (обозначаем crf(vi,., vn)) г) cr°s{vb---ivn) = cp{vi,. ,vn) | <p — атомарная или отрицание атомарной формулы и Ш \= (p(s)} ii) cr$+1(v 1,., vn) — конъюнкция следующих трёх формул:

1. a§(vi,.,vn);

2. Vvn+i У хеш .,vn, vn+i);

3. АхеШ 3vn+i(T^x(vi, .,vn, vn+i). in) Если А > 0 — предельный ординал, то <?g(vi,., vn) =

Л vl{vi,.,vn).

0<\

При необходимости указать на модель пишем сг^щ^ вместо erf. Если s — пустая последовательность, пишем аа или а^.

ОПРЕДЕЛЕНИЕ 15 Пусть дана модель Ш такая, что sr(m) = \i.

Каноническая теория Скотта (Sgn ) состоит из следующих прелдожений:

А4

Vvi,. -,vk((T^mtS){v ь. .,vk) ^здК • ■ -,Vk)) для всех конечных последовательностей s = (xi,., xj-) из ж.

Каноническое предложение Скотта — конъюнкция канонической теории Скотта: т ^ Л SW

Если дЛ — счётная модель, то предложением Скотта является предложение, обладающее свойством:

Ж ^ т ^ VI \=сгт для любой счётной модели ОТ. (Теорема Скотта) Известно, что для счётных моделей, r(s) = а —> ш,х) =а (m,s) (sot,®) ^ (an,s).

Напомним несколько определений и обозначений, относящихся к булевым алгебрам. Все необходимые сведения о булевых алгебрах можно найти в [1].

В [1] определяются естественный порядок на булевой алгебре: а < b allb = b и идеал Фреше. Следуя принятым там обозначениям, через Fa(QI) обозначим а-тый итерированный идеал Фреше алгебры 21. В дальнейшем, если из контекста ясно о какой алгебре идет речь, будем писать просто Fa вместо

Fa(21) .

ОПРЕДЕЛЕНИЕ 16 Рангом Фреше булевой алгебры 21 называется первый ординал р(21) = а такой, что Fa =

Fa+1 •

Известно, что ранг Фреше суператомной булевой алгебры является непредельным ординалом, и в фактор алгебре 2l/Fp(2i)-i(2l) конечное число атомов [1]. Тогда типом суператомной булевой алгебры называется пара г(21) = (а, т), где р(21) = а + 1 и га — число атомов в 21 /Fa. Известно, что счётная суператомная булева алгебра определяется своим типом с точностью до изоморфизма [1].

Кетонен топологическими методами получил характеризацию типов изоморфизмов булевых алгебр [18]. Затем Ю.Л.Ершов [5], на основе алгебраически методов, получил редукцию проблемы изоморфизма для класса дистрибутивных решёток с относительными дополнениями (алгебр Ершова). Приведём здесь его характеризацию для булевых алгебр.

Пусть р(21) = 7. Полагаем

Еа = {х Е А | идеал (x)/Fa П F^jFa - главный}.

Определим аддитивную функцию а : А —> 7 + 1, полагая сг(х) — а — первый ординал такой, что х Е Еа.

ОПРЕДЕЛЕНИЕ 17 Типом булевой алгебры 21 называется тройка (р, 7, га), где

Р = Р(Ю,

7 = <г(1) » и т равно числу атомов в 21 /Fa, если р = а + 1 > у, и нулю в противном случае.

Рассмотрим = 21 /Fp. Определим аддитивную функцию g из в 7 + 1, полагая g(x/Fp) = сг(ж).

Ю.Л.Ершов доказал, что 2lo = 2li тогда и только тогда, когда их типы совпадают и существует автоморфизм безатомной булевой алгебры </? такой, что (Ух) до(х) — SlO^O2?)) ■

Напомним, следуя Гончарову [1].

ОПРЕДЕЛЕНИЕ 18 Если 21 — алгебраическая система и X С | 211, то наименьшую подсистему, содержащую множество X назовём подсистемой, порождённой множеством X, и обозначим gr(X).

Говорим, что X — множество, порождающее 21, если gr(X) = 21.

ОПРЕДЕЛЕНИЕ 19 Линейно упорядоченным базисом булевой алгебры 21 называется линейно упорядоченное подмножество L, порождающее 21 такое, что L не содержит 1; а 0 е L.

Известно, что каждая счётная булева алгебра имеет линейно упорядоченный базис и изоморфна его алгебре полуинтервалов. Более того, каждая В - конструктивизация В - конструктивной булевой алгебры эквивалентна В - конструктивизации алгебры полуинтервалов некоторого В - конструктивного линейно упорядоченного множества [1].

ОПРЕДЕЛЕНИЕ 20 Двоичным деревом называется нижняя полурешётка с минимальным элементом, в которой каждый элемент имеет ровно двух наследников или максимальный и каждый начальный сегмент является конечным линейно упорядоченным мноэюеством.

Дерево без максимальных элементов называется полным.

Будем представлять двоичные деревья множествами конечных последовательностей из нулей и единиц (г, а, р,.). При этом г < а, если т - начальный сегмент а. Через т * а обозначим конкатенацию последовательностей г и а.

ОПРЕДЕЛЕНИЕ 21 Пусть Т - двоичное дерево. Построим отображение из Т в безатомную булеву алгебру: полагаем <^(0) = 1® .

Выберем для каждой a G Т (р (сг) так, чтобы если сг*0 Е Т, то p(a*0)\J<p(a* 1) = <р(<т),(р(<т*0)Г\(р(<7*1) = О®

Будем рассматривать подалгебру безатомной алгебры, порождённую <р(Т).

Каждая В - конструктивная булева алгебра представляется в виде булевой алгебры, порождённой В- конструктивным двоичным деревом.

Теперь введем понятия, касающиеся вычислимости в допустимых множествах. Допустимые множества будем рассматривать в расширенной сигнатуре а' — a U {£/, S, Е} , где а — исходная сигнатура модели, лежащей в основании допустимого множества. Определение допустимых множеств и все необходимые сведения о них содержатся в [14, 5]. Определения и обозначения ниже следуют Ершову [5].

ОПРЕДЕЛЕНИЕ 22 Пусть А — допустимое множество, S С. А — Е -множество.

Пусть f : Ord —А* — Е -функция, причём s= U /М

Тогда назовём f резольвентой множества S в А.

Допустимое множество А назовём резольвентным, если существует резольвента множества А в А.

ОПРЕДЕЛЕНИЕ 23 Пусть А - допустимое множество,

Ж = (М; (Jf ),<*> модель, где Рf* — предикатные символы, щ — соответствующая местность.

Говорим, что Ш — Е - определима в А, если существуют Е-формулы <р(х),фо(хо, хг), фо{хо,Х1),фг(х),ф^х), где ф^х), $i{x) зависят от щ переменных, такие, что фо определяет отношение эквивалентности на ц>к[х\,

N = cpA[x],

М2\ф$[х} = М2ПфоА1х}: Nni \ ф^[х] = Nni П фгк[х\, и модель о; о} изоморфна Ж.

ОПРЕДЕЛЕНИЕ 24 Если в предыдущем определении соответствующее отношение эквивалентности заменить на равенство, говорим, что 9Я — однозначно Е - определима в А.

ОПРЕДЕЛЕНИЕ 25 Пусть задано некоторое семейство S. А - нумерацией семейства S называется любое частичное отображение v : A—^S, являющееся отображением "на".

Пусть заданы модель Ш1 = (М; {Р^1)г<к), где Pi — предикатные символы, щ — их местность, и А- нумерация v модели 971. Обозначим через v~l(Pi) множество таких наборов (a;i,. хщ) из Ani, что Ж |= PiOOi), • • • Фп4)) •

ОПРЕДЕЛЕНИЕ 26 А- нумерация v модели

Ж = (М; (РПкк) называется А- конструктивизацией, если множества

Q = {(x,y)eu-1(M)\p{x) = v(y)}, (u-\M)f\©} v~\Pi) U являются X -мноэюествами.

Модель называется А- конструктивизируемой, если она имеет хотя бы одну А- конструктивизацию.

Известно, что модель ЯЛ Е- определима в допустимом множестве А тогда и только тогда, когда она А- конструктиви-зируема [5].

Пару (971, и) — модель вместе с ее А- нумерацией (конст-руктивизацией) — назовем А- нумерованной (конструктивной) моделью.

ОПРЕДЕЛЕНИЕ 27 Две А - конструктивизации щ и v\ модели Ш называются эквивалентными, если существует X предикат R(x: у) и автоморфизм (р модели такие, что

Vq1(M) CSRk сЦх,у) £ R)(x е vq1(m) k v0(x) = рЫуШ

Пишем (ЯЯ, щ) ~ (Ш, v\)

ОПРЕДЕЛЕНИЕ 28 Модель Ш называется А- автоустойчивой, если две любые ее А- конструктивизации эквивалентны.

Здесь определения аналогичны определениям, относящимся к конструктивизируемым (в арифметике) моделям [6].

Определим, следуя Барвайсу [14], в допустимых множествах £ - функцию sp(x), выделяющую носитель х.

ОПРЕДЕЛЕНИЕ 29 Определение по индукции:

1. U(а) sp(a) = {а}

2. S(x) —sp(x) = U{sp(y) | у G х}

Где U и S - предикаты, выделяющие праэлементы и мно-оюества соответственно.

Предикат, выделяющий функции (fun(f)) — является Д-предикатом на любом допустимом множестве (функция — множество упорядоченных пар со свойством однозначности). £-функциями являются функции, выделяющие область определения (<5(/)) и область значений (p(f)) функции. Функция, сопоставляющая произвольному элементу допустимого множества его ранг, является функцией. Для допустимого множества А функция истинности формулы <p{v) из L& в модели Ш1 из А на элементах х является Е- функцией от (p(v),ffl, х.

1. Гончаров С.С. Счетные булевы алгебры и разрешимость. Новосибирск: Научная книга, 1996

2. Гончаров С.С. Автоустойчивость и вычислимые семейства конструктивизаций// Алгебра и логика. 1975. Т.14. с.647-680

3. Гончаров С.С. Число неэквивалентных конструктивизаций// Алгебра и логика. 1977. Т.16. с.257-282

4. Ершов Ю.Л. Е- определимость в допустимых множествах// Доклады АН СССР, 1985, т.285, п.4, с.792-795

5. Ершов Ю.Л. Дистрибутивные решётки с относительными дополнениями// Алгебра и логика, 1979, т.18, п.6, с.680-722

6. Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. Москва: Мир, 1980

7. Ершов Ю.Л. Определимость и вычислимость. Новосибирск: Научная книга, 1995

8. Кирпотина Н.А. Элементарная эквивалентность в языке списочных надстроек// в сб. Теория вычислений и языки спецификаций, Новосибирск, 1991, Вычислительные системы, вып. 139, с.26-37

9. Клини С. Функционалы конечных типов, вычислимые на машинах Тьюринга, пер. с англ. в сб. Математическая логика и её приложения, Москва: Мир, 1965, с.37-46

10. Кудинов О.В. Проблема описания автоустойчивых моделей// Алгебра и логика, 1997, Т.36, п.1, с.26-36

11. Роджерс X. Теория рекурсивных функций и эффективная вычислимость, пер. с англ. Москва: Мир. 1972

12. Хисамиев А.Н. Сильная Ai- определимость модели в допустимом множестве// Сибирский математический журнал, 1998, т.39, п.1, 191-200

13. Ash C.J. Categoricity in hiperarithmetical degrees// Annals of pure and applied logic, 1987. v.34 n.l, p.1-14

14. Barwise J. Admissible sets and structures. Berlin: Springer, 1975

15. Barwise J. Infmitary logic and admissible sets// J. Symbolic Logic, 1969. v.34, p.226-252

16. Chang C.C. Some remarks on the model theory of infinitary languages, in The Syntax and Semantics of Infinitary Logic// Lecture Notes in Math., Berlin, 1968, V.72 (ed. Barwise), Berlin:Springer, p.36-63

17. Karp C. Languages with Expressions of Infinit Lenght. Amsterdam: North-Holland, 1964

18. Ketonen J. The struture of countable Boolean algebras// Ann. Math., 1978, v.108, n.l, p.41-89

19. Kripke S. Transfinite recursion on admissible ordinals, I, II (Abstract)// J. Symbolic Logic, 1964, v.29, p. 161-162

20. Platek R. Foundations of recursion theory: Dissertations and Supplement. Stanford (Calif): Stanford University, 1966

21. Scott D. Invariant Borel Sets// Fund. Math. 1964, v.56, p.117-128

22. Scott D. Logic with denumerable long formulas and finite strings of quantifiers, in The Theory of Models, Amsterdam: North-Holland, 1965

23. Turing A.M. System of logic based on ordinals// Proc. London Math. Soc. 1939, Ser.2, v.45, p.161-228

24. Ромина А.В. Автоустойчивость гиперарифметических моделей// Алгебра и логика. 2000, т.39, п.2, с.198-205

25. Ромина А.В. £ определимость булевых алгебр в допустимых множествах// Алгебра и логика. 2000, т.39, п.6, с.711

26. Ромина А.В. Гиперарифметическая устойчивость булевых алгебр// в сб. Обобщенная вычислимость и определимость. Новосибирск, 1998. Вычислительные системы, вып. 161 С.21-27.

27. Ромина А.В. Автоустойчивость гиперарифметических моделей/ тезисы докладов международной конференции по математической логике, посвященной 90-летию со дня рождения академика А.И.Мальцева, Новосибирск, 1999,719с.53-54