Jumps of computably enumerable equivalence relations |
| |
Authors: | Uri Andrews Andrea Sorbi |
| |
Affiliation: | 1. Department of Mathematics, University of Wisconsin, Madison, WI 53706-1388, USA;2. Dipartimento di Ingegneria Informatica e Scienze Matematiche, Università Degli Studi di Siena, I-53100 Siena, Italy |
| |
Abstract: | We study computably enumerable equivalence relations (or, ceers), under computable reducibility ≤, and the halting jump operation on ceers. We show that every jump is uniform join-irreducible, and thus join-irreducible. Therefore, the uniform join of two incomparable ceers is not equivalent to any jump. On the other hand there exist ceers that are not equivalent to jumps, but are uniform join-irreducible: in fact above any non-universal ceer there is a ceer which is not equivalent to a jump, and is uniform join-irreducible. We also study transfinite iterations of the jump operation. If a is an ordinal notation, and E is a ceer, then let denote the ceer obtained by transfinitely iterating the jump on E along the path of ordinal notations up to a. In contrast with what happens for the Turing jump and Turing reducibility, where if a set X is an upper bound for the A-arithmetical sets then computes , we show that there is a ceer R such that , for every finite ordinal n, but, for all k, (here Id is the identity equivalence relation). We show that if are notations of the same ordinal less than , then , but there are notations of such that and are incomparable. Moreover, there is no non-universal ceer which is an upper bound for all the ceers of the form where a is a notation for . |
| |
Keywords: | 03D25 03D30 03D45 03F15 Computably enumerable equivalence relation Computable reducibility on equivalence relations Halting jump |
本文献已被 ScienceDirect 等数据库收录! |
|