Product Design, Manufacturing & Innovation Resources
家 » 有理数的可数性

有理数的可数性

1874
  • Georg Cantor
19th-century mathematician studying countability of rational numbers in an office.

(图片仅供参考)

尽管有理数集 [latex]mathbb{Q}[/latex] 稠密(即任意两个不同的有理数之间都存在另一个有理数),但它却是可数无限的。这意味着所有有理数都可以与自然数集 [latex]mathbb{N} = {1, 2, 3, }[/latex] 一一对应。这一令人惊讶的结果表明,[latex]mathbb{Q}[/latex] 与 [latex]mathbb{N}[/latex] 和 [latex]mathbb{Z}[/latex] 具有相同的基数。

康托尔对有理数可数性的证明是集合论发展史上的一个里程碑,也是我们对无穷概念理解的一大进步。这个证明既构造性又简洁优雅。一种常用的方法是将所有正有理数 p/q 排列在一个二维网格中,其中行索引为 p,列索引为 q。然后,我们可以沿着对角线遍历这个网格,从 1/1 开始,然后是 2/1、1/2,接着是 3/1、2/2、1/3,以此类推。这条路径被称为康托尔的对角线论证(尽管这个术语更常用于他证明实数不可数性的例子),它系统地列出了所有正有理数。 有理数.

在遍历过程中,任何非最简分数(例如 2/2 或 2/4)都会被跳过,以确保每个有理数只被计数一次。这个过程会生成一个包含所有正有理数的有序列表。为了包含所有有理数,可以将正有理数列表与其对应的负有理数列表交错排列,并在列表开头放置零:0, 1, -1, 1/2, -1/2, 2, -2, 0。这显式地构造了自然数集和有理数集之间的一一对应关系,证明了有理数集是可数的。

这个结果与直觉相悖,因为有理数是稠密的。任意两个有理数之间总能找到另一个(例如,它们的平均值),这表明有理数比整数“更多”,而整数之间存在明显的空隙。康托尔的证明表明,这种直觉是误导性的,无限集的“大小”(即它的基数)更为微妙。他后来证明了实数集是不可数的,从而建立了一个无穷的层级结构。

UNESCO Nomenclature: 1101
– Algebra, Number theory and Group theory

类型

抽象系统

中断

Incremental

用法

Conceptual/Theoretical

前体

  • 一一对应(双射)的概念
  • 博尔扎诺早期关于无限集的研究
  • 严谨数学分析的发展
  • 集合的概念

应用程序

  • 集合论基础
  • 计算机科学的计算理论(例如,证明所有可能的计算机程序的集合是可数的)
  • 测度论中,可数集的测度为零。
  • 区分不同大小的无限集合(例如,有理数集与实数集)

专利:

NA

潜在创新理念

  • 一种用于分布式计算的任务调度算法,它使用类似康托枚举的方法将作业分配给看似无限的处理器流。
  • 一种数据序列化格式,可以将任何基于理性的数据结构唯一地编码为单个整数。
  • 一种具有可数无限多个状态的通用计算机器的理论模型
  • 一种网络寻址协议,它可以使用有理数枚举为潜在无限数量的设备分配唯一地址。
  • 一种通过将坐标映射到单个可计数索引来索引动态增长的多维数据库中元素的方法
  • a procedural content generation algorithm for 电子游戏 that creates an infinitely large but navigable world by mapping locations to rational numbers
  • 一种形式语言定义,其中有效语句对应于有理数,从而可以唯一枚举所有可能的程序。
  • a proof-of-stake 区块链 protocol where validator selection is based on a deterministic traversal of the set of rational numbers
  • 一种通过将非零元素坐标映射到单个整数索引来压缩稀疏矩阵的方案
  • 一种通过遍历有理网格探索解空间的遗传算法,确保最终测试所有可能的分数阶参数。
相关概念:可数性、集合论、格奥尔格·康托尔、无限集、基数、双射、自然数、稠密集、对角线论证、阿列夫零集。

历史背景

有理数的可数性

1790
1800
1844
1874
1893
1900
1779
1799
1801
1850
1875
1897
1950

(如果日期未知或不相关,例如“流体力学”,则提供其显著出现的近似估计)

第十年 周年纪念日

只有注册会员才能免费获取完整尺寸的图片和下载内容。

> 登录 <