<?xml version="1.0" encoding="UTF-8"?>
<!DOCTYPE article PUBLIC "-//NLM//DTD JATS (Z39.96) Journal Publishing DTD v1.3 20210610//EN" "JATS-journalpublishing1-3.dtd">
<article article-type="research-article" dtd-version="1.3" xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xml:lang="ru"><front><journal-meta><journal-id journal-id-type="publisher-id">mais</journal-id><journal-title-group><journal-title xml:lang="ru">Моделирование и анализ информационных систем</journal-title><trans-title-group xml:lang="en"><trans-title>Modeling and Analysis of Information Systems</trans-title></trans-title-group></journal-title-group><issn pub-type="ppub">1818-1015</issn><issn pub-type="epub">2313-5417</issn><publisher><publisher-name>Yaroslavl State University</publisher-name></publisher></journal-meta><article-meta><article-id pub-id-type="doi">10.18255/1818-1015-2022-2-104-114</article-id><article-id custom-type="elpub" pub-id-type="custom">mais-1649</article-id><article-categories><subj-group subj-group-type="heading"><subject>Research Article</subject></subj-group><subj-group subj-group-type="section-heading" xml:lang="ru"><subject>Discrete Mathematics in Relation to Computer Science</subject></subj-group></article-categories><title-group><article-title>Степени перечислимости ограниченных множеств</article-title><trans-title-group xml:lang="en"><trans-title>Enumeration Degrees of the Bounded Sets</trans-title></trans-title-group></title-group><contrib-group><contrib contrib-type="author" corresp="yes"><name-alternatives><name name-style="eastern" xml:lang="ru"><surname>Солон</surname><given-names>Борис Яковлевич</given-names></name><name name-style="western" xml:lang="en"><surname>Solon</surname><given-names>Boris Y.</given-names></name></name-alternatives><email xlink:type="simple">bysolon@gmail.com</email><xref ref-type="aff" rid="aff-1"/></contrib></contrib-group><aff-alternatives id="aff-1"><aff xml:lang="ru"><institution>Ивановский государственный университет</institution><country>Россия</country></aff><aff xml:lang="en"><institution>Ivanovo State University</institution><country>Russian Federation</country></aff></aff-alternatives><pub-date pub-type="collection"><year>2022</year></pub-date><pub-date pub-type="epub"><day>17</day><month>06</month><year>2022</year></pub-date><volume>29</volume><issue>2</issue><fpage>104</fpage><lpage>114</lpage><permissions><copyright-statement>Copyright &amp;#x00A9; Солон Б.Я., 2022</copyright-statement><copyright-year>2022</copyright-year><copyright-holder xml:lang="ru">Солон Б.Я.</copyright-holder><copyright-holder xml:lang="en">Solon B.Y.</copyright-holder><license xml:lang="ru" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>Данная работа распространяется под лицензией Creative Commons Attribution 4.0.</license-p></license><license xml:lang="en" license-type="creative-commons-attribution" xlink:href="https://creativecommons.org/licenses/by/4.0/" xlink:type="simple"><license-p>This work is licensed under a Creative Commons Attribution 4.0 License.</license-p></license></permissions><self-uri xlink:href="https://www.mais-journal.ru/jour/article/view/1649">https://www.mais-journal.ru/jour/article/view/1649</self-uri><abstract><p>Термин &lt;&lt;тотальная степень перечислимости&gt;&gt; связан с тем, что е-степень тотальна тогда и только тогда, когда она содержит график некоторой тотальной функции. В ряде работ автора и группы математиков из University of Wisconsin-Madison рассматривались так называемые &lt;&lt;граф-кототальные степени перечислимости&gt;&gt;, т.е. е-степени, содержащие дополнение графика некоторой тотальной функции $f(x)$. В данной статье сделан следующий шаг -- рассмотрены степени перечислимости множеств, ограниченных сверху или снизу графиком тотальной функции. Более точно, множество A ограничено сверху, если $A=\\{\\langle x,y\\rangle:y &lt; f(x)\\}$ для некоторой тотальной функции f(x) и множество A ограничено снизу, если $A=\\{\\langle x,y\\rangle:y &gt; f(x)\\}$ для некоторой тотальной функции $f(x)$. В статье приводится ряд результатов, показывающих существование нетотальных степеней перечислимости, содержащих ограниченные множества, причем построенные е-степени являются квазиминимальными. Важным является результат, утверждающий, что ограниченные множества обладают свойством Фридберга, связанным с~инверсией скачка.</p></abstract><trans-abstract xml:lang="en"><p>The term ``total enumeration degree'' is related to the fact that the e-degree is total if and only if  it contains a graph of some total function. In a number of works by the author and a group of mathematicians from the University of Wisconsin-Madison, the so-called ``graph-cototal enumeration degrees'' were considered, i.e. e-degrees containing the complement of the graph of some total function $f(x)$. In this article, the next step is taken -- the enumeration degrees of sets bounded from above or below by a graph of a total function are considered. More precisely, the set A is bounded from above if $A=\\{\\langle x,y\\rangle:y &lt; f(x)\\}$ for some total function $f(x)$ and the set A is bounded from below if $A=\\{\\langle x,y\\rangle:y &gt; f(x)\\}$ for some total function $f(x)$. The article presents a number of results showing the existence of nontotal enumeration degrees containing bounded sets, and the constructed e-degrees are quasi-minimal. An important result is the one stating that bounded sets have the Friedberg property related to the jump inversion.</p></trans-abstract><kwd-group xml:lang="ru"><kwd>степени перечислимости</kwd><kwd>квазиминимальные степени перечислимости</kwd><kwd>ограниченные множества</kwd></kwd-group><kwd-group xml:lang="en"><kwd>enumeration degrees</kwd><kwd>quasi-minimal enumeration degrees</kwd><kwd>bounded sets</kwd></kwd-group></article-meta></front><back><ref-list><title>References</title><ref id="cit1"><label>1</label><citation-alternatives><mixed-citation xml:lang="ru">U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova, and M. Soskova, “On cototality and the skip operator in the enumeration degrees”, Transactions of the American Mathematical Society, vol. 372, no. 3, pp. 1631-1670, 2019.</mixed-citation><mixed-citation xml:lang="en">U. Andrews, H. Ganchev, R. Kuyper, S. Lempp, J. Miller, A. Soskova, and M. Soskova, “On cototality and the skip operator in the enumeration degrees”, Transactions of the American Mathematical Society, vol. 372, no. 3, pp. 1631-1670, 2019.</mixed-citation></citation-alternatives></ref><ref id="cit2"><label>2</label><citation-alternatives><mixed-citation xml:lang="ru">B. Solon and S. Rozhkov, “Enumeration degrees of the bounded total sets”, in International Conference on Theory and Applications of Models of Computation, Springer, 2006, pp. 737-745.</mixed-citation><mixed-citation xml:lang="en">B. Solon and S. Rozhkov, “Enumeration degrees of the bounded total sets”, in International Conference on Theory and Applications of Models of Computation, Springer, 2006, pp. 737-745.</mixed-citation></citation-alternatives></ref><ref id="cit3"><label>3</label><citation-alternatives><mixed-citation xml:lang="ru">S. Rozhkov, “Properties of e-degrees of the bounded total sets”, Automatic Control and Computer Sciences, vol. 44, no. 7, pp. 452-454, 2010.</mixed-citation><mixed-citation xml:lang="en">S. Rozhkov, “Properties of e-degrees of the bounded total sets”, Automatic Control and Computer Sciences, vol. 44, no. 7, pp. 452-454, 2010.</mixed-citation></citation-alternatives></ref><ref id="cit4"><label>4</label><citation-alternatives><mixed-citation xml:lang="ru">H. Rogers Jr, Theory of recursive functions and elfective computability. New York: McGraw-Hill, 1967.</mixed-citation><mixed-citation xml:lang="en">H. Rogers Jr, Theory of recursive functions and elfective computability. New York: McGraw-Hill, 1967.</mixed-citation></citation-alternatives></ref><ref id="cit5"><label>5</label><citation-alternatives><mixed-citation xml:lang="ru">M. G. Rosinas, “Chastichnie stepeni i r-stepeni”, Siberian Mathematical Journal, vol. 15, no. 6, pp. 1323-1331, 1974.</mixed-citation><mixed-citation xml:lang="en">M. G. Rosinas, “Chastichnie stepeni i r-stepeni”, Siberian Mathematical Journal, vol. 15, no. 6, pp. 1323-1331, 1974.</mixed-citation></citation-alternatives></ref><ref id="cit6"><label>6</label><citation-alternatives><mixed-citation xml:lang="ru">S. B. Cooper, “Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense”, The Journal of symbolic logic, vol. 49, no. 2, pp. 503-513, 1984.</mixed-citation><mixed-citation xml:lang="en">S. B. Cooper, “Partial degrees and the density problem. Part 2: The enumeration degrees of the Σ2 sets are dense”, The Journal of symbolic logic, vol. 49, no. 2, pp. 503-513, 1984.</mixed-citation></citation-alternatives></ref><ref id="cit7"><label>7</label><citation-alternatives><mixed-citation xml:lang="ru">M. G. Rosinas, “Operacia skachka dlja nekotorih vidov svodimosti”, VINITI Dep, pp. 3185-76,</mixed-citation><mixed-citation xml:lang="en">M. G. Rosinas, “Operacia skachka dlja nekotorih vidov svodimosti”, VINITI Dep, pp. 3185-76,</mixed-citation></citation-alternatives></ref><ref id="cit8"><label>8</label><citation-alternatives><mixed-citation xml:lang="ru">K. McEvoy, “Jumps of quasi-minimal enumeration degrees”, The Journal of symbolic logic, vol. 50, no. 3, pp. 839-848, 1985.</mixed-citation><mixed-citation xml:lang="en">K. McEvoy, “Jumps of quasi-minimal enumeration degrees”, The Journal of symbolic logic, vol. 50, no. 3, pp. 839-848, 1985.</mixed-citation></citation-alternatives></ref><ref id="cit9"><label>9</label><citation-alternatives><mixed-citation xml:lang="ru">J. Case, “Enumeration reducibility and partial degrees”, Annals of mathematical logic, vol. 2, no. 4, pp. 419-439, 1971.</mixed-citation><mixed-citation xml:lang="en">J. Case, “Enumeration reducibility and partial degrees”, Annals of mathematical logic, vol. 2, no. 4, pp. 419-439, 1971.</mixed-citation></citation-alternatives></ref></ref-list><fn-group><fn fn-type="conflict"><p>The authors declare that there are no conflicts of interest present.</p></fn></fn-group></back></article>
