scientific article; zbMATH DE number 3867312

From MaRDI portal
Publication:3335771





[For the entire collection see Zbl 0538.00005.] A lot of important undecidability results are based on the fact that certain sets are recursively inseparable. An obvious generalization of recursive inseparability is inseparability by a recursively enumerable (r.e.) set, i.e., r.e. inseparability. We consider index sets of certain disjoint sets S and T of computable elements of an effective complete partial order (cpo) under certain numberings of these elements and study the r.e. and the effective r.e. inseparability of such index sets. The main result about effective r.e. inseparability is that the index set of S is effectively r.e. inseparable from the index set of T, if there is an r.e. subset T' of T such that S has a nonempty intersection with the closure of T' in the Scott topology of the cpo. As a consequence from this result one obtains the cpo generalizations of some well-known theorems, the theorem by Rice/Shapiro on completely r.e. sets of computable cpo elements and the theorem by Myhill/Shepherdson on effective operators. Moreover, it follows that the index set of a non Scott-open class of computable cpo elements is productive. This generalizes a result by Myhill/Dekker.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3335771)