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 this page instead for the normal view: A generalization of Selivanov's theorem |
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
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
0.9340951
0 references
0 references
0 references
0.9239912
0 references
0.92350423
0 references
0.92250866
0 references
0.9223305
0 references