A generalization of Selivanov's theorem (Q1358035)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1023939
Language Label Description Also known as
default for all languages
No label defined
    English
    A generalization of Selivanov's theorem
    scientific article; zbMATH DE number 1023939

      Statements

      A generalization of Selivanov's theorem (English)
      0 references
      0 references
      0 references
      25 March 1999
      0 references
      It is known [\textit{V. L. Selivanov}, Algebra Logic 15, 297-306 (1976); translation from: Algebra Logika 15, No. 4, 470-484 (1976; Zbl 0358.02050)] that a nontrivial quotient semilattice of computable enumerations by equivalence is not a lattice. In the paper under review the authors obtain several generalizations of this claim. A typical result: Let \(P\) be a collection of enumerations of a family of recursively enumerable sets with a nontrivial set of classes of \(\Pi_4^0\)-equivalent indexings of \(P\). Then the semilattice of equivalence classes of computable indexings of \(P\) is not a lattice.
      0 references
      computable enumerations
      0 references
      Turing reducibility
      0 references
      recursively enumerable sets
      0 references
      semilattice of equivalence classes
      0 references

      Identifiers