Classifying Positive Equivalence Relations
Bernardi, Claudio ; Sorbi, Andrea
J. Symbolic Logic, Tome 48 (1983) no. 1, p. 529-538 / Harvested from Project Euclid
Given two (positive) equivalence relations $\sim_1, \sim_2$ on the set $\omega$ of natural numbers, we say that $\sim_1$ is $m$-reducible to $\sim_2$ if there exists a total recursive function $h$ such that for every $x, y \in \omega$, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$. We prove that the equivalence relation induced in $\omega$ by a positive precomplete numeration is complete with respect to this reducibility (and, moreover, a "uniformity property" holds). This result allows us to state a classification theorem for positive equivalence relations (Theorem 2). We show that there exist nonisomorphic positive equivalence relations which are complete with respect to the above reducibility; in particular, we discuss the provable equivalence of a strong enough theory: this relation is complete with respect to reducibility but it does not correspond to a precomplete numeration. From this fact we deduce that an equivalence relation on $\omega$ can be strongly represented by a formula (see Definition 8) iff it is positive. At last, we interpret the situation from a topological point of view. Among other things, we generalize a result of Visser by showing that the topological space corresponding to a partition in e.i. sets is irreducible and we prove that the set of equivalence classes of true sentences is dense in the Lindenbaum algebra of the theory.
Publié le : 1983-09-14
Classification: 
@article{1183741310,
     author = {Bernardi, Claudio and Sorbi, Andrea},
     title = {Classifying Positive Equivalence Relations},
     journal = {J. Symbolic Logic},
     volume = {48},
     number = {1},
     year = {1983},
     pages = { 529-538},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183741310}
}
Bernardi, Claudio; Sorbi, Andrea. Classifying Positive Equivalence Relations. J. Symbolic Logic, Tome 48 (1983) no. 1, pp.  529-538. http://gdmltest.u-ga.fr/item/1183741310/