Разрешимость теории Th(w, 0,1, <, +, f0,..., fn)
Аннотация
Данная работа посвящена исследованию свойств теорий, образованных из арифметики А.Л. Семенова добавлением функций fi,i > 0, которые в работе названы «гиперфункциями», полученных итерацией, согласованной со сложением функции fo. Доказано, что такие теории являются модельно полными. Также показано, что при выполнении условия эффективной периодичности гиперфункций теории являются разрешимыми.
Список литературы
1. Булос Дж., Джеффри Р. Вычислимость и логика. М.: Мир, 1994.
2. Верещагин Н.К., Шень А. Языки и исчисления. М.: МЦНМО, 2002.
3. Семёнов А.Л. О некоторых расширениях арифметики сложения натуральных чисел // Изв. АН СССР. 1979. 43(5). С.1175-1195.
4. Семёнов А.Л. Логические теории одноместных функций на натуральном ряде // Изв. АН СССР. 1983. 47(3). С.623-658.
5. Снятков А.С. Разрешимость теории Tc = Th(u, 0,1,<, +,cx, Cx) // Вестник ТвГУ сер. Прикл. матем. 2007. 5(35). С. 113-121.
6. Снятков А.С. Разрешимость теории Tf = Th(u, 0,1,<, +,f (x),F(x)) // Вест¬ник ТвГУ сер. Прикл. матем. 2008. 14(34). С. 39-51.
7. Ackermann W. Zum Hilbertschen Aufbau der reellen Zahlen // Mathematische Annalen. 1928. 99. P. 118-133.
Для цитирования:
Снятков А.С. Разрешимость теории Th(w, 0,1, <, +, f0,..., fn). Моделирование и анализ информационных систем. 2010;17(3):72-90.
For citation:
Snyatkov A.S. On Decidability of the Theory Th(u, 0,1,<, +, f0,..., fn). Modeling and Analysis of Information Systems. 2010;17(3):72-90. (In Russ.)
Просмотров: 126
Послать статью по эл. почте 