Эта публикация цитируется в
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