##
**Equivalence structures and isomorphisms in the difference hierarchy.**
*(English)*
Zbl 1196.03049

Effective properties of equivalence structures in the context of the difference hierarchy are studied.

At first, the authors prove that every \(\Delta^0_2\) character (a set of pairs of integers closed downwards with respect to the second component) can be realized as the character of a d.c.e. equivalence structure. This contrasts with a result from [W. Calvert, D. Cenzer, V. Harizanov and A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic 141, No. 1–2, 61–78 (2006; Zbl 1103.03037)], where a \(\Delta^0_2\) character was found that is not realized as the character of a computable structure.

Secondly, the authors study the levels of isomorphisms of computable equivalence structures in the difference hierarchy, e.g., they build examples of equivalence structures that are isomorphic via an \(n\)-c.e. isomorphism but not via (\(n-1\))-c.e. isomorphisms.

Thirdly, the levels of categoricity in the difference hierarchy are studied. In particular, it is proved that the weakly \(\omega\)-c.e. categoricity coincides with the usual computable categoricity for the equivalence structures (so the difference hierarchy collapses on the finite levels). Finally, it is proved that \(\Delta ^0_2\) categoricity is equivalent to graph-\(\omega \)-c.e. categoricity for the equivalence classes.

At first, the authors prove that every \(\Delta^0_2\) character (a set of pairs of integers closed downwards with respect to the second component) can be realized as the character of a d.c.e. equivalence structure. This contrasts with a result from [W. Calvert, D. Cenzer, V. Harizanov and A. Morozov, “Effective categoricity of equivalence structures”, Ann. Pure Appl. Logic 141, No. 1–2, 61–78 (2006; Zbl 1103.03037)], where a \(\Delta^0_2\) character was found that is not realized as the character of a computable structure.

Secondly, the authors study the levels of isomorphisms of computable equivalence structures in the difference hierarchy, e.g., they build examples of equivalence structures that are isomorphic via an \(n\)-c.e. isomorphism but not via (\(n-1\))-c.e. isomorphisms.

Thirdly, the levels of categoricity in the difference hierarchy are studied. In particular, it is proved that the weakly \(\omega\)-c.e. categoricity coincides with the usual computable categoricity for the equivalence structures (so the difference hierarchy collapses on the finite levels). Finally, it is proved that \(\Delta ^0_2\) categoricity is equivalent to graph-\(\omega \)-c.e. categoricity for the equivalence classes.

Reviewer: Iskander Kalimullin (Kazan)

### MSC:

03C57 | Computable structure theory, computable model theory |

### Keywords:

equivalence structures; difference hierarchy; levels of categoricity; computable categoricity### Citations:

Zbl 1103.03037
PDFBibTeX
XMLCite

\textit{D. Cenzer} et al., J. Symb. Log. 74, No. 2, 535--556 (2009; Zbl 1196.03049)

Full Text:
DOI

### References:

[1] | Recursively enumerable sets and degrees (1987) |

[2] | DOI: 10.1016/j.apal.2005.10.002 · Zbl 1103.03037 · doi:10.1016/j.apal.2005.10.002 |

[3] | Siberian Advances in Mathematics 2 pp 68– (1992) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.