Deprecated: $wgMWOAuthSharedUserIDs=false is deprecated, set $wgMWOAuthSharedUserIDs=true, $wgMWOAuthSharedUserSource='local' instead [Called from MediaWiki\HookContainer\HookContainer::run in /var/www/html/w/includes/HookContainer/HookContainer.php at line 135] in /var/www/html/w/includes/Debug/MWDebug.php on line 372
A generalization of Selivanov's theorem - MaRDI portal

A generalization of Selivanov's theorem (Q1358035)

From MaRDI portal





scientific article; zbMATH DE number 1023939
Language Label Description Also known as
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