RUS  ENG
Полная версия
ЖУРНАЛЫ // Известия высших учебных заведений. Математика // Архив

Изв. вузов. Матем., 2024, номер 4, страницы 89–93 (Mi ivm9975)

Краткие сообщения

Неразрешимость одноместных PFP-операторов без вложения в теории одного следования

В. С. Секорин

Тверской государственный университет, ул. Желябова, д. 33, г. Тверь, 170100, Россия

Аннотация: В данной работе мы исследуем разрешимость расширений логики первого порядка. Например, в работах А. С. Золотова показано, что логика с унарным оператором транзитивного замыкания для теории следования является разрешимой. Мы показываем, что в аналогичной ситуации логика с унарным оператором частичной неподвижной точки разрешимой не является. Для этого мы сводим проблему остановки счетчиковой машины к проблеме истинности формулы. При этом используется только один оператор частичной неподвижной точки, он является унарным, невложенным и применяется к универсальной или экзистенциальной формуле.

Ключевые слова: логика первого порядка, частичная фиксированная точка, неразрешимость.

УДК: 510.624

Поступила: 11.01.2024
Исправленный вариант: 11.01.2024
Принята к публикации: 20.03.2024

DOI: 10.26907/0021-3446-2024-4-89-93



© МИАН, 2024