|
Алгебра и логика, 2004, том 43, номер 6, страницы 650–665
(Mi al101)
|
|
|
|
Эта публикация цитируется в 31 научных статьях (всего в 31 статьях)
Сложность теорий вычислимых категоричных моделей
С. С. Гончаровa, Б. Хусаиновb a Институт математики им. С. Л. Соболева СО РАН
b University of Auckland
Аннотация:
М. Лерман и Дж. Шмерл дали некоторые достаточные условия для существования вычислимых моделей счетно категоричных арифметических теорий. Более точно, они показали: если $T$ – счетно категоричная арифметическая теория, причем множество всех ее предложений, начинающихся с квантора существования и имеющих не более $n+1$ чередующейся группы однотипных кванторов, лежит в классе $\Sigma_{n+1}^0$ для любого $n$, то теория $T$ имеет вычислимую модель. Дж. Найт улучшила этот результат, добавив условие определенной равномерности и опустив требование арифметичности теории $T$. Однако, все известные примеры теорий $\aleph_0$-категоричных вычислимых моделей имеют низкий уровень алгоритмической сложности и было неизвестно, существуют ли теории, которые бы удовлетворяли условиям, установленным М. Лерманом и Дж. Шмерлом, для достаточно больших $n$. В этой работе строятся такие примеры.
Ключевые слова:
вычислимая модель, счетно категоричная теория.
Поступило: 08.09.2002 Окончательный вариант: 16.09.2003
Образец цитирования:
С. С. Гончаров, Б. Хусаинов, “Сложность теорий вычислимых категоричных моделей”, Алгебра и логика, 43:6 (2004), 650–665; Algebra and Logic, 43:6 (2004), 365–373
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/al101 https://www.mathnet.ru/rus/al/v43/i6/p650
|
Статистика просмотров: |
Страница аннотации: | 577 | PDF полного текста: | 148 | Список литературы: | 68 | Первая страница: | 1 |
|