Classifying positive equivalence relations

Journal of Symbolic Logic 48 (3):529-538 (1983)
  Copy   BIBTEX

Abstract

Given two (positive) equivalence relations ∼ 1 , ∼ 2 on the set ω of natural numbers, we say that ∼ 1 is m-reducible to ∼ 2 if there exists a total recursive function h such that for every x, y ∈ ω, we have $x \sim_1 y \operatorname{iff} hx \sim_2 hy$ . We prove that the equivalence relation induced in ω 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 ω 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

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 92,150

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

$\sum_{0}^{n}$ -Equivalence Relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351 - 358.
Maximal R.e. Equivalence relations.Jeffrey S. Carroll - 1990 - Journal of Symbolic Logic 55 (3):1048-1058.
Thin equivalence relations and effective decompositions.Greg Hjorth - 1993 - Journal of Symbolic Logic 58 (4):1153-1164.
Infinite Time Decidable Equivalence Relation Theory.Samuel Coskey & Joel David Hamkins - 2011 - Notre Dame Journal of Formal Logic 52 (2):203-228.
On Σ1 1 equivalence relations with Borel classes of bounded rank.Ramez L. Sami - 1984 - Journal of Symbolic Logic 49 (4):1273 - 1283.
? 0 N -equivalence relations.Andrea Sorbi - 1982 - Studia Logica 41 (4):351-358.

Analytics

Added to PP
2009-01-28

Downloads
216 (#93,707)

6 months
11 (#241,733)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

Fixed point theorems for precomplete numberings.Henk Barendregt & Sebastiaan A. Terwijn - 2019 - Annals of Pure and Applied Logic 170 (10):1151-1161.
Relatively precomplete numerations and arithmetic.Franco Montagna - 1982 - Journal of Philosophical Logic 11 (4):419 - 430.
The theory of ceers computes true arithmetic.Uri Andrews, Noah Schweber & Andrea Sorbi - 2020 - Annals of Pure and Applied Logic 171 (8):102811.

View all 22 citations / Add more citations

References found in this work

Creative sets.John Myhill - 1955 - Mathematical Logic Quarterly 1 (2):97-108.
Creative sets.John Myhill - 1955 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 1 (2):97-108.
Theorie der Numerierungen I.Ju L. Eršov - 1973 - Mathematical Logic Quarterly 19 (19‐25):289-388.
Theorie der Numerierungen II.J. U. L. Eršov - 1975 - Mathematical Logic Quarterly 21 (1):473-584.

View all 8 references / Add more references