Effective Versions of Strong Measure Zero and Borel’s Conjecture

Borel’s conjecture is the statement that a set has strong measure zero if and only if it is countable. This is known to be independent of ZFC. In this talk, I will define effective versions of strong measure zero with respect to varying degrees of complexity and computability restraints. At each level of effectivity, the effectively countable sets are proven to have effective strong measure zero. This is also the case for classical strong measure zero. However, in the effective versions the converse always has an answer, and the answer depends on the level of effectivity. Equivalent characterizations of the effective strong measure zero sets and their properties are also investigated. It is shown that at the level of lower semicomputability, the notion coincides with the set NCR defined by Reimann and Slaman.

Committee: Jack Lutz (major professor), James Lathrop, Yan-Bin Jia, Pavan Aduri, and Konstantin Slutsky