RUS  ENG
Полная версия
ЖУРНАЛЫ // Моделирование и анализ информационных систем // Архив

Модел. и анализ информ. систем, 2022, том 29, номер 2, страницы 104–114 (Mi mais770)

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



Реферативные базы данных:


© МИАН, 2024