Recursively Enumerable Equivalence Relations Modulo Finite Differences
From MaRDI portal
Publication:4315325
DOI10.1002/malq.19940400407zbMath0829.03024MaRDI QIDQ4315325
Publication date: 8 December 1994
Published in: Mathematical Logic Quarterly (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1002/malq.19940400407
\(m\)-reducibility; recursively enumerable equivalence relations; recursion-theoretic semilattice; true first-order arithmetic
03D35: Undecidability and degrees of sets of sentences
03D15: Complexity of computation (including implicit computational complexity)
03D25: Recursively (computably) enumerable sets and degrees
Related Items
\(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures, Elementary theories and hereditary undecidability for semilattices of numberings, The theory of ceers computes true arithmetic