Recursive-combinatorial properties of subsets of the natural numbers (Q803118)

From MaRDI portal
Revision as of 01:15, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Recursive-combinatorial properties of subsets of the natural numbers
scientific article

    Statements

    Recursive-combinatorial properties of subsets of the natural numbers (English)
    0 references
    1990
    0 references
    Seven families of subsets of \({\mathbb{N}}\) are considered with respect to m-, tt- and \(\ell\)-reducibilities and two theorems are proved on the relations among those families. A recursive function f is called selective if \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\in \{x_ 1,...,x_ n\}).\) Let \(A\subseteq {\mathbb{N}}\) and \(\beta\not\equiv 0,1\) be an n-ary Boolean function. A is called \(\beta\)-selective if there is an n-ary selective recursive function f such that \((\forall x_ 1,...,x_ n)(f(x_ 1,...,x_ n)\in A\leftrightarrow \beta (\chi_ A(x_ 1),...,\chi_ A(x_ n))=1).\) The Boolean function \(\beta\not\equiv 0,1\) is called admissible if there is a \(\beta\)-selective set \(A\neq \emptyset,{\mathbb{N}}\). The following theorem is proved. If \(\beta \not\equiv x_ 1\) is an admissible function, then the family of \(\beta\)-selective sets coincides either with the family of recursive sets or with the family of semirecursive sets.
    0 references
    reducibilities
    0 references
    recursive function
    0 references
    \(\beta \) -selective set
    0 references
    recursive sets
    0 references
    semirecursive sets
    0 references
    0 references

    Identifiers