Структурные свойства предельно монотонной сводимости последовательностей множеств

Д.Х. Зайнетдинов

Казанский Приволжский федеральный университет, г. Казань, 420008, Россия

Полный текст PDF

Аннотация

Работа посвящена изучению предельно монотонных множеств, а также исследованию основных структурных свойств предельно монотонной сводимости (lm-сводимости) между множеством и последовательностью множеств. Предельно монотонную сводимость можно рассматривать как частный случай Σ-сводимости, определенной на семействах начальных сегментов натуральных чисел. В настоящей работе lm-сводимость между множеством и последовательностью, состоящей из бесконечных множеств, будет рассмотрена на языке предельно монотонного оператора. Основным результатом работы является доказательство отсутствия наименьшей не предельно монотонной последовательности относительно lm-сводимости между множеством и последовательностью множеств. Данный результат будет доказан с помощью метода приоритета с бесконечными нарушениями с использованием дерева стратегий. Результат, представленный в настоящей работы, является обобщением результата об отсутствии наименьшего Σ₂⁰-множества, не являющегося предельно монотонным, относительно lm-сводимости множеств.

Ключевые слова: предельно монотонная функция, предельно монотонное множество, предельно монотонный оператор, предельно монотонная сводимость, последовательность множеств, Σ₂⁰-множество

Благодарности. Работа выполнена за счет средств субсидии, выделенной Казанскому федеральному университету для выполнения государственного задания в сфере научной деятельности, проект № 1.1515.2017/4.6.

Литература

1. Хисамиев Н.Г. Критерий конструктивизируемости прямой суммы циклических p-групп // Изв. АН Казахской ССР. Сер. физ.-матем. – 1981. – Т. 98, № 1. – С. 51–55.

2. Khisamiev N.G. Arithmetic hierarchy of abelian groups // Sib. Math. J. – 1988. – V. 29, No 6. – P. 987–999. – doi: 10.1007/BF00972425.

3. Khisamiev N.G. Constructive abelian groups // Stud. Logic Found. Math. – 1998. – V. 139. – P. 1177–1231. – doi: 10.1016/S0049-237X(98)80050-5.

4. Downey R.G., Kach A.M., Turetsky D. Limitwise monotonic functions and their applications // Proc. 11th Asian Logic Conf. – 2011. – P. 59–85. – doi: 10.1142/9789814360548_0004.

5. Khoussainov B., Nies A., Shore R. Computable models of theories with few models // Notre Dame J. Formal Logic. – 1997. – V. 38, No 2. – P. 165–178. – doi: 10.1305/ndjfl/1039724885.

6. Kalimullin I., Khoussainov B., Melnikov A. Limitwise monotonic sequences and degree spectra of structures // Proc. Am. Math. Soc. – 2013. – V. 141, No 9. – P. 3275–3289. – doi: 10.1090/S0002-9939-2013-11586-8.

7. Kach A., Turetsky D. Limitwise monotonic functions, sets, and degrees on computable domains // J. Symb. Logic. – 2010. – V. 75, No 1. – P. 131–154. – doi: 10.2178/jsl/1264433912.

8. Зайнетдинов Д.Х., Калимуллин И.Ш. О предельно монотонной сводимости Σ₂⁰-множеств // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2014. – Т. 156, кн. 1. – С. 22–30.

9. Faizrahmanov M., Kalimullin I., Zainetdinov D. Maximality and minimality under limitwise monotonic reducibility // Lobachevskii J. Math. – 2014. – V. 35, No 4. – P. 333–338. – doi: 10.1134/S1995080214040155.

10. Зайнетдинов Д.Х. Предельно монотонная сводимость на множествах и парах множеств // Изв. вузов. Матем. – 2016. – № 3. – С. 97–101.

11. Goncharov S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R. Enumerations in computable structure theory // Ann. Pure Appl. Logic. – 2005. – V. 136, No 3. – P. 219–246. – doi: 10.1016/j.apal.2005.02.001.

12. Калимуллин И.Ш., Пузаренко В.Г. О сводимости на семействах // Алгебра и логика. – 2009. – Т. 48, № 1. – С. 31–53.

13. Зайнетдинов Д.Х. Σ-сводимость и lm-сводимость множеств и последовательностей множеств // Учен. зап. Казан. ун-та. Сер. Физ.-матем. науки. – 2016. – Т. 158, кн. 1. – С. 51–65.

Поступила в редакцию

24.12.17

Зайнетдинов Дамир Хабирович, кандидат физико-математических наук, младший научный сотрудник кафедры алгебры и математической логики

Казанский (Приволжский) федеральный университет

ул. Кремлевская, д. 18, г. Казань, 420008, Россия

E-mail:  damir.zh@mail.ru

Для цитирования: Зайнетдинов Д.Х. Структурные свойства предельно монотонной сводимости последовательностей множеств // Учен. зап. Казан. ун-та. Сер. Физ.- матем. науки. – 2018. – Т. 160, кн. 3. – С. 517–527. 

For citation: Zainetdinov D.Kh. Structural properties of limitwise monotonic reducibility of sequences of sets. Uchenye Zapiski Kazanskogo Universiteta. Seriya Fiziko-Matematicheskie Nauki, 2018, vol. 160, no. 3, pp. 517–527. (In Russian) 

Контент доступен под лицензией Creative Commons Attribution 4.0 License.