這篇文章的話題源自來自于大老李最近的一次編程經(jīng)歷。上兩月，我在用一個很奇怪的語言編程。這種編程語言里變量類型只有正整數(shù)，沒有小數(shù)和負(fù)數(shù)。變量的操作也只有加、減和乘，沒有除法，有些基本的循環(huán)結(jié)構(gòu)和變量大小的判斷等等。

這種編程語言聽上去是很簡陋，你先不用管為什么我要用這種語言編程，以后有機(jī)會聊。就這種語言，我遇到了一個很大的編程困難是，我需要一個堆棧(Stack)數(shù)據(jù)結(jié)構(gòu)。在其他任何支持?jǐn)?shù)組或者列表的編程語言里，實(shí)現(xiàn)堆棧完全不是問題。堆棧就是從數(shù)組最末尾開始存取的一個數(shù)據(jù)結(jié)構(gòu)。

但我現(xiàn)在使用的這種編程語言里，內(nèi)置的除了整數(shù)型變量，沒有任何數(shù)據(jù)結(jié)構(gòu)。那有沒有辦法實(shí)現(xiàn)一個堆棧呢？上網(wǎng)搜了下，還真有，而且方法其實(shí)很簡單。這個方法是先考慮這樣一個問題：有沒有可能找到一對自然數(shù)與全體自然數(shù)的一一對應(yīng)。

這里簡單介紹下無窮基數(shù)理論。簡單來說，無窮基數(shù)理論提出了這樣一種比較具有無窮多元素的集合大小的方法，就是看兩個無窮集合中的元素是否能建立一一對應(yīng)的關(guān)系，其實(shí)在函數(shù)語言里，這種性質(zhì)叫“雙射”。稍微解釋下雙射函數(shù)。其實(shí)先得知道兩個概念，“單射”和“滿射”。

比如有個函數(shù)叫y=f(x)，如果代入不同的x，總是得到不同的y，那么這個函數(shù)就叫“單射”。單射是一種很重要的函數(shù)性質(zhì)，比如二次曲線和多數(shù)三角函數(shù)都不是單射。

還有一個概念叫“滿射”，意思是函數(shù)的值域被填滿了。也就是任何一個值域里的值，代入y，總能找到一個x，使得f(x)=y。實(shí)數(shù)函數(shù)

就不是滿射，因?yàn)閥是負(fù)數(shù)的時候，就找不到對應(yīng)的x。

那一個函數(shù)即是單射又是滿射的時候，我們就叫它“雙射”。

如果存在兩個無窮集合元素之間的雙射，我們就認(rèn)為這兩個無窮集合的“大小”是一樣的。而且已經(jīng)證明，無窮集合中，“最小”的就是自然數(shù)集合。有意思的是，可以建立偶數(shù)到全體自然數(shù)的雙射，也就是在無窮基數(shù)理論的范疇下，偶數(shù)與全體自然數(shù)“一樣多”。這是“無窮”概念給我們造成的反直覺結(jié)論之一。

那現(xiàn)在考慮這樣一個集合，其元素是自然數(shù)對，比如(1,2), (100,200 )等等，也包括（0, 0)。本文中，自然數(shù)是包括0的。那么這個成對自然數(shù)的集合直觀形象就是笛卡爾坐標(biāo)系第一象限中的縱橫坐標(biāo)都是整數(shù)的點(diǎn)，再加上x和y軸正方向上的整數(shù)點(diǎn)和原點(diǎn)。有時我們說這種成對的自然數(shù)集合，為自然數(shù)集合的“笛卡爾積”就是這個道理。

現(xiàn)在的問題是：自然數(shù)集合的笛卡爾積能否建立與自然數(shù)的一一對應(yīng)，即雙射呢？

從直覺上來看確實(shí)是可以，我們只要想一個辦法把這些點(diǎn)按某種順序羅列出來，做到既不重復(fù)也不遺漏就可以了。排列出來后，就相當(dāng)于給這些點(diǎn)用自然數(shù)編了號，那么雙射就自然成立了。

具體怎么做呢？其實(shí)有不止一種方法，數(shù)學(xué)家康托當(dāng)初使用了一種像一筆畫一樣方法，按對角線方向來回往復(fù)的對這些點(diǎn)進(jìn)行連接和排序。

比如，按他的方法，自然數(shù)對排列的最開始三項(xiàng)就是(0,0)， (1,0)和(0，1)。它們就會對應(yīng)自然數(shù)0到2。它的通項(xiàng)公式如下：

這個通項(xiàng)公式就被稱為“康托配對函數(shù)”，因?yàn)樗×艘粚ψ匀粩?shù)作為參數(shù)，產(chǎn)生了另一個自然數(shù)的輸出，有點(diǎn)像把這一對函數(shù)打包，用另一個自然數(shù)編了號。

而且這個函數(shù)是雙射，也就是不同的自然數(shù)對，打包后必然對應(yīng)不同的自然數(shù)。反過來，給定一個自然數(shù)，它也必然唯一的對應(yīng)一對自然數(shù)。當(dāng)然，這需要找出康托配對函數(shù)的逆函數(shù)形式，這個問題要比找配對函數(shù)的通項(xiàng)公式稍微困難點(diǎn)，有興趣的讀者可以挑戰(zhàn)自己，去找一下這個逆函數(shù)的計(jì)算公式。

不管怎么說，康托配對函數(shù)的特點(diǎn)就是一個自然數(shù)包含了兩個自然數(shù)的信息。如果拿到一對自然數(shù)，只要代入配對函數(shù)，存儲計(jì)算結(jié)果，就等價于存儲了這一對自然數(shù)，而且是有序?qū)?。這也是“配對函數(shù)”名稱的來歷。

有了這樣的思路，用一個變量實(shí)現(xiàn)一個堆棧就很容易了，基本想法就是對配對的結(jié)果繼續(xù)配對。比如這個變量初值就設(shè)為0。當(dāng)數(shù)字a需要入棧時，就對(0, a)代入配對函數(shù)，把結(jié)果存儲到這個變量中，假設(shè)是b。當(dāng)再有數(shù)字c需要入棧時，就對(b,c)配對，得到d，存入變量。總之，當(dāng)有新數(shù)字入棧時就與當(dāng)前變量值配對，存入變量即可。

用康托配對函數(shù)實(shí)現(xiàn)堆棧的例子： 設(shè)變量a的初值為0，需要先后入棧1,2,3。 1入棧，則將(0,1)代入配對函數(shù)，并將結(jié)果存入a:

2入棧，將(1,2)代入配對函數(shù)，并將結(jié)果存入a:

3入棧，將(8,3)代入配對函數(shù)，并將結(jié)果存入a:

數(shù)字出棧時，將a的值反復(fù)代入配對函數(shù)的逆函數(shù)即可。

以上方法，我們就很簡單找到了一個用一個變量就實(shí)現(xiàn)堆棧結(jié)構(gòu)的方法。當(dāng)然，實(shí)踐中我們幾乎不用這種方法，一個是因?yàn)檫@種方法的計(jì)算效率低，速度慢；另一個問題是康托配對函數(shù)的數(shù)值增長速度很快，入棧數(shù)字一多，很容易超過單個變量值的上限；所以不實(shí)用。但以上兩個問題在我節(jié)目開頭談到的那種編程語言中都不是問題，所以用它來實(shí)現(xiàn)堆棧再合適不過了。

不管怎么說，我們成功地用配對函數(shù)實(shí)現(xiàn)了一個自然數(shù)集的笛卡爾積到自然數(shù)上的雙射，因此我們可以確定它們的無窮基數(shù)是一樣的。

那我們會聯(lián)想到這樣一個問題，有沒有其他無窮集合上的配對函數(shù)？比如，有沒有辦法對全體整數(shù)配對，建立一對整數(shù)到整數(shù)集合上的雙射？

方法當(dāng)然是有的。因?yàn)橐呀?jīng)有了自然數(shù)集上的配對函數(shù)，那么只要建立整數(shù)到自然數(shù)的雙射，問題就解決的。而全體整數(shù)要映射到自然數(shù)，方法有很多。一種常見方法就是把負(fù)數(shù)按次序映射到奇數(shù)，正數(shù)按次序映射到偶數(shù)，0映射到0。它的轉(zhuǎn)換公式如下：

這種函數(shù)數(shù)學(xué)中稱為folding function/折疊函數(shù)，因?yàn)樗悬c(diǎn)像把數(shù)軸按原點(diǎn)對折了一下。

有折疊函數(shù)，那么整數(shù)的配對就簡單了，只要把一對整數(shù)分別代入折疊函數(shù)，轉(zhuǎn)換為一對自然數(shù)，然后再代入康托配對函數(shù)，這樣就得到一個自然數(shù)結(jié)果。那么再把這個函數(shù)代入折疊函數(shù)的反函數(shù)，那么能把這個自然數(shù)再對應(yīng)回某個整數(shù)，從而構(gòu)造出了整數(shù)集的配對函數(shù)。

這個過程雖然有點(diǎn)曲折，但確實(shí)數(shù)學(xué)中很常用的一個思路，就是把未知問題向已知問題轉(zhuǎn)化的過程。

（上圖：另一種建立坐標(biāo)系上整點(diǎn)到整數(shù)的雙射的方法。請想一下通項(xiàng)公式怎么寫。）

整數(shù)的配對函數(shù)有了，那么有理數(shù)的配對函數(shù)也有了，因?yàn)橛欣頂?shù)也是可數(shù)集，也能建立到自然數(shù)的雙射。

但是以上得到的關(guān)于整數(shù)和有理數(shù)的配對函數(shù)，它們都是分段函數(shù)，不像康托配對函數(shù)，就是一個簡單的多項(xiàng)式表達(dá)形式。

美國數(shù)學(xué)家哈維·弗里德曼就提出了這樣一個問題，能否構(gòu)建一個二元的多項(xiàng)式函數(shù)，能夠?qū)崿F(xiàn)有理數(shù)集上的配對函數(shù)？

它的意思是：找一個多項(xiàng)式函數(shù)f(x,y)，代入后可以算出另一個有理數(shù)。并且對不同的x,y，總能得到不同的有理數(shù)。并且，對任何一個有理數(shù)，我們總能找到恰好一對x,y，使得函數(shù)值是這個有理數(shù)，這就是雙射。

但略感意外的這是到目前還未解決的問題。比如我們可以稍微求其次，先考慮單射函數(shù)。 就是只要不同的x,y，總能得到不同的函數(shù)值就可以。

你可以稍微思考一下，你會感覺到這似乎是有可能的。當(dāng)然，首先因?yàn)樨?fù)負(fù)得正的關(guān)系，你會考慮要避免指數(shù)上出現(xiàn)偶數(shù)， 感覺上指數(shù)是奇數(shù)再稍微復(fù)雜點(diǎn)就可以。比如有人猜想，

就是這樣一個單射函數(shù)。

比如對方程:

除了(1,1) 以外，還有沒有其他的有理數(shù)解呢？看上去是沒有了。但是意外的是目前數(shù)學(xué)家還沒能確切地證明

是一個單射函數(shù)。

如果再加入“滿射”這一條件，那問題當(dāng)然就更難了。根據(jù)陶哲軒的一篇博客，他幾乎肯定不存在哈維·弗里德曼問的那個二元有理數(shù)函數(shù)到有理數(shù)集合上的雙射多項(xiàng)式函數(shù)。

那今天的內(nèi)容就到這里。我的感想是，我從一個實(shí)踐中的編程問題，了解到了配對函數(shù)這個數(shù)學(xué)中非常有意思的概念，進(jìn)而最后還發(fā)現(xiàn)數(shù)學(xué)中還未解決的哪怕是二元有理數(shù)多項(xiàng)式的單射證明，這數(shù)論里面的“水”真的是深不可測！

參考鏈接：

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/