Семейство с единственной минимальной, но не наименьшей нумерацией

Семейство с единственной минимальной, но не наименьшей нумерацией

Файзрахманов М. Х.

УДК 510.5 
DOI: 10.33048/smzh.2024.65.212


Аннотация:

Доказывается существование семейства вычислимо перечислимых множеств, обладающего единственной с точностью до эквивалентности вычислимой минимальной, но не наименьшей нумерацией.

Литература:
  1. Badaev S. A., Goncharov S. S. On computable minimal enumerations // Algebra. Proc. third Int. Conf. Algebra, memory M. I. Kargopolov. Berlin; New York: Walter de Gruyter, 1995. P. 21–32.
     
  2. Badaev S. A., Goncharov S. S. Theory of numberings: open problems // Computability theory and its applications, P. Cholak (ed.) et al. Providence, RI: Am. Math. Soc., 2000. P. 23–38. (Contemp. Math. 257).
     
  3. Марченков С. С. О вычислимых нумерациях семейств общерекурсивных функций // Алгебра и логика. 1972. Т. 11, № 5. С. 588–607.
     
  4. Гончаров С. С. Вычислимые однозначные нумерации // Алгебра и логика. 1980. Т. 19, № 5. С. 507–551.
     
  5. Гончаров С. С. Позитивные вычислимые нумерации // Докл. АН СССР. 1993. Т. 332, № 2. С. 142–143.
     
  6. Гончаров С. С. Семейство с единственной однозначной, но не наименьшей нумерацией // Тр. Ин-та математики. 1988. Т. 8. С. 42–58.
     
  7. Гончаров С. С. Семейства с единственной позитивной нумерацией // Вычисл. системы. 1992. № 146. С. 96–104.
     
  8. Goncharov S. S., Harizanov V., Knight J., McCoy C., Miller R., Solomon R. Enumerations in computable structure theory // Ann. Pure Appl. Logic. 2005. V. 136, N 3. P. 219–246.
     
  9. Hirschfeldt D. R. Degree spectra of relations on computable structures // Bull. Symb. Logic. 2000. V. 6, N 2. P. 197–212.
     
  10. Ершов Ю. Л. Теория нумераций. М.: Наука, 1977.
     
  11. Ершов Ю. Л. Нумерации семейств общерекурсивных функций // Сиб. мат. журн. 1967. Т. 8, № 5. С. 1015–1025.
     
  12. Semukhin P. Prime models of finite computable dimension // J. Symb. Logic. 2009. V. 74, N 1. P. 336–348.
     
  13. Бадаев С. А. Минимальные нумерации // Тр. Ин-та математики СО РАН. 1993. Т. 25. С. 3–34.
     
  14. Бадаев С. А. Минимальные нумерации позитивно вычислимых семейств // Алгебра и логика. 1994. Т. 33, № 3. С. 233–254.
     
  15. Вьюгин В. В. О некоторых примерах верхних полурешеток вычислимых нумераций // Алгебра и логика. 1973. Т. 12, № 5. С. 512–529.
     
  16. Goncharov S. S., Yakhnis A., Yakhnis V. Some effectively infinite classes of enumerations // Ann. Pure Appl. Logic. 1993. V. 60, N 3. P. 207–235.
     
  17. Гончаров С. С., Сорби А. Обобщенно-вычислимые нумерации и нетривиальные полурешетки Роджерс // Алгебра и логика. 1997. Т. 36, № 6. С. 621–641.
     
  18. Бадаев С. А., Гончаров С. С. О полурешетках Роджерса семейств арифметических множеств // Алгебра и логика. 2001. Т. 40, № 5. С. 507–522.
     
  19. Badaev S. A., Lempp S. A decomposition of the Rogers semilattice of a family of d.c.e. sets // J. Symb. Logic. 2009. V. 74, N 2. P. 618–640.
     
  20. Файзрахманов М. Х. Минимальные обобщенно вычислимые нумерации и высокие степени // Сиб. мат. журн. 2017. Т. 58, № 3. С. 710–716.
     
  21. Faizrahmanov M. Kh. Extremal numberings and fixed point theorems // Math. Logic Quart. 2022. V. 68, N 4. P. 398–408.
     
  22. Файзрахманов М. Х. Две теоремы о минимальных обобщенно-вычислимых нумерациях // Вестн. Моск. ун-та. Сер. 1. Математика, механика. 2023. № 3. С. 28–35.
     
  23. Файзрахманов М. Х. О p-универсальных и p-минимальных нумерациях // Сиб. мат. журн. 2022. Т. 63, № 2. С. 440–449.
     
  24. Файзрахманов М. Х. Сводимость по перечислимости и позитивная сводимость нумераций семейств арифметических множеств // Сиб. мат. журн. 2023. Т. 64, № 1. С. 204–212.
     
  25. Ershov Yu. L. Theory of numberings // E. R. Griffor (ed.), Handbook of computability theory. Amsterdam: Elsevier, 1999. P. 473–503. (Stud. Logic Found. Math.; V. 140).
     
  26. Soare R. I. Recursively enumerable sets and degrees. A study of computable functions and computably generated sets. Perspectives in mathematical logic. Berlin; Heidelberg; New York, etc.: Springer-Verl., 1987.
     
  27. Soare R. I. Turing computability: theory and applications (theory and applications of computability). Berlin: Springer, 2016.

Работа поддержана грантом Российского научного фонда (проект № 23-21-00181) и выполнена в рамках реализации программы развития Научно-образовательного математического центра Приволжского федерального округа (соглашение № 075-02-2023-944).


Файзрахманов Марат Хайдарович (ORCID 0000-0002-4519-9696)
  1. Казанский (Приволжский) федеральный университет,
    ул. Кремлевская, 18, Казань 420008

E-mail: marat.faizrahmanov@gmail.com

Статья поступила 27 апреля 2023 г.
После доработки — 1 октября 2023 г.
Принята к публикации 28 января 2024 г.