Sparse-witness construction of a simple set
ID: sparse-witness-construction-of-a-simple-set
Enumerate all computably enumerable sets as . For each , once a witness appears in , enumerate one such witness into and never act for again. Every infinite supplies a witness. Only requirements can put numbers into , so at least numbers in that interval stay outside . Thus is a simple set. The proof uses a numerical bound rather than an infinitude test.
New to topics? Read the docs here!