On the Borel-Cantelli Lemmas, the Erdős-Rényi Theorem, and the Kochen-Stone Theorem

Rob Arthan, Paulo Oliva


In this paper we present a quantitative analysis of the first and second Borel-Cantelli Lemmas and of two of their generalisations: the Erdős–Rényi Theorem, and the Kochen-Stone Theorem. We will see that the first three results have direct quantitative formulations, giving an explicit relationship between quantitative formulations of the assumptions and the conclusion. For the Kochen-Stone theorem, however, we can show that the numerical bounds of a direct quantitative formulation are not computable in general. Nonetheless, we obtain a quantitative formulation of the Kochen-Stone Theorem using Tao's notion of metastability.


Quantitative analysis; metastability; Borel-Cantelli lemma; Kochen-Stone theorem; Erdős–Rényi Theorem

Full Text:

6. [PDF]

DOI: https://doi.org/10.4115/jla.2021.13.6

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Logic and Analysis ISSN:  1759-9008