素?cái)?shù)

稍微學(xué)過(guò)數(shù)學(xué)的人都很清楚素?cái)?shù)（質(zhì)數(shù)）這一概念，它被定義為：在大于1的自然數(shù)中，除了1和它本身以外不再有其他因數(shù)。

比如說(shuō)，2、3、5、7、11……

形式系統(tǒng)

形式系統(tǒng)就不那么接地氣了，恐怕沒(méi)幾個(gè)人聽(tīng)說(shuō)過(guò)。我們可以把形式系統(tǒng)當(dāng)做數(shù)學(xué)中的公理系統(tǒng)。回憶數(shù)學(xué)課本上的定理是怎么出現(xiàn)的：

給定公理1、公理2；
計(jì)算、推導(dǎo)；
得到結(jié)論，即定理。

這里的公理是不需證明的定理，中間的推導(dǎo)過(guò)程是對(duì)公理的合乎規(guī)則的操作，定理則是推導(dǎo)出的新的結(jié)論，整個(gè)過(guò)程即是“證明”。

形式系統(tǒng)與公理系統(tǒng)類似，其實(shí)，形式系統(tǒng)是對(duì)公理系統(tǒng)的形式化抽象。形式系統(tǒng)由三大要素構(gòu)成：形式語(yǔ)言、推理規(guī)則和公理集合。

我們很容易將這三個(gè)要素與前面定理的證明過(guò)程聯(lián)系起來(lái)。形式語(yǔ)言是公理和定理的載體，或者說(shuō)是它們的表示形式；推理規(guī)則是推導(dǎo)過(guò)程中必須遵守的規(guī)則；公理集合是給定的所有公理的集合。

這些話都太過(guò)于抽象，不能再多說(shuō)下去了，我們還是看看如何構(gòu)建一個(gè)可以表示素?cái)?shù)的形式系統(tǒng)吧。

素?cái)?shù)的形式化表述

我們要構(gòu)建一個(gè)形式系統(tǒng)，該形式系統(tǒng)的定理都寫(xiě)作Px。其中x是由任意多個(gè)'-'組成的字符串。

這里的Px就是所謂的形式語(yǔ)言，符合Px形式的字符串在該形式系統(tǒng)中被認(rèn)為是有意義的。但有意義的字符串并不一定都是定理，我們規(guī)定，只有當(dāng)x中的'-'數(shù)目為素?cái)?shù)時(shí)，Px是一個(gè)定理，否則Px無(wú)意義。比如，P---是個(gè)定理，而P----則不是。

現(xiàn)在，我們得想出一些規(guī)則來(lái)產(chǎn)生有效的Px了。

回到現(xiàn)實(shí)世界，要想判斷一個(gè)數(shù)N是否是素?cái)?shù)，只需要判定N是否能夠整除2～N-1之間的任何一個(gè)自然數(shù)，如果都不能，那么N是素?cái)?shù)，否則不是。用形式話的語(yǔ)言表述這件事并不容易，我們需要能夠判定整除的規(guī)則，然后是判定一個(gè)數(shù)不能被2~N-1之間任意一個(gè)數(shù)整除的規(guī)則，最后得到這個(gè)數(shù)是素?cái)?shù)。

第一步，不可整除性：

定義1：xBZCy，其中x和y是'-'組成的字符串。
規(guī)則1：若xBZCy是個(gè)定理，則xBZCxy是個(gè)定理。

我們可以把定義1的含義理解成y不能被x整除。那么規(guī)則1就可以理解為，如果y不能被x整除，那么x+y也不能被x整除。

第二步，連續(xù)不可整除性：

定義2：zMYx，其中z和x是'-'組成的字符串。
規(guī)則2：如果--BZCz是個(gè)定理，則zMY--是個(gè)定理。
規(guī)則3：如果zMYx與x-BZCz都是定理，則zMYx-是個(gè)定理。

我們可以把定義2的含義理解成在2和x之間沒(méi)有能整除z的數(shù)。那么規(guī)則2可以理解為，如果z不能被2整除，那么在2和2之間沒(méi)有能整除z的數(shù)。規(guī)則3可以理解為如果在2和x之間沒(méi)有能整除z的數(shù)，且z不能被x+1整除，那么在2和x+1之間沒(méi)有能整除z的數(shù)。有點(diǎn)數(shù)學(xué)歸納法的感覺(jué)了吧。

第三步，素?cái)?shù)：

規(guī)則4：若z-MYz是個(gè)定理，則Pz-是個(gè)定理。
公理：P--。

規(guī)則4可以理解為，如果在2和z之間沒(méi)有能整除z+1的數(shù)，那么z+1是素?cái)?shù)。這正是我們想要的素?cái)?shù)的定義！當(dāng)然，不要忘了最后一條公理，2是素?cái)?shù)。

大功告成了，之所以把一句話拆分成這么多條復(fù)雜的定義和規(guī)則，就是為了能夠形式化、沒(méi)有歧義地構(gòu)造素?cái)?shù)的判定過(guò)程。

我知道看到這里的人肯定是懵逼的，上面寫(xiě)了些什么，其實(shí)我也沒(méi)能全部理解。但無(wú)疑形式系統(tǒng)是很有趣的，它可以讓我們用數(shù)學(xué)的方法描述世界。如果你注意到我在解釋規(guī)則的時(shí)候都用了“可以”這個(gè)詞，就能想象其實(shí)形式系統(tǒng)并不是那么具體，它既可以這樣解釋，也可以有其它不同的解釋。所以說(shuō)形式系統(tǒng)是一種抽象，是對(duì)任何事物的邏輯抽象，這也是數(shù)學(xué)的強(qiáng)大之處。

參考資料

《哥德?tīng)枴釥?、巴赫：集異壁之大成?侯世達(dá)
【數(shù)理邏輯如何入門(mén)】：公理系統(tǒng)和形式系統(tǒng) 豆瓣/邏輯