Premium
Weakly precomplete computably enumerable equivalence relations
Author(s) -
Badaev Serikzhan,
Sorbi Andrea
Publication year - 2016
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.201500057
Subject(s) - mathematics , equivalence relation , equivalence class (music) , equivalence (formal languages) , isomorphism (crystallography) , discrete mathematics , pure mathematics , class (philosophy) , natural number , combinatorics , characterization (materials science) , chemistry , materials science , artificial intelligence , computer science , crystal structure , crystallography , nanotechnology
Using computable reducibility ⩽ on equivalence relations, we investigate weakly precomplete ceers (a “ceer” is a computably enumerable equivalence relation on the natural numbers), and we compare their class with the more restricted class of precomplete ceers. We show that there are infinitely many isomorphism types of universal (in fact uniformly finitely precomplete) weakly precomplete ceers , that are not precomplete; and there are infinitely many isomorphism types of non‐universal weakly precomplete ceers. Whereas the Visser space of a precomplete ceer always contains an infinite effectively discrete subset, there exist weakly precomplete ceers whose Visser spaces do not contain infinite effectively discrete subsets. As a consequence, contrary to precomplete ceers which always yield partitions into effectively inseparable sets, we show that although weakly precomplete ceers always yield partitions into computably inseparable sets, nevertheless there are weakly precomplete ceers for which no equivalence class is creative. Finally, we show that the index set of the precomplete ceers is Σ 3 ‐complete, whereas the index set of the weakly precomplete ceers is Π 3 ‐complete. As a consequence of these results, we also show that the index sets of the uniformly precomplete ceers and of the e‐complete ceers are Σ 3 ‐complete.