Jumps of computably enumerable equivalence relations (Q1693042)

Computably enumerable equivalence relations on \(\omega\) (ceers) were first studied in [\textit{Yu. L. Ershov}, Z. Math. Logik Grundlagen Math. 19, 289--388 (1973; Zbl 0295.02025)]. For ceers \(R\) and \(S\), \(R \leq S\) iff there is a computable function \(f\) with \(xRy \Leftrightarrow f(x) S f(y)\) for all \(x, y\in\omega\). In terms of solvability, this amounts to \(R \lneq m S\). Degrees for ceers are generated by \(\deg(R) = \deg(S)\) iff \(R \leq S\) and \(S \leq R\). They are bounded below by the degree of the minimal ceer and above by the degree of universal ceers. Define the jump \(R'\) of \(R\) by \(x R' y\) iff \(x = y\) or \(\phi _x(x) R \phi _y(y)\). For ceers \(R\) and \(S\), say \(xR\oplus Sy\) iff either (\(x=2u\), \(y=2v\), and \(xRy\)) or (\(x=2u+1\), \(y=2v+1\), and \(xSy\)). From this we derive the join operation \(\vee\) on degrees: where \(a\) and \(b\) are the degrees of \(R\) and \(S\), \(a \vee b\) is the degree of \(R\oplus S\). Call \(e\) join-irreducible if, whenever \(e \leq a \vee b\), either \(e \leq a\) or \(e \leq b\). It is shown that all jump degrees are join-irreducible but that above the degree of any non-universal ceer there are join-irreducible degrees that are not jumps. The paper also studies transfinite iterations of the jump operation. Using Kleene's system of ordinal notation, it proves that there is no non-universal ceer which bounds \(\mathrm{Id}^\alpha\) for every \(\alpha\) that is a notation for \(\omega^2\).