НИС "Современные проблемы математической логики" в ВШЭ. Дата и время: 17.01.2025 в 16:20 Докладчик: Тихон Пшеницын Название: Введение в гиперарифметическую иерархию Аннотация: Многим известна арифметическая иерархия, которая классифицирует неразрешимые множества, задаваемые арифметическими формулами первого порядка. Также на слуху аналитическая иерархия, определяемая аналогичным образом с помощью логики второго порядка. Однако менее популярна гиперарифметическая иерархия, которая заполняет пробел между арифметической и аналитической иерархиями. В гиперарифметической иерархии определяются уровни ^0_ и ^0_ не только для натуральных , но и для всех конструктивных ординалов. Мы начнем с аккуратного введения гиперарифметической иерархии, обсудим ее основные свойства. Будет приведен пример ^0_-полного множества вычислимых инфинитарных формул в простейшем языке (эти формулы строятся из констант "истина" и "ложь" с помощью вычислимых конъюнкций и дизъюнкций). После этого будет приведено несколько примеров логик, задача выводимости в которых имеет гиперарифметический уровень сложности (эти результаты получены в работах С.Л. Кузнецова, С.О. Сперанского и докладчика, в том числе в соавторстве).
