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!