RUS  ENG
Полная версия
ЖУРНАЛЫ // Алгебра и логика // Архив

Алгебра и логика, 1990, том 29, номер 4, страницы 421–429 (Mi al2113)

Эта публикация цитируется в 3 статьях

Слабые комбинаторно-селекторные свойства подмножеств натуральных чисел

А. Н. Дёгтев


Аннотация: Пусть $A\subseteq N$ и $\beta$ — $n$-местная булева функция. Назовем $A$ слабо $\beta$-селекторным множеством, если существует $n$-местная ЧРФ $f$ такая, что выполнены следующие условия:
(а) $(\forall x_1,\dots, x_n)(f(x_1,\dots, x_n)\downarrow\Rightarrow f(x_1,\dots, x_n)\in\{x_1,\dots, x_n\})$;
(б) $(\forall x_1,\dots, x_n)(x_1,\dots, x_n\in A\Rightarrow f(x_1,\dots, x_n)\downarrow)$;
(c) $(\forall x_1,\dots, x_n)(f(x_1,\dots, x_n)\downarrow\Rightarrow (f(x_1,\dots, x_n)\in A\Rightarrow\beta(\chi(x_1),\dots,\chi(x_n))=1))$,
где $f(x_1,\dots,x_n)\downarrow$ означает, что $f(x_1,\dots,x_n)$ определено, $\chi$ — характеристическая функция $A$. Назовем множество $A\subseteq N$ слабо полурекурсивным (селекторным), если оно слабо $\beta$-селекторное, где $\beta=x\vee y$ (соответственно $\beta=(x\wedge y)\vee(x\wedge z)\vee(y\wedge z)$). Доказывается
Теорема. Пусть булева функция $\beta$ такова, что $\beta(x,\dots, x)=x$, и $\beta\not\equiv x$. Тогда класс $\beta$-селекторных множеств совпадает или с классом всех РПМ, или с классом слабо полурекурсивных, или с классом слабо селекторных множеств.
Затем выясняются некоторые свойства множеств из этих классов (в частности, класс слабо селекторных множеств строго содержит класс слабо полурекурсивных множеств).

УДК: 510.5

Поступило: 06.04.1988


 Англоязычная версия: DOI: 10.1007/BF01978405

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


© МИАН, 2024