СЕМЕЙСТВА ПЕРЕСТАНОВОК И ИДЕАЛЫ ТЬЮРИНГОВЫХ СТЕПЕНЕЙ (2022)
Изучаются семейства PI, состоящие из перестановок натурального ряда ω, степени которых принадлежат идеалу тьюринговых степеней I, и их скачки P′I. Для любого счётного тьюрингова идеала I приводятся описания спектров степеней семейств PI и их скачков P′I. Для некоторых идеалов I, порождённых в. п. степенями, определяются спектры семейств PI.
Идентификаторы и классификаторы
- Префикс DOI
- 10.33048/alglog.2022.61.603
- eLIBRARY ID
- 54693357
Согласно классическому результату К. Джокуша [1], см. также [2, гл. XII, теор. 3.4], семейство всех вычислимых функций, как и семейство всех вычислимых перестановок, см. предложение 1, является aвычислимым тогда и только тогда, когда тьюрингова степень a — высокaя (0 ′′ 6 a ′ ). Как обычно, процитированный результат допускает релятивизацию. Она позволяет охарактеризовать классы степеней, вычисляющих семейства всех перестановок, степени которых принадлежат главным тьюринговым идеалам. Как следует из результатов работы [3], классический объект теории вычислимости — группа Ga всех a-вычислимых перестановок натурального ряда ω — имеет изоморфные x-вычислимые копии в точности для тех степеней x, для которых a ′′ 6 x. Отсюда следует, что классы скачков степеней, вычисляющих семейство всех a-вычислимых перестановок, и степеней, вычисляющих изоморфные копии группы Ga, совпадают. Настоящая работа имеет целью прояснение особенностей строения спектров групп перестановок, степени которых принадлежат произвольному (необязательно главному) тьюринговому идеалу I, с помощью скачков семейств перестановок, чьи степени также принадлежат I.
Список литературы
1. | C. G. Jockusch, jun., Degrees in which the recursive sets are uniformly recursive, Can. J. Math., 24, No. 6 (1972), 1092-1099. | |
---|---|---|
2. | R. I. Soare, Recursively enumerable sets and degrees. A study of computable functions and computably generated sets (Perspect. Math. Log., Omega Series), Berlin etc., Springer-Verlag, 1987. | |
3. | Р. И. Соар, Вычислимо перечислимые множества и степени. Изучение вычислимых функций и вычислимо перечислимых множеств, Казань, Казанское матем. об-во, 2000. | |
4. | А. С. Морозов, Перестановки и неявная определимость, Алгебра и логика, 27, № 1 (1988), 19-36. EDN: CYHPXT | |
5. | И. Ш. Калимуллин, В. Г. Пузаренко, О сводимости на семействах, Алгебра и логика, 48, № 1 (2009), 31-53. EDN: KAJKCX | |
6. | В. А. Руднев, О существовании неотделимой пары в рекурсивной теории допустимых множеств, Алгебра и логика, 27, N 1 (1988), 48-56. | |
7. | А. С. Морозов, В. Г. Пузаренко, О S-подмножествах натуральных чисел, Алгебра и логика, 43, № 3 (2004), 291-320. EDN: HRTEXJ | |
8. | A. Montalban, Computable structure theory. Within the arithmetic (Perspect. Log.), Cambridge, Cambridge Univ. Press; Urbana, IL, Assoc. Symb. Log. (ASL), 2021. | |
9. | L. J. Richter, Degrees of structures, J. Symb. Log., 46, No. 4 (1981), 723-731. | |
10. | В. Г. Пузаренко, Об одной сводимости на допустимых множествах, Сиб. матем. ж., 50, № 2 (2009), 415-429. EDN: KXEYNF | |
11. | V. Baleva, The jump operation for structure degrees, Arch. Math. Logic, 45, No. 3 (2006), 249-265. EDN: YHDEVY | |
12. | A. Montalbaan, Notes on the jump of a structure, in: K. Ambos-Spies (ed.) et al., Mathematical theory and computational practice. 5th conf. on computability in Europe (CiE 2009, Heidelberg, Germany, July 19-24, 2009), Proc. (Lect. Notes Comput. Sci., 5635), Berlin, Springer-Verlag, 2009, 372-378. | |
13. | A. A. Soskova, I. N. Soskov, A jump inversion theorem for the degree spectra, J. Log.Comput., 19, No. 1 (2009), 199-215. EDN: GQNSZE | |
14. | В. Г. Пузаренко, Неподвижные точки оператора скачка, Алгебра и логика, 50, № 5 (2011), 615-646. EDN: OJZXTT | |
15. | Ю. Л. Ершов, Определимость и вычислимость (Сибирская школа алгебры и логики), Новосибирск, Науч. кн., М., Экономика, 2-е изд., испр. и доп., 2000. | |
16. | J. Barwise, Admissible sets and structures. An approach to definability theory (Perspec. Math. Log.), Reprint of the 1975 original published by Springer, Cambridge, Cambridge Univ. Press; Urbana, IL, Assoc. Symb. Log. (ASL), 2016. | |
17. | Yu. L. Ershov, V. G. Puzarenko, A. I. Stukachev, HF-Computability, in: S. B. Cooper (ed.), Computability in context.Computation and logic in the real world, London, World Scientific, 2011, 173-248. EDN: XFJDSB | |
18. | G. Barmpalias, A. Nies, Upper bounds on ideals in the computably enumerable Turing degrees, Ann. Pure Appl. Logic, 162, No. 6 (2011), 465-473. | |
19. | A. Nies, Computability and randomness, (Oxf. Logic Guides, 51), Oxford, Oxford Univ. Press, 2009. | |
20. | A. Nies, Lowness properties and randomness, Adv. Math., 197, No. 1 (2005), 274-305. EDN: LTSCYF | |
21. | K. M. Ng, On strongly jump traceable reals, Ann. Pure App. Logic, 154, No. 1 (2008), 51-69. | |
22. | D. Diamondstone, N. Greenberg, D. Turetsky, Inherent enumerability of strong jump-traceability, Trans. Am. Math. Soc., 367, No. 3 (2015), 1771-1796. | |
23. | S. Schwarz, Index sets related to prompt simplicity, Ann. Pure App. Logic, 42, No. 3 (1989), 243-254. |
Выпуск
Другие статьи выпуска
Понятие P-стабильности является частным случаем обобщённой стабильности полных теорий. Изучаются инъективные S-полигоны с P-стабильной теорией. Доказывается, что класс инъективных S-полигонов (P,1)-стабилен только в том случае, когда моноид S одноэлементен. Кроме того, описываются коммутативные и линейно упорядоченные моноиды S, класс инъективных S-полигонов над которыми (P,s)-, (P,a)- и (P,e)-стабилен.
Генерические алгоритмы решают проблемы на множествах почти всех входов, выдавая неопределённый ответ для остальных редких входов. В статье доказывается, что проблема равенства генерически разрешима в конечно порождённых полугруппах S, для которых существует такая конгруэнция θ, что полугруппа S/θ является бесконечным финитно аппроксимируемым моноидом с сокращениями и с разрешимой проблемой равенства. Это обобщает ранее полученный результат автора о генерической разрешимости проблемы равенства в конечно определённых полугруппах, которые остаются бесконечными при добавлении свойств коммутативности и сокращения. Отметим, что примерами таких полугрупп служат полугруппы с одним определяющим соотношением, а также так называемые сбалансированные полугруппы, для которых Вон доказал генерическую разрешимость проблемы равенства. В частности, сбалансированными являются классические полугруппы Цейтина и Маканина с неразрешимой проблемой равенства.
Доказывается, что сингулярная супералгебра с 2-мерной чётной частью изоморфна супералгебре B2∣3(φ,ξ,ψ). В частности, не существует бесконечномерных простых сингулярных супералгебр с 2-мерной чётной частью. Доказывается, что если сингулярная супералгебра содержит нечётный левый аннулятор, то она содержит невырожденный переключатель. Наконец, устанавливается, что для любого числа N≥5, за исключением чисел 6,7,8,11, существуют сингулярные супералгебры с переключателем размерности N. Для чисел N=6,7,8,11 не существует сингулярных N-мерных супералгебр с переключателем. |
---|
Рассматривается совместная логика задач и высказываний QHC, введённая С. А. Мелиховым, а также интуиционистская модальная логика QH4. Рассмотрено погружение этих логик в классическую логику предикатов первого порядка. Установлен аналог теоремы Лёвенгейма-Сколема о счётной элементарной подмодели для логик QHC и QH4.
Рассматривается класс обобщённых дифференцирований, возникающий в связи с задачей присоединения единицы к алгебре с обобщённым дифференцированием, а также поиска обёртывающих для алгебр Новикова-Пуассона. Приводятся условия существования локализации алгебры с тернарным дифференцированием, а также условия, при которых по алгебре с тернарным дифференцированием можно построить алгебру Новикова-Пуассона и Йорданову супералгебру. И наконец, показывается, как простота алгебры с обобщённым дифференцированием по Брешару связана с простотой соответствующей алгебры Новикова.
Ранее К. Дошен и М. Божич ввели четыре независимые интуиционистские модальные логики - по одной для каждого из четырёх типов модальных операторов: необходимости N, возможности P, невозможности Im и не-необходимости Un. Эти логики обозначаются HKM, где M∈{N,P,Un,Im}. Интерес к тому, чтобы рассматривать четыре типа модальных операторов по отдельности, связан именно с тем, что над интуиционистской логикой они не могут быть сведены друг к другу. Здесь изучаются расширения логик HKM, у которых есть нормальные напарники. Оказывается, что нормальные напарники есть у всех расширений логик HKN и HKUn. Для расширений HKP и HKIm получен критерий существования нормальных напарников, который заключается в присутствии некоторого модального закона двойного отрицания. Также показывается, как добавление этого закона влияет на выразительные возможности логики. Особый интерес представляет результат о том, что расширения HKP и HKIm имеют нормальных напарников, только если они дефинициально эквивалентны расширениям HKN и HKUn соответственно. Этот результат является ещё одним примером различия в поведении четырёх типов модальных операторов над интуиционистской логикой.
Издательство
- Издательство
- НГУ
- Регион
- Россия, Новосибирск
- Почтовый адрес
- 630090, Новосибирская область, г. Новосибирск, ул. Пирогова, д. 1.
- Юр. адрес
- 630090, Новосибирская область, г. Новосибирск, ул. Пирогова, д. 1.
- ФИО
- Федорук Михаил Петрович (Руководитель)
- E-mail адрес
- rector@nsu.ru
- Контактный телефон
- +7 (383) 3634000
- Сайт
- https://www.nsu.ru/