Выразительная сила языков первого порядка для конечных алгебраических систем над бесконечными универсумами

• Автор: Дудаков, Сергей Михайлович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2006
• Место защиты: Тверь
• Количество страниц: 176 с.

Актуальность

Обзор литературы

Цели работы

Апробация работы

Структура диссертации

1 Определения

1.1 Основные обозначения

1.2 Теории и алгебраические системы

1.3 Арифметические теории

1.4 Автоматные системы

1.5 Свойство коллапса к сигнатуре

2 Термально изолированные множества
2.1 Определения
2.2 Существование термально изолированных множеств
2.3 Коллапс к порядку для арифметики Семёнова
2.4 Свойства предикатных обогащений начального фрагмента
нестандартных моделей арифметики Пресбургера
2.5 Коллапс к порядку для обогащений начального фрагмента
нестандартных моделей арифметики Пресбургера

3 Случайный граф
3.1 Определения
3.2 Состояния над случайным графом
3.3 Разрешимое упорядочение случайного графа
3.4 Мопадические сигнатуры
4 Сводимые теории
4.1 Основные определения
4.2 Свойства сводимых алгебраических систем
4.3 (&,/)-формулы
4.4 Тотальная сводимость систем
4.5 Достаточные условия сводимости
4.6 Сводимость, изолированность и псевдоконечная однородность
5 Автоматные системы и их обобщения
5.1 Сложное обогащение арифметики Пресбургера
5.2 Элиминация кванторов в теории Тд
5.3 Начальные фрагменты системы £я
5.4 Состояния 2Д над системой £Е
5.5 Обобщения теории ТЕ
6 Эффективная трансляция
6.1 Достаточные условия эффективной трансляции
6.2 Приложения к классическим теориям
6.3 Арифметика Пресбургера
6.4 Теория действительных чисел
6.5 Эффективные обогащения Семёнова арифметики Пресбургера
Заключение
Основные результаты
Направления дальнейших исследований

Литература Предметный указатель

и не выполнено
У г/(ч » о) л Р( (8

Так же очевидна эквивалентность
V У{к) » 0 ) Л -пРг (у) ^ V уМ » 0.
к ) к
Здесь — к-ая компонента набора у. Следовательно, можно считать, что
если формула <р содержит Р-. (й), то для всех г А выполнено <0. Если это не так, то всё сводится к случаю с меньшим количеством вхождений Выберем произвольное к, пусть терм г® имеет вид
(к) , (к)
р + т- >х,
где Шг € и, Ш; ф 0 И ^ Не СОДерЖИТ X, И обозначим
№) , [к)
У = Рг + Щ X.
Тогда, заменив всюду х на
(к) У
(к) ’
ш; '
вместо мы получим формулу (р1:
(з у Є ш) |(4 < у ^ 4) Л (4 «1 у «2 4) Л (А р■; (г')
где каждый г'А имеет вид /Д. + хп'ку. Упростим её.
Если 4 ^ 0, то формула ложна. Если і'2 >■ 0, то неравенство у ^ 1'2 можно опустить. Таким образом, можно считать, что 4 и Д — натуральные числа.
Так как у Є од то двойное неравенство
4 < у <*2 У2
сводится к неравенству
4 «Ї о« 4,