Reductions between certain incidence problems and the continuum hypothesis
Choose format
RIS BIB ENDNOTEReductions between certain incidence problems and the continuum hypothesis
Publication date: 08.10.2019
Reports on Mathematical Logic, 2019, Number 54, pp. 121-143
https://doi.org/10.4467/20842589RM.19.006.10654Authors
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.
[1] L.F. Aurichi, Sobre a Hipótese do Contınuo. Algumas Equivalęncias e Aplicaçoes, MsC Dissertation (in Portuguese), USP University of Sao Paulo, Brazil, 2005.
[2] M. Barr, *-autonomous categories. With an appendix by Po-Hsiang Chu, Lecture Notes in Mathematics 752, Berlin, Heidelberg, New York, Springer-Verlag, 1979, vi + 140 pp.
[3] A. Blass, Questions and Answers – A Category Arising in Linear Logic, Complexity Theory, and Set Theory, In: J.-Y. Girard, Y. Lafont, and L. Regnier (eds.), Advances in Linear Logic, London Math. Soc. Lecture Notes 222 (1995), 61–81.
[4] A. Blass, Propositional Connectives and the Set Theory of the Continuum, CWI Quarterly 9 (1996), 25–30.
[5] C. Freiling, Axioms of Symmetry: throwing darts at the real number line, Journal of Symbolic Logic 51:1 (1986), 190–200.
[6] H. Garcia and S.G. da Silva, Identifying small with bounded: unboundedness, domination, ideals and their cardinal invariants, South American Journal of Logic 2:2 (2016), 425–436.
[7] M.R. Garey and D.S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, A Series of Books in the mathematical Sciences, San Francisco, W.H. Freeman and Company, 1979, x + 338 pp.
[8] D.G. Green and T. Leishman, Computing and Complexity – Networks, Nature and Virtual Worlds, In: C.A. Hooker, D.M. Gabbay, P. Thagard, J. Woods (eds.), Hand-book of the Philosophy of Science, Vol. 10 – Philosophy of Complex Systems, 1st ed., North Holland, 2011, pp. 137–161.
[9] K. Kunen, Set theory. An introduction to independence proofs, Studies in Logic and the Foundations of Mathematics, Vol. 102, Amsterdam, North-Holland Publishing Company, 1980, xvi + 313 pp.
[10] P. Maddy, Believing the axioms. I, Journal of Symbolic Logic 53:2 (1988), 481–511.
[11] J.T. Moore, M. Hrušák, and M. Dzamonja, Parametrized ♦ principles, Transactions of Americal Mathematical Society 356:6 (2004), 2281–2306.
[12] A. Moreno and M. Mossio, Biological Autonomy: A Philosophical and Theoretical Enquiry, History, Philosophy and Theory of the Life Sciences 12, Dordrecht, Springer, 2015, xxxiv + 221 pp.
[13] V. de Paiva, A dialectica-like model of linear logic, In: D. Pitt, D. Rydeheard, P. Dybjer, A. Pitts, and A. Poigne (eds.), Category Theory and Computer Science, Springer, 1989, pp. 341–356.
14] V. de Paiva, The Dialectica Categories, Computer Laboratory, University of Cambridge, 1990.
[15] V. de Paiva, Dialectica and Chu constructions: cousins?, Theory and Applications of Categories 17 (2006), 127–152.
[16] C.H. Papadimitriou, Computational complexity, Addison-Wesley Publishing Company, Amsterdam, 1994, xv + 523 pp.
[17] S.M. Ross, A first course in probability, 9th ed., Pearson Education/Prentice Hall, Upper Saddle River, NJ, 2014, xi + 467 pp.
[18] W. Sierpinski, Hypoth`ese du Continu, Monografie Matematyczne, 1`ere ed. PWN, Varsóvia, 1934, v + 192 pp.
[19] S.G. da Silva and V. de Paiva, Dialectica categories, cardinalities of the continuum and combinatorics of ideals, Logic Journal of the IGPL 25:4 (2017), 585–603.
[20] S.G. da Silva, The Axiom of Choice and the Partition Principle from Dialectica Categories, 2018. Submitted.
[21] P. Vojtáš, Generalized Galois-Tukey-connections between explicit relations on classical objects of real analysis, In: H. Judah (ed.), Set theory of the reals (Ramat Gan, 1991), Bar-Ilan Univ., Ramat Gan, Israel Math. Conf. Proc. 6, 1993, pp. 619–643
Information: Reports on Mathematical Logic, 2019, Number 54, pp. 121-143
Article type: Original article
Instituto de Matemática e Estatística, Universidade Federal da Bahia, Campus de Ondina, Av. Adhemar de Barros, S/N, Ondina, CEP 40170110, Salvador, BA, Brazil
Published at: 08.10.2019
Received at: 18.02.2019
Article status: Open
Licence: CC BY-NC-ND
Percentage share of authors:
Classification number:
Article corrections:
-Publication languages:
EnglishView count: 2135
Number of downloads: 1271