<![CDATA[WUJ]]><![CDATA[info@ejournals.eu]]>https://www.ejournals.eu/20200809ejournals.eu.article.1443403010610.4467/20842589RM.19.006.1065420<![CDATA[Continuum Hypothesis, incidence problems, complexity, Dialectica Categories.]]>00ED031001Number10102<![CDATA[Reports on Mathematical Logic]]>03<![CDATA[2019]]>01<![CDATA[Number 54]]>1A01<![CDATA[Samuel G. da Silva]]>0101<![CDATA[Reductions between certain incidence problems and the continuum hypothesis]]>01en002203020PLN03<![CDATA[In this work, we consider two families of incidence problems, C1 and C2,, which are related to real numbers and countable subsets of the real line. Instances of problems of C1 are as follows: given a real number x, pick randomly a countable set of reals A hoping that x ∈ A, whereas instances of problems of C2 are as follows: given a countable set of reals A, pick randomly a real number x hoping that x ∉ A. One could arguably defend that, at least intuitively, problems of C2 are easier to solve than problems of C1. After some suitable formalization, we prove (within ZFC) that, on one hand, problems of C2 are, indeed, at least as easy to solve as problems of C1. On the other hand, the statement “Problems of C1 have the exact same complexity of problems of C2” is shown to be an equivalent of the Continuum Hypothesis.
Received 18 February 2019
AMS subject classification: Primary 03E50; Secondary 18A05, 18A15]]>012019100815000401http://dx.doi.org/10.4467/20842589RM.19.006.10654