On Dark Computably Enumerable Equivalence Relations |
| |
Authors: | N A Bazhenov B S Kalmurzaev |
| |
Institution: | 1.Sobolev Institute of Mathematics,Novosibirsk State University,Novosibirsk,Russia;2.Al-Farabi Kazakh National University,Almaty,Kazakhstan |
| |
Abstract: | We study computably enumerable (c.e.) relations on the set of naturals. A binary relation R on ω is computably reducible to a relation S (which is denoted by R ≤ c S) if there exists a computable function f(x) such that the conditions (xRy) and (f(x)Sf(y)) are equivalent for all x and y. An equivalence relation E is called dark if it is incomparable with respect to ≤ c with the identity equivalence relation. We prove that, for every dark c.e. equivalence relation E there exists a weakly precomplete dark c.e. relation F such that E ≤ c F. As a consequence of this result, we construct an infinite increasing ≤ c -chain of weakly precomplete dark c.e. equivalence relations. We also show the existence of a universal c.e. linear order with respect to ≤ c . |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|