КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 24-11-00227
НазваниеЭффективно непрерывные отображения в математической логике и теории алгоритмов
Руководитель Калимуллин Искандер Шагитович, Доктор физико-математических наук
Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Казанский (Приволжский) федеральный университет" , Республика Татарстан (Татарстан)
Конкурс №92 - Конкурс 2024 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-101 - Математическая логика и основания математики
Ключевые слова Т0-пространства, пространства Ершова-Скотта, Н-собранные пространства, нумерованные семейства, алгоритмические сводимости
Код ГРНТИ27.03.19
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Проект направлен на изучение строения топологических Т0-пространств, которые возникают в различных разделах математической логики, алгебры и теории алгоритмов. В частности, проект предполагает исследование обобщений пространств Ершова-Скотта (в зарубежной литературе называемых также областями Скотта), нумерованных пространств, наделенных e-топологией, и других пространств, возникающих при изучении алгебраических структур и алгоритмических сводимостей. Кроме того, будут исследованы взаимосвязи этих пространств с пространствами их непрерывных функций, наделенных специальными топологиями, а также с ассоциированными с ними категориями, например, категориями нумерованных множеств, в которых морфизмы задаются m-операторами и операторами перечисления.
Пространства Ершова-Скотта имеют многочисленные приложения в теоретическом программировании и теории вычислимости. В частности, они послужили основой для построения моделей бестипового лямбда-исчисления. При этом построении ключевую роль сыграли пространства непрерывных функций, наделенные топологией поточечной сходимости. Сохранение свойств топологических Т0-пространств при переходе к пространствам непрерывных функций тесно связано и с понятием так называемой декартово замкнутой категории.
С помощью эффективно непрерывных отображений между нумерованными множествами, наделенными e-топологией, можно определить понятия их полноты и предполноты (которые можно определить также в категорных терминах, рассматривая нумерованные множества как объекты, а эффективно непрерывные отображения как морфизмы). Ключевое свойство (пред)полно нумерованных множеств заключается в справедливости в них теоремы Клини о рекурсии как без параметров, так и с ними. Они особо интенсивно изучаются последние два десятилетия специалистами из России, Казахстана, Италии, Сингапура, Нидерландов и т.д. К настоящему моменту опубликовано множество работ, посвященных такого вида нумерациям, в которых прослеживается программа их дальнейшего исследования. Помимо прочего, в проекте также предполагается получение продвижений в ее реализации.
Результаты, полученные в рамках проекта, будут иметь приложения не только в общей топологии, но и в теоретическом программировании, теории категорий, дискретной математике. Отметим также, что свойства и строение пространств непрерывных функций, наделенных той или иной топологией, активно изучаются в настоящее время специалистами из Германии, Китая, США.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Аннотация результатов, полученных в 2024 году
В рамках исследования вычислимой сводимости для бинарных отношений (на натуральных числах) изучались алгебраические и элементарные свойства для степенной структуры PR всех счетных предпорядков относительно вычислимой сводимости. Получен следующий результат.
ТЕОРЕМА. Множество степеней всех счетных эквивалентностей формульно определимо в степенной структуре PR. Отсюда вытекает, что элементарная теория для PR эквивалентна по Тьюрингу арифметике второго порядка.
В рамках исследований по теории алгоритмического распознавания (algorithmic learning theory) изучалась распознаваемость по тексту (TxtEx-распознаваемость) для классов счетных алгебраических структур. Получен следующий результат.
ТЕОРЕМА. Счетное семейство K cчетных алгебраических структур является распознаваемым по тексту в том и только том случае, когда существует счетное семейство S позитивных инфинитарных Sigma_2-предложений, такое, что каждая структура из K однозначно выделяется внутри класса K посредством некоторой формулы из семейства S.
Получены критерии невычислимости и высокости в.п. множеств:
- вычислимость произвольного в.п. множества A равносильна каждому из следующих двух условий:
(a) множество неподвижных точек любой A-вычислимой функции в стандартной геделевской нумерации {W_e} семейства всех в.п. множеств неиммунно,
(b) множество неподвижных точек любой A-вычислимой функции в произвольной предполной нумерации неиммунно;
- в.п. множество A не является высоким тогда и только тогда, когда
(c) для любой A-вычислимой функции f либо существует n такое, что оба множества W_f(n) и W_n пустые, либо существует вычислимое множество C, не содержащее x, для которых W_x пусто, но содержащее бесконечно много n, для которых W_f(n) = W_n; это условие, в свою очередь, равносильно условию
(d) для любой полной относительно некоторого вычислимого множества B вычислимой нумерации v и любой A-вычислимой функции f либо существует n такое, что v(f(n)) = v(n) = B, либо существует вычислимое множество C, не содержащее x, для которых v(x) = B, но содержащее бесконечно много n, для которых v(f(n)) = v(n).
Доказано совместное обобщение критерия полноты Арсланова и AND-теоремы Виссера в произвольной предполной нумерации: для любых предполной нумерации v, неполного по Тьюрингу в.п. множества A, частично A-вычислимой функции d, такой, что для всех n из области ее определения элементы v(d(n)) и v(n) различны, и для любой частично вычислимой функции p существует такая вычислимая функция f, что
(a) v(f(n)) = v(p(n)) для всех n из области определения p,
(b) значение d(f(n)) не определено для всех остальных n.
Установлено, что если размерность относительно пополнений в конструктивном метрическом пространстве всех вычислимых вещественных чисел семейства множеств вещественных чисел F конечна, то F обладает вычислимой нумерацией, полной относительно каждого своего элемента, у которого пополнение является наименьшим по включению элементом множества пополнений всех элементов F.
Была проведена классификация степеней по перечислимости алгебраихческих структур в терминах дихотомии непрерывных степеней и элементов К-пар. Установлено, что наиболее трудным случаем для дальнейших исследований являются именно K-пары, на которых и проявляются известные ранее неравномерности в сводимостях частичных представлений алгебраических структур.
ТЕОРЕМА. Если (A,B) – К-пара неперечислимых множеств (то есть декартов квадрат A и B содержится в перечислимом множестве W, а декартов квадрат дополнений A и B содержится в дополнении W), то существует семейство перечислимых множеств (а значит и некоторая алгебраическая структура), имеющее представление во всех степенях по перечислимости не ниже A, но единого оператора по перечислимости, осуществляющее такое представление, не существует.
Построено подпространство конструктивного метрического пространства всех вычислимых вещественных чисел, которое является полным относительно каждого элемента некоторого Pi-0-1-класса ненулевой (равномерной вероятностной) меры (в канторовском пространстве), но не является полным. Для его инвариантных подпространств M была доказано, что если M является полным относительно каждого элемента непустого Pi-0-1-класса или класса меры 1, то M является полным.
Было исследовано понятие обобщенной собранности топологических Т0-пространств, а также обобщенные собрификации таких пространств. Было доказано, что для аппроксимационных пространств Ершова-Скотта обобщенные собрификации гомеоморфны пространствам базисных Н-идеалов. Помимо этого, были найдены Н-ранги аппроксимационных пространств, а также условия, при выполнении которых различные обобщенные аппроксимации гомеоморфны.
Публикации
1.
Баженов Н.А., Фокина Е.Б., Россеггер Д., Соскова А., Ватев С.
Learning Families of Algebraic Structures from Text
Lecture Notes in Computer Science ((LNCS, volume 14773)) Twenty Years of Theoretical and Practical Synergies (CiE 2024), Bazhenov N., Fokina E., Rossegger D., Soskova A., Vatev S. (2024). Learning Families of Algebraic Structures from Text. In: Levy Patey, L., Pimentel, E., Galeotti, L., Manea, F. (eds) Twenty Years of Theoretical and Practical Synergies. CiE 2024. Lecture Notes in Computer Science, vol 14773., pp. 166-178, Springer, Cham. https://doi.org/10.1007/978-3-031-64309-5_14 (год публикации - 2024)
10.1007/978-3-031-64309-5_14
2.
Файзрахманов М.Х.
О полных и почти полных конструктивных метрических пространствах
Вестник Московского университета. Серия 1. Математика. Механика, М. Х. Файзрахманов, “О полных и почти полных конструктивных метрических пространствах”, Вестн. Моск. ун-та. Сер. 1. Матем., мех., 2025, № 3, 31–38; Moscow University Mathematics Bulletin, 80:3 (2025), 184–191 (год публикации - 2025)
10.55959/MSU0579-9368-1-66-3-5
3.
Кудряшова М.И., Швидефски М.В.
To the theory of H-sober spaces. II
Lobachevskii Journal of Mathematics, Pleiades Publiching, USA, Kudryashova, M.I., Schwidefsky, M.V. To the Theory of Sober Spaces: II. Approximation Spaces. Lobachevskii J Math 46, 1871–1878 (2025) (год публикации - 2025)
10.1134/S1995080225606149
4.
Файзрахманов М.Х.
Теоремы непрерывности для одного класса вычислимых операторов
Математические заметки, М. Х. Файзрахманов, “Теоремы непрерывности для одного класса вычислимых операторов”, Матем. заметки, 117:4 (2025), 591–599; Math. Notes, 117:4 (2025), 643–649 (год публикации - 2025)
10.4213/mzm14387
Аннотация результатов, полученных в 2025 году
В рамках исследований особенностей распределения вычислимых нумераций семейств вычислимо перечислимых множеств и частично вычислимых функций, принадлежащих классам нумераций, удовлетворяющих разным формам теоремы о неподвижной точке, были получены следующие результаты.
(1) Установлена эффективная бесконечность классов полных и предполных нумераций, а также нумераций, удовлетворяющих теореме о неподвижной точке, семейств всех в.п. множеств и всех ч.в. функций.
(2) Установлена эффективная бесконечность класса непредполных нумераций, удовлетворяющих теореме о неподвижной точке, семейств всех в.п. множеств и всех ч.в. функций.
(3) Получен критерий эффективной бесконечности классов нумераций, удовлетворяющих теореме о неподвижной точке, конечных семейств в.п. множеств.
(4) Построено вычислимое семейство, для которого классы его полных и предполных нумераций являются бесконечными, но не эффективно бесконечными.
(5) Доказан критерий m-полноты множеств в терминах диагонально невычислимых функций.
(6) Построен контрпример, показывающий, что критерий полноты Арсланова не имеет места для линейной сводимости.
В рамках исследования степеней по перечислимости частичных представлений алгебраических структур были найдены новые примеры сводимостей частичных представлений, не исчерпывающиеся Sigma-операторами.
В рамках исследований теории распознавания для семейств счетных алгебраических структур получены критерии для распознаваемости по информанту для некоторых классических парадигм распознаваемости. В частности, установлен следующий результат – счетное семейство счетных алгебраических структур K является частично распознаваемым в том и только том случае, когда множество инфинитарных Sigma_2-теорий структур из класса K является антицепью относительно включения.
В рамках исследований теории вычислимости для Т0-пространств были получены следующие результаты.
(1) Для любого оракула Z категория Z-вычислимо перечислимых дистрибутивных c-частично упорядоченных множеств и категория Z-вычислимо перечислимых почти полуспектральных пространств с базой дуально эквивалентны.
(2) Для любого оракула Z категория Z-вычислимых дистрибутивных решеток и категория Z-вычислимых почти спектральных пространств с базой дуально эквивалентны.
(3) Предложены новые конструкции для получения пополнений Т0-пространств, основанные на понятии идеала ч.у. множества и топологического пространства.
(4) Исследованы свойства ретрактов (проекций) Т0-пространств с аппроксимациями.
(5) Установлено сохранение ряда свойств топологических пространств при переходе к обобщенным собрификациям и пространствам непрерывных функций, наделенных разными топологиями.
Публикации
1. Баженов Н.А., Калимуллин И.Ш., Швидефски М.В. A Computable Stone Duality Алгебра и логика (год публикации - 2026)
2.
Файзрахманов М.Х.
Notes on classes of minimal numberings of arithmetical set families
Lobachevskii Journal of Mathematics, Lobachevskii Journal of Mathematics, 2025, Vol. 46, No. 4, pp. 1904–1911. (год публикации - 2025)
10.1134/S1995080225606125
3.
Файзрахманов М.Х., Щедрикова З.К.
Свойства непрерывности конструктивных операторов на вычислимо перечислимых вещественных числах
Математические труды, Файзрахманов М.Х., Щедрикова З.К. Свойства непрерывности конструктивных операторов на вычислимо перечислимых вещественных числах // Математические труды. - 2025. -V. 28, №4. - C. 158–173 (год публикации - 2025)
10.25205/1560-750X-2025-28-4-158-173
4. Файзрахманов М.Х. Some properties of constructive functions on the quasireals Journal of Logic and Analysis (год публикации - 2026)
5.
Баженов Н.А., Чиприани В., Джайн С., Сан Мауро Л., Стефан Ф.
Classifying different criteria for learning algebraic structures
Annals of Pure and Applied Logic, Volume 177, Issue 1, January 2026, 103648 (год публикации - 2026)
10.1016/j.apal.2025.103648
6.
Файзрахманов М.Х.
Computable operators on left–c.e. reals and their continuity properties
Logic Journal of the IGPL, Vol.33, No.3 (год публикации - 2025)
10.1093/jigpal/jzaf011
7.
Файзрахманов М.Х.
Один подход к классификации минимальных нумераций семейств арифметических множеств
Сибирский математический журнал, Том 66, № 2, стр. 330-338 (год публикации - 2025)
10.33048/smzh.2025.66.214
8.
Баженов Н.А., Калмурзаев Б., Нг К.М., Нурланбек Д.
On cardinalities of Rogers semilattices for families in the Ershov hierarchy
Information and Computation, Volume 307, November 2025, 105354 (год публикации - 2025)
10.1016/j.ic.2025.105354
9.
Файзрахманов М.Х.
Control Structures in Computable Numberings and the Completion Operator
Theory of Computing Systems, Volume 69, article number 21, (2025) (год публикации - 2025)
10.1007/s00224-025-10222-1
10. Калимуллин И.Ш. Об алгоритмических преобразованиях частичных порядков в линейно упорядоченные структуры Алгебра и логика (год публикации - 2025)