Аннотация:
Понятие доказуемо тотальной (то есть, всюду определенной) вычислимой функции играет важную роль в теории доказательств. Сопоставляя каждому тотальному алгоритму арифметическое утверждение о его тотальности, на множестве всех таких алгоритмов/утверждений можно естественным образом ввести отношение сводимости: f сводится к g, если из тотальности g следует тотальность f (в рамках данной арифметической теории).
В докладе будет дан обзор результатов о соответствующей структуре степеней, а также продемонстрированы основные методы построения степеней с заданными свойствами. Будут рассмотрены как аналоги результатов, относящихся к структуре тьюринговых степеней (теоремы о плотности, высокие и низкие степени, теоремы об обращении скачка и другие), так и результаты, специфичные для решёток арифметических предложений (операторы непротиворечивости и “недоказуемости”, и другие).
|
