Reductions between certain incidence problems and the continuum hypothesis

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.

---

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2019).