Discrete mathematics in relation to computer science
Степени перечислимости ограниченных множеств
Б. Я. Солон Ивановский государственный университет, ул. Ермака, д.39, г. Иваново, 153025 Россия
Аннотация:
Термин «тотальная степень перечислимости» связан с тем, что
$e$-степень тотальна тогда и только тогда, когда она содержит график некоторой тотальной функции. В ряде работ автора и группы математиков из University of Wisconsin-Madison рассматривались так называемые «граф-кототальные степени перечислимости», т.е.
$e$-степени, содержащие дополнение графика некоторой тотальной функции
$f(x)$. В данной статье сделан следующий шаг – рассмотрены степени перечислимости множеств, ограниченных сверху или снизу графиком тотальной функции. Более точно, множество
$A$ ограничено сверху, если
$A=\{\langle x,y\rangle:y < f(x)\}$ для некоторой тотальной функции
$f(x)$ и множество
$A$ ограничено снизу, если
$A=\{\langle x,y\rangle:y > f(x)\}$ для некоторой тотальной функции
$f(x)$.
В статье приводится ряд результатов, показывающих существование нетотальных степеней перечислимости, содержащих ограниченные множества, причем построенные
$e$-степени являются квазиминимальными. Важным является результат, утверждающий, что ограниченные множества обладают свойством Фридберга, связанным с инверсией скачка.
Ключевые слова:
степени перечислимости, квазиминимальные степени перечислимости, ограниченные множества.
УДК:
510.676,
519.7
MSC: 03D25 Поступила в редакцию: 27.04.2022
Исправленный вариант: 23.05.2022
Принята в печать: 25.05.2022
DOI:
10.18255/1818-1015-2022-2-104-114