Effective Versions of Strong Measure Zero and Borel’s Conjecture

Abstract: In this talk I will discuss effective versions of strong measure zero that have been developed for various levels of complexity and computability. Borel’s conjecture that a set has strong measure zero if and only if it is countable is known to be independent of ZFC. I will go over effective versions of Borel’s conjecture and show that they hold in time and space bounded levels, but not at the level of computability.

I will also describe some properties of the effective strong measure zero sets and show that they have many equivalent characterizations. One of the main results being the equivalence at the lower semicomputable level to the class NCR defined by Reimann and Slaman. I will also mention some similarities and differences between strong measure zero sets in effective and non-effective settings.

computational complexitygeneral topologylogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic