一个变量“存储”任意多的数-- 从“康托配对函数”聊开去
这篇文章的话题源自来自于大老李最近的一次编程经历。上两月,我在用一个很奇怪的语言编程。这种编程语言里变量类型只有正整数,没有小数和负数。变量的操作也只有加、减和乘,没有除法,有些基本的循环结构和变量大小的判断等等。
这种编程语言听上去是很简陋,你先不用管为什么我要用这种语言编程,以后有机会聊。就这种语言,我遇到了一个很大的编程困难是,我需要一个堆栈(Stack)数据结构。在其他任何支持数组或者列表的编程语言里,实现堆栈完全不是问题。堆栈就是从数组最末尾开始存取的一个数据结构。
但我现在使用的这种编程语言里,内置的除了整数型变量,没有任何数据结构。那有没有办法实现一个堆栈呢?上网搜了下,还真有,而且方法其实很简单。这个方法是先考虑这样一个问题:有没有可能找到一对自然数与全体自然数的一一对应。
这里简单介绍下无穷基数理论。简单来说,无穷基数理论提出了这样一种比较具有无穷多元素的集合大小的方法,就是看两个无穷集合中的元素是否能建立一一对应的关系,其实在函数语言里,这种性质叫“双射”。稍微解释下双射函数。其实先得知道两个概念,“单射”和“满射”。
比如有个函数叫y=f(x),如果代入不同的x,总是得到不同的y,那么这个函数就叫“单射”。单射是一种很重要的函数性质,比如二次曲线和多数三角函数都不是单射。
还有一个概念叫“满射”,意思是函数的值域被填满了。也就是任何一个值域里的值,代入y,总能找到一个x,使得f(x)=y。实数函数

就不是满射,因为y是负数的时候,就找不到对应的x。
那一个函数即是单射又是满射的时候,我们就叫它“双射”。

如果存在两个无穷集合元素之间的双射,我们就认为这两个无穷集合的“大小”是一样的。而且已经证明,无穷集合中,“最小”的就是自然数集合。有意思的是,可以建立偶数到全体自然数的双射,也就是在无穷基数理论的范畴下,偶数与全体自然数“一样多”。这是“无穷”概念给我们造成的反直觉结论之一。
那现在考虑这样一个集合,其元素是自然数对,比如(1,2), (100,200 )等等,也包括(0, 0)。本文中,自然数是包括0的。那么这个成对自然数的集合直观形象就是笛卡尔坐标系第一象限中的纵横坐标都是整数的点,再加上x和y轴正方向上的整数点和原点。有时我们说这种成对的自然数集合,为自然数集合的“笛卡尔积”就是这个道理。
现在的问题是:自然数集合的笛卡尔积能否建立与自然数的一一对应,即双射呢?
从直觉上来看确实是可以,我们只要想一个办法把这些点按某种顺序罗列出来,做到既不重复也不遗漏就可以了。排列出来后,就相当于给这些点用自然数编了号,那么双射就自然成立了。
具体怎么做呢?其实有不止一种方法,数学家康托当初使用了一种像一笔画一样方法,按对角线方向来回往复的对这些点进行连接和排序。

比如,按他的方法,自然数对排列的最开始三项就是(0,0), (1,0)和(0,1)。它们就会对应自然数0到2。它的通项公式如下:

这个通项公式就被称为“康托配对函数”,因为它取了一对自然数作为参数,产生了另一个自然数的输出,有点像把这一对函数打包,用另一个自然数编了号。
而且这个函数是双射,也就是不同的自然数对,打包后必然对应不同的自然数。反过来,给定一个自然数,它也必然唯一的对应一对自然数。当然,这需要找出康托配对函数的逆函数形式,这个问题要比找配对函数的通项公式稍微困难点,有兴趣的读者可以挑战自己,去找一下这个逆函数的计算公式。
不管怎么说,康托配对函数的特点就是一个自然数包含了两个自然数的信息。如果拿到一对自然数,只要代入配对函数,存储计算结果,就等价于存储了这一对自然数,而且是有序对。这也是“配对函数”名称的来历。
有了这样的思路,用一个变量实现一个堆栈就很容易了,基本想法就是对配对的结果继续配对。比如这个变量初值就设为0。当数字a需要入栈时,就对(0, a)代入配对函数,把结果存储到这个变量中,假设是b。当再有数字c需要入栈时,就对(b,c)配对,得到d,存入变量。总之,当有新数字入栈时就与当前变量值配对,存入变量即可。
用康托配对函数实现堆栈的例子: 设变量a的初值为0,需要先后入栈1,2,3。 1入栈,则将(0,1)代入配对函数,并将结果存入a:

2入栈,将(1,2)代入配对函数,并将结果存入a:

3入栈,将(8,3)代入配对函数,并将结果存入a:

数字出栈时,将a的值反复代入配对函数的逆函数即可。
以上方法,我们就很简单找到了一个用一个变量就实现堆栈结构的方法。当然,实践中我们几乎不用这种方法,一个是因为这种方法的计算效率低,速度慢;另一个问题是康托配对函数的数值增长速度很快,入栈数字一多,很容易超过单个变量值的上限;所以不实用。但以上两个问题在我节目开头谈到的那种编程语言中都不是问题,所以用它来实现堆栈再合适不过了。
不管怎么说,我们成功地用配对函数实现了一个自然数集的笛卡尔积到自然数上的双射,因此我们可以确定它们的无穷基数是一样的。
那我们会联想到这样一个问题,有没有其他无穷集合上的配对函数?比如,有没有办法对全体整数配对,建立一对整数到整数集合上的双射?
方法当然是有的。因为已经有了自然数集上的配对函数,那么只要建立整数到自然数的双射,问题就解决的。而全体整数要映射到自然数,方法有很多。一种常见方法就是把负数按次序映射到奇数,正数按次序映射到偶数,0映射到0。它的转换公式如下:

这种函数数学中称为folding function/折叠函数,因为它有点像把数轴按原点对折了一下。
有折叠函数,那么整数的配对就简单了,只要把一对整数分别代入折叠函数,转换为一对自然数,然后再代入康托配对函数,这样就得到一个自然数结果。那么再把这个函数代入折叠函数的反函数,那么能把这个自然数再对应回某个整数,从而构造出了整数集的配对函数。
这个过程虽然有点曲折,但确实数学中很常用的一个思路,就是把未知问题向已知问题转化的过程。

(上图:另一种建立坐标系上整点到整数的双射的方法。请想一下通项公式怎么写。)
整数的配对函数有了,那么有理数的配对函数也有了,因为有理数也是可数集,也能建立到自然数的双射。
但是以上得到的关于整数和有理数的配对函数,它们都是分段函数,不像康托配对函数,就是一个简单的多项式表达形式。
美国数学家哈维·弗里德曼就提出了这样一个问题,能否构建一个二元的多项式函数,能够实现有理数集上的配对函数?
它的意思是:找一个多项式函数f(x,y),代入后可以算出另一个有理数。并且对不同的x,y,总能得到不同的有理数。并且,对任何一个有理数,我们总能找到恰好一对x,y,使得函数值是这个有理数,这就是双射。
但略感意外的这是到目前还未解决的问题。比如我们可以稍微求其次,先考虑单射函数。 就是只要不同的x,y,总能得到不同的函数值就可以。
你可以稍微思考一下,你会感觉到这似乎是有可能的。当然,首先因为负负得正的关系,你会考虑要避免指数上出现偶数, 感觉上指数是奇数再稍微复杂点就可以。比如有人猜想,

就是这样一个单射函数。
比如对方程:

除了(1,1) 以外,还有没有其他的有理数解呢?看上去是没有了。但是意外的是目前数学家还没能确切地证明

是一个单射函数。
如果再加入“满射”这一条件,那问题当然就更难了。根据陶哲轩的一篇博客,他几乎肯定不存在哈维·弗里德曼问的那个二元有理数函数到有理数集合上的双射多项式函数。

那今天的内容就到这里。我的感想是,我从一个实践中的编程问题,了解到了配对函数这个数学中非常有意思的概念,进而最后还发现数学中还未解决的哪怕是二元有理数多项式的单射证明,这数论里面的“水”真的是深不可测!
参考链接:
https://mathworld.wolfram.com/PairingFunction.html
https://stackoverflow.com/questions/919612/mapping-two-integers-to-one-in-a-unique-and-deterministic-way
https://terrytao.wordpress.com/2019/06/08/ruling-out-polynomial-bijections-over-the-rationals-via-bombieri-lang/