Generalizations of enumeration reducibility using recursive infinitary propositional sentences (Q1207542): Difference between revisions

Call \(B\) enumeration reducible to \(A\) \((B\leq_ e A)\) iff for every set \(S\), if \(A\) is r.e. in \(S\), then \(B\) is r.e. in \(S\). This paper shows a generalization of this correspondence: the relation between sets \(A\) and \(B\) that for every set \(S\) if \(A\) is \(\Sigma^ 0_ \alpha\) in \(S\) then \(B\) is \(\Sigma^ 0_ \beta\) in \(S\), is equivalent to the condition that \(B\) is definable from \(A\) in a particular way involving recursive infinitary propositional sentences. Some further generalizations involving infinitely many sets and ordinals are also established.