×

\(\Sigma^ n_ 0\)-equivalence relations. (English) Zbl 0539.03023

This paper deals with the reducibility pre-order \(\leq_ m\) ranging over equivalence relations on the set of natural numbers, where \({\mathcal R}\leq_ m{\mathcal S}\) if there exists a recursive function f such that, for all x, y: x \({\mathcal R} y\) if and only if f(x) \({\mathcal S} f(y)\). For \(n\geq 1\), \(\Sigma^ 0_ n\)-precomplete equivalence relations are introduced (generalizing a notion due to Ershov). It is shown that every \(\Sigma^ 0_ n\)-precomplete \(\Sigma^ 0_ n\)-equivalence relation is complete with respect of \(\leq_ m\) restricted to \(\Sigma^ 0_ n\)-equivalence relations. Several additional features of \(\Sigma^ 0_ n\)-precomplete equivalence relations are discussed. A representation theorem is also proved: Let T be an r.e. consistent theory which satisfies specific requirements (e.g. T is Peano arithmetic) and for \(n\geq 1\) let \(T^ n\) denote the theory obtained by adding as axioms all \(\Pi_{n-1}\) true sentences; then for every \(\Sigma^ 0_ n\)-equivalence relation \({\mathcal R}\) there is a \(\Sigma_ n\) formula F of T such that for all x, y: x \({\mathcal R} y\) iff \(T^ n\vdash F(\bar x)\leftrightarrow F(\bar y).\)

MSC:

03D45 Theory of numerations, effectively presented structures
Full Text: DOI

References:

[1] C. Bernardi, On the relation provable equivalence and on partitions in effectively inseparable sets, Studio Logica 40 (1981), pp. 29-37. · Zbl 0468.03020 · doi:10.1007/BF01837553
[2] C. Bernardi and A. Sorbi, Classifying positive equivalence relations, to appear in Journal of Symbolic Logic (1983). · Zbl 0528.03030
[3] Ju. L. Ersov, Theorie der Numerierungen I, Zeitschrift f?r Mathematische Logik und Grundlagen der Mathematik 19 (1973), pp. 289-388.
[4] Ju. L. Ersov, Theorie der Numerierungen II, Zeitschrift f?r Mathematische Logik und Grudlagen der Mathematik 21 (1975), pp. 473-584. · doi:10.1002/malq.19750210164
[5] Ju. L. Ersov, Positive equivalences (English, translation), Algebra and Logic, 10 (1973), pp. 378-394. · Zbl 0276.02024 · doi:10.1007/BF02218645
[6] P. G. Hinman, Recursion-Theoretic Hierarchies, Springer-Verlag, Heidelberg. · Zbl 0371.02017
[7] C. F. Kent, The relation of A to Prov ?A? in the Lindenbaum sentence algebra, Journal of Symbolic Logic 38 (1973), pp. 295-298. · Zbl 0275.02034 · doi:10.2307/2272065
[8] H. Rogers, Theory of Recursive Functions and Effective Camputability, McGraw Hill, New York 1967. · Zbl 0183.01401
[9] A. Sorbi, Numerazioni positive, r. e. classi e formule, Bollettino del-Unione Matematica Italiana, Suppl. Vol. 1 (1982), pp. 79-88. · Zbl 0502.03023
[10] A. Visser, Numerations, ?-Calculus and Arithmetic, Fert. for H. B. Curry (Hindley, Seldin editors), Academic Press 1980, pp. 259-284.
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.