On the uncountability of \mathbb{R}

DOI10.1017/JSL.2022.27zbMATH Open1523.03004arXiv2007.07560MaRDI QIDQ6345137FDOQ6345137

Authors: Dag Normann, Sam Sanders 

Publication date: 15 July 2020

Abstract: Cantor's first set theory paper (1874) establishes the uncountability of $mathbbR$. We study this most basic mathematical fact formulated in the language of higher-order arithmetic. In particular, we investigate the logical and computational properties of NIN (resp. NBI), i.e. the third-order statement: there is no injection (resp. bijection) from $[0,1]$ to $mathbbN$. Working in Kohlenbach's higher-order Reverse Mathematics, we show that NIN and NBI are hard to prove in terms of (conventional) comprehension axioms, while many basic theorems, like Arzela's convergence theorem for the Riemann integral (1885), are shown to imply NIN and/or NBI. Working in Kleene's higher-order computability theory based on S1-S9, we show that the following fourth-order process based on NIN is similarly hard to compute: for a given $[0,1]ightarrowmathbbN$-function, find reals in the unit interval that map to the same natural number.

Mathematics Subject Classification ID

Foundations of classical theories (including reverse mathematics) (03B30) Hierarchies of computability and definability (03D55) Higher-type and set recursion theory (03D65) Second- and higher-order arithmetic and fragments (03F35) Other degrees and reducibilities in computability and recursion theory (03D30)

This page was built for publication: On the uncountability of $\mathbb{R}$

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6345137)