Classifying equivalence relations in the Ershov hierarchy (Q2204368)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classifying equivalence relations in the Ershov hierarchy |
scientific article |
Statements
Classifying equivalence relations in the Ershov hierarchy (English)
0 references
15 October 2020
0 references
This article examines the behavior of \(\Delta^0_2\) equivalence relations with respect to computable reducibility \(\le_c\), considering the \(c\)-degrees at the various levels of the Ershov hierarchy. The authors discuss dark equivalence relations and introduce the stronger notion of a pair of ``mutually dark'' relations. They show that every level of the hierarchy, except for that of the co-ceers, contains mutually dark (and hence dark) relations. The paper also establishes several results on the existence and especially the non-existence of sups and infs of \(c\)-degrees. Mutually dark relations play an important role here as well.
0 references
computability theory
0 references
Ershov hierarchy
0 references
\(\Delta^0_2\) equivalence relations
0 references
computably enumerable equivalence relations
0 references