Recursively enumerable degreesについて

概要

論文の詳細を見る
The main purpose of this paper is to prove the following propositions 1°, 2°. 1° Let A and B be recursively enumerable sets enumerated by recursive functions f and g, respectively, without repetitions. Then A is recursive in B if and only if there exist recursive functions F(w) and G(w) which satisfy the following conditions ; (i) [numerical formula] is infinite, (ii) for each t, there exists at least one s such that [numerical formula]. 2° Let B_0, …, B_m be non-recursive recursively enumerable sets, and P_i (x, y, X_1, …, X_<m-1>) be predicates recursive in sets X_1, …, X_<m-1> for each i ⪇ m-1. Then ther exist recursively enumerable sets A_1, …, A_<m-1> such that (a) and (b) are satisfied; (a) [numerical formula] for each i<m, (b) [numerical formula]. The last proposition, which is proved with the help of the priority method, gives an alternative proof of the existence theorem by Sacks.
明治大学の論文