Title: Semi-decidable equivalence relations obtained by composition and lattice join of decidable equivalence relations,
Abstract: 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.