Определимость в наследственно конечных допустимых множествах

• Автор: Хисамиев, Асылхан Назифович
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 1999
• Место защиты: Новосибирск
• Количество страниц: 68 с.

ОГЛАВЛЕНИЕ
Введение
Глава 1. Е- нумерация и Е - определимость в наследственно конечном допустимом множестве
§1. Е- нумерация и критерий Е - определимости в ЕГР(ШТ) над моделью Ш1, допускающую Е- нумерацию
§2. Нумерация конечно порожденных алгебр
§3. Условие существование Е- нумерации
§4. Некоторые применения
§5. Одно условие Е- определимости модели в
наследственно конечном допустимом множестве
§6. О внутренней перечислимости линейных
порядков
Глава 2. Сильная Д[- определимость модели в допустимом
множестве
§7. В- модели и критерий А- определимости модели в наследственно конечном допустимом множестве
§8. Абелевы р- группы
§9. Булевы алгебры
Литература

Введение
Попытки математиков решить трудные алгоритмические проблемы привели к необходимости уточнения понятия алгоритма. В работах Поста, Тьюринга, Клини, Маркова были даны точные определения этого понятия. Эти уточнения относятся только к алгоритмам, входные и выходные данные которых можно считать натуральными числами. В то же время в математике известны алгоритмические проблемы, которые связаны с более широким классом объектов (действительные и комплексные числа, произвольные поля и т.д.). Для охвата этих алгоритмических проблем были предложены различные обобщения обычного понятия алгоритма. Одним из таких важных обобщений является понятие Е- определимости в допустимом множестве над данной моделью. При таком обобщении оказались справедливыми аналоги многих важных теорем обычной теории алгоритмов.
Наименьшим допустимым множеством над моделью Ш является наследственно конечное допустимое множество ЯЕ(ШТ). Ю.Л. Ершовым в [4] введено понятие Е- определимой модели в ЯЯ(Ш1), которое является обобщением понятия кон-структивизируемой модели. Например, справедливо следующее утверждение [6]: если модель Ш конструктивизируе-ма, то модель 91 Ег определима в ЯЕ(9Я) тогда и только тогда, когда 91 конструктивизируема. Поэтому представляет интерес исследование Е- определимых моделей в

ЯР(ШІ).
Основные результаты, полученые в этой области, приведены в монографиях Ю.Л.Ершова [4] и Дж.Барвайса [23]. Ю.Л.Ершов [7] получил интересный критерий Е- определимости несчетной модели в наследственно конечном допустимом множестве НЕ(Ь) над плотным порядком Ь без концов. Отсюда, например, следует, что поле комплесных чисел Е- определимо в НЕ(Ь) над плотным линейным порядком без концов мощности континиум. В то же время поле действительных чисел її не Е~ определимо в НЕ(Ь) ни для какого плотного порядка.
Диссертация посвящена исследованию Е- определимости модели в наследственно конечном допустимом множестве. Она состоит из двух глав и девяти параграфов. Перейдем к изложению основных результатов диссертации.
В первой главе введено понятие внутренне перечислимой модели и получен критерий Е- определимости модели в НР(Ш) для внутренне перечислимой модели Ш.
Рассматриваются только не более, чем счетные модели конечных сигнатур. Говорят, что алгебраическая система — —< Мі, Р”1
<Р,77,Фі
такая, что
X р*[х0, 11 Г1*[х0, хі] Г) X2 есть отношение конгруэнтности на алгебраической системе

Р = Ф?[г0| хті-і]Л Хщ, 1 < І < 3,

§6. О внутренней перечислимости линейных
порядков
В данном параграфе доказано, что любое линейно упорядоченное множество не внутренне перечислимо. Для этого установлены критерии экстенсиональной эквивалентностей наследственно конечных допустимых множеств, представляющих самостоятельный интерес. Ершов Ю.Л. в [4,стр. 196] получил критерий для достаточно насыщенных моделей Ш. когда элементы /го, /гх из НР(Ш) реализуют один и тот же тип. Оказывается, что этот критерий справедлив для любой модели 9Л, если ограничится рассмотрением только 1-типов.
Пусть ЯЛ15 9Яг - счетные модели конечной сигнатуры СГд. Модель Шх назовем экстенсионально беднее модели Шг. если любое 3 -предложение сигнатуры СГо истинное в модели истинно и в модели Ш12, и будем обозначать как Шг.
Пусть Ш]_, Ш12 - счетные модели конечной сигнатуры а о и о = (Т0 и {Е, 0, II, }- сигнатура наследственно-конечных множеств, где предикат II в НР{Ш:) интерпретируется как множество праэлементов. Расмотрим сигнатуру <т2 = 0 и {с?}, д константный символ такой, что б £ а{). Пусть < НР(9Я1), Ъ > и < НР(ШТ2), с > модели сигнатуры т2, с! интерпретируется в НР(9Я1) и ДЕ(Ш12) как Ь и с соответственно. Тогда справедливо предложение.
ПРЕДЛОЖЕНИЕ 6.5 Модель < НР(дЯ1),Ь > экстенсионально беднее модели < НР(Шг),с > тогда и только тогда, когда выполнено условие:
щ) Для любой конечной концевой подмодели 21 С С< НР(Ш1),Ь > найдутся концевая подмодель 95 С