Classifying positive equivalence relations

DOI10.2307/2273443MaRDI QIDQ3309827zbMATH OpenOpenAlexFDO

Authors Claudio Bernardi, Andrea Sorbi

Publication date 1983

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2307/2273443

zbMATH Keywords

equivalence relationsnumerationsPAprecompletenessprovable equivalence

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45) First-order arithmetic and fragments (03F30)

Cites work

• Creative Functions
• Creative sets
• scientific article; zbMATH DE number 3291134 (Why is no real title available?)
• On the relation provable equivalence and on partitions in effectively inseparable sets
• Recursively enumerable classes and their application to recursive sequences of formal theories
• Theorie der Numerierungen I

Cited in

(47)

• Hyperdiagonalizable algebras
• On a conjecture of Bergstra and Tucker
• On dark computably enumerable equivalence relations
• Jumps of computably enumerable equivalence relations
• Precomplete numberings
• The category of equivalence relations
• Completeness of the hyperarithmetic isomorphism equivalence relation
• Special classes of positive preorders
• Partial combinatory algebra and generalized numberings
• Index sets for classes of positive preorders
• The theory of ceers computes true arithmetic
• Classifying equivalence relations in the Ershov hierarchy
• Minimal equivalence relations in hyperarithmetical and analytical hierarchies
• The structure of computably enumerable preorder relations
• On computably enumerable structures
• On the degree structure of equivalence relations under computable reducibility
• Weakly precomplete equivalence relations in the Ershov hierarchy
• Fixed point theorems for precomplete numberings
• Graphs realised by r.e. equivalence relations
• On universal positive graphs
• Weakly precomplete computably enumerable equivalence relations
• A survey on universal computably enumerable equivalence relations
• On Σ¹ ₁ equivalence relations over the natural numbers
• Precomplete Equivalence Relations in Dominical Categories
• GENERALIZATIONS OF THE RECURSION THEOREM
• Theoretical Pearls:Representing ‘undefined’ in lambda calculus
• Primitive recursive equivalence relations and their primitive recursive complexity
• Fixpoints and relative precompleteness
• Initial segments of the degrees of ceers
• Computable embeddability for algebraic structures
• Fixed points and unfounded chains
• Agreement reducibility
• ON THE STRUCTURE OF COMPUTABLE REDUCIBILITY ON EQUIVALENCE RELATIONS OF NATURAL NUMBERS
• Word problems and ceers
• COMPUTABLE REDUCIBILITY OF EQUIVALENCE RELATIONS AND AN EFFECTIVE JUMP OPERATOR
• Computable reducibility for computable linear orders of type
• \(\Sigma_1^0\) and \(\Pi_1^0\) equivalence structures
• A note on joins and meets for positive linear preorders
• Some properties of precompletely and positively numbered sets
• Computably enumerable equivalence relations via primitive recursive reductions
• Defining algorithmically presented structures in first order logic
• On the theory of computably enumerable linear preorders with concatenation
• Fixed point theorems in computability theory
• Computable structure theory of partial combinatory algebras
• The noneffectivity of Arslanov's completeness criterion and related theorems
• \(\Sigma^ n_ 0\)-equivalence relations
• Reducibilities among equivalence relations induced by recursively enumerable structures

This page was built for publication: Classifying positive equivalence relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3309827)