2017/11/08 by Edward J. Green, Green, Edward J.
Computer Science · Mathematics · #03D25 #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #math.LO #msc:03D25
paper · pdf · doi:10.48550/arxiv.1711.03056
14 pages. Version 2 incorporates numerous clarifications and corrections in details of proofs. Thre results of version 1 are unchanged, except for an inconsequential amendment of lemma 12
openalex publication_date 2017/11/08 · openalex created_date 2017/11/17 · arxiv created 2018/01/20 · arxiv updated 2018/01/23 · openalex updated_date 2026/07/28
Composition and lattice join (transitive closure of a union) of equivalence relations are operations taking pairs of decidable equivalence relations to relations that are semi-decidable, but not necessarily decidable. This article addresses the question, is every semi-decidable equivalence relation obtainable in those ways from a pair of decidable equivalence relations? It is shown that every semi-decidable equivalence relation, of which every equivalence class is infinite, is obtainable as both a composition and a lattice join of decidable equivalence relations having infinite equivalence classes. An example is constructed of a semi-decidable, but not decidable, equivalence relation having finite equivalence classes that can be obtained from decidable equivalence relations, both by composition and also by lattice join. Another example is constructed, in which such a relation cannot be obtained from decidable equivalence relations in either of the two ways.