Reductions between certain incidence problems and the continuum hypothesis

• Autorzy: da Silva Samuel G.

Identyfikatory

DOI

10.4467/20842589RM.19.006.10654

• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

Continuum Hypothesis; incidence problems; complexity; Dialectica Categories

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2019
• Tom: Vol. 54
• Strony: 121--143
• Opis fizyczny: Bibliogr. 21 poz.

Twórcy

autor

da Silva Samuel G.

• Instituto de Matemática e Estatística Universidade Federal da Bahia Campus de Ondina, Av. Adhemar de Barros, S/N Ondina, CEP 40170-110, Salvador, BA, Brazil

Bibliografia

• [1] L.F. Aurichi, Sobre a Hipótese do Contínuo. Algumas Equivaléncias e Aplicącoes, 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.), Handbook 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. Džamonja, 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. Sierpiński, Hypothése 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.

Uwagi

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