Premium
On Some Properties of Recursively Enumerable Equivalence Relations
Author(s) -
Baratella Stefano
Publication year - 1989
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.19890350309
Subject(s) - equivalence relation , recursively enumerable language , equivalence (formal languages) , relation (database) , mathematics , computer science , logical equivalence , discrete mathematics , combinatorics , database
The study of equivalence relations in a recursion theoretic framework was started by Ju. L. ERSOV (see [5] ) and later on applied to logic first by A. VISSER in [13] and then by C. BERNARDI, F. MONTAQNA, A. SoRsr and G. SOHMARU~A (see [3], [S], IlOJ, [l 11). Results of representation and classification for equivalence relations have been proved by the above mentioned authors and more recently by A. LACHLAN and A. KANDA ([6], [7]). An equivalence relation (ex.) Ron the set w natural numbers is said to be recursively enumerable (or positive) if ( R ) = ((5, y) I %By) is an r.e. set. Following CARROLL [4], we will say that R is an r.e.e.r. Here we do not want to deal with (R) in place of R, because, as we shall see below, not all recursive properties of R are reflected in < R ) .