The uncountability of the real numbers is one of their most basic properties, known (far) outside of mathematics. Cantor's 1874 proof of the uncountability of the real numbers even appears in the very first paper on set theory, i.e. a historical milestone. Despite this famous status and history, the computational properties of the uncountability of the real numbers have not been studied much. In this paper, we study the following computational operation that witnesses that the real numbers not countable: on input a countable set of reals, output a real not in that set. In particular, we formulate a considerable number of operations that are computationally equivalent to the centred operation, working in Kleene's higher-order computability theory based on his S1-S9 computation schemes. Perhaps surprisingly, our equivalent operations involve most basic properties of the Riemann integral and Volterra's early work circa 1881.
翻译:真实数字的不可计算性是他们最基本的特性之一, 数学之外已知的( 远处) 。 坎托尔1874年关于真实数字不可计算性的证据甚至出现在关于设定理论的第一份文件中, 即历史里程碑。 尽管存在这一著名的状态和历史, 真实数字不可计算性的计算性没有多少研究。 在本文中, 我们研究以下计算操作, 证明真实数字不可计算: 输入一组可计数的真数, 产生一个真实的不可计算性。 特别是, 我们根据克莱恩的S1- S9计算方法, 以高阶可计算性理论为基础, 制定了与中心操作相同的大量操作, 以计算为单位的操作。 也许令人惊讶的是, 我们的等同操作涉及里曼集成和沃尔特拉早期工程的最基本的特性, 也就是1881年。