【原】小樂(lè)數(shù)學(xué)科普：當(dāng)1+1+1等于1時(shí)——James Propp教授專欄

zzllrr小樂(lè) 2024-12-21 發(fā)布于江蘇

展開(kāi)全文

本文開(kāi)場(chǎng)曲——吉格舞曲“愛(ài)爾蘭浣女” The Irish Washerwoman

（作者在文中舉例時(shí)有用到）

作者：James Propp教授 2024-12-19

譯者：zzllrr小樂(lè)（數(shù)學(xué)科普公眾號(hào)）2024-12-21

有各種各樣的數(shù)學(xué)運(yùn)算（操作），其特性是執(zhí)行兩次運(yùn)算等于什么都不做。這樣的運(yùn)算被稱為對(duì)合（involution），你可以在數(shù)學(xué)中隨處找到它們：取一個(gè)數(shù)的負(fù)數(shù)，取一個(gè)數(shù)的倒數(shù)，將一個(gè)物體旋轉(zhuǎn)180度 1，否定一個(gè)命題，取一個(gè)集合的補(bǔ)集，我可以繼續(xù)舉例······。

當(dāng)執(zhí)行 X 兩次相當(dāng)于什么都不做時(shí)，那么執(zhí)行 X 三次相當(dāng)于執(zhí)行 X 一次，執(zhí)行 X 四次相當(dāng)于執(zhí)行 X 兩次，依此類推。在這種情況下，要知道當(dāng)你多次執(zhí)行 X 時(shí)會(huì)發(fā)生什么，只需知道你執(zhí)行 X 的次數(shù)n是偶數(shù)還是奇數(shù)。如果 n 是奇數(shù)，則執(zhí)行 n 次運(yùn)算與執(zhí)行一次相同；如果 n 為偶數(shù)，則執(zhí)行 n 次運(yùn)算與什么都不做相同。（參見(jiàn)我之前的文章“當(dāng) 1+1 等于 0 時(shí)”）。

試圖對(duì)所有這種行為方式的數(shù)學(xué)運(yùn)算進(jìn)行分類，甚至只對(duì)重要的數(shù)學(xué)運(yùn)算進(jìn)行分類，將是一項(xiàng)艱巨的任務(wù)，而我今天的目標(biāo)不是進(jìn)行這樣的綜合調(diào)查。但是還有其他一些運(yùn)算并不完全是對(duì)合 – 可以稱它們?yōu)?/span>“準(zhǔn)對(duì)合” 2 – 它們具有做 3 次等于做 1 次、做 4 次等于做 2 次等性質(zhì)。這些較罕見(jiàn)的運(yùn)算是我今天的主題。

對(duì)于這類運(yùn)算，如果你想知道當(dāng)你做一個(gè)運(yùn)算 n 次時(shí)會(huì)發(fā)生什么，按n 是正奇數(shù)、正偶數(shù)還是零，對(duì)應(yīng)三種情況 3 。與“0、1、0、1、0、1······”的模2算術(shù)不同，控制這些運(yùn)算的計(jì)數(shù)類型是“0、1、2、1、2、1、2······”。

下面我給你看三個(gè)例子。其中前兩個(gè)是技術(shù)性的，但第三個(gè)很容易理解，值得被更多地了解。如果前兩個(gè)看起來(lái)太神秘，請(qǐng)隨意跳到第三個(gè)。

正交補(bǔ) Orthocomplementation

我們的第一個(gè)例子來(lái)自線性代數(shù)，但為了方便起見(jiàn)，我將切換到三維幾何，以通常的方式配備 x、y 和 z 坐標(biāo)。給定此空間中的一組直線的集合 S，設(shè) Perp(S)或者P(S) 為垂直于 S 中每條直線的所有直線的集合。例如，假設(shè) S 由三條在xy-平面上圍出一個(gè)三角形的直線組成。然后，P(S) 由平行于 z 軸的所有直線組成，P(P(S)) 由平行于xy-平面的所有直線組成，P(P(P(S))) 由平行于z軸的所有直線組成，依此類推。P(P(S)) 與 S 不同，但 P(P(P(S))) 與 P(S) 相同。

如果我們?cè)O(shè) S 是由三條相互垂直的直線組成的集合，就會(huì)出現(xiàn)一個(gè)更令人費(fèi)解的例子。那么 P(S) 根本不包含任何直線；也就是說(shuō)，它是空集，也寫成 { }。那么，在這種情況下，我們應(yīng)該如何看待 P(P(S)) 呢？也就是說(shuō)，P({ }) 到底是什么？如果你做了很多數(shù)學(xué)運(yùn)算，你就可以猜到會(huì)發(fā)生什么，因?yàn)槟阋郧耙?jiàn)過(guò)我們數(shù)學(xué)家這樣做：我們將“我見(jiàn)過(guò)愛(ài)爾蘭的每一只獨(dú)角獸”這樣的斷言視為（空洞的）正確的。（如果你認(rèn)為我聲稱見(jiàn)過(guò)愛(ài)爾蘭的所有獨(dú)角獸的陳述是錯(cuò)的，那就請(qǐng)你找出一只我沒(méi)見(jiàn)過(guò)的；事實(shí)上，因?yàn)閻?ài)爾蘭沒(méi)有獨(dú)角獸，所以我聲稱見(jiàn)過(guò)愛(ài)爾蘭所有的獨(dú)角獸，肯定是一句正確但空洞的話）

因此，對(duì)于平面中的每一條直線 L，L 垂直于 { } 的每一條直線（因?yàn)?{ } 中沒(méi)有一條直線是不垂直于 L 的，事實(shí)上，因?yàn)?{ } 中根本沒(méi)有直線），這意味著 P({ }) 是我們空間中所有直線L 的完全集合（全集）。因此我們看到，當(dāng) S 由三條相互垂直的直線組成時(shí)，P(S) = { } 是不包含任何直線的集合，而P(P(S)) 是包含所有直線的集合，P(P(P(S)))是不包含任何直線的集合，依此類推。同樣，P(P(S)) 與 S 不同，但 P(P(P(S)) 與 P(S) 相同。

這并非巧合：可以證明 P(P(P(S)) 與 P(S) 始終相同。

連續(xù)執(zhí)行兩次 Perp（取垂直線 perpendicular）是一種數(shù)學(xué)家所說(shuō)的 “閉包” （closure operation）的例子。閉包運(yùn)算是一種具有這種性質(zhì)的運(yùn)算（操作）：一個(gè)事物的閉包的閉包與這個(gè)事物的閉包相同。也就是說(shuō)，它是執(zhí)行 “兩次等于一次” 的那種操作 ? 。如果把C(S)定義為 P(P(S))，則 C(C(S)) 為 P(P(P(P(S))))，等于 P(P(S))，即 C(S)；所以 C 是一種閉包操作。

通常，操作 Perp 應(yīng)用于向量空間（或者更技術(shù)上稱為內(nèi)積空間 inner-product space）。你有一些大的向量空間 V 和一些較小的位于 V 內(nèi)部的向量空間 W 。然后 Perp(W) 是位于V 內(nèi)部的另一個(gè)向量空間，Perp(Perp(W)) 也是如此，依此類推。當(dāng) V 是有限維的向量空間時(shí)，Perp(Perp(W)) 始終等于 W，但在無(wú)限維空間中這不再是正確的。盡管如此，在那些無(wú)限維空間中，Perp(Perp(Perp(W))) 始終等于 Perp(W) 仍然是正確的。因此，Perp 是執(zhí)行“三次等于一次”（thrice-equals-once）操作的一個(gè)示例。Perp(W) 被稱為 W 的“正交補(bǔ)”（orthogonal complement，orthocomplement）——因此作為本節(jié)的標(biāo)題。

直覺(jué)主義否定 Intuitionistic Negation

我們本文三個(gè)“三次等于一次”的運(yùn)算（操作）案例中最奇怪的是非經(jīng)典（更具體地說(shuō)，構(gòu)造主義）框架中的邏輯否定。在這里，我使用“構(gòu)造主義的”（constructivist）這個(gè)詞來(lái)表示 20 世紀(jì)出現(xiàn)的一種邏輯風(fēng)格，而不是英文同名的教育運(yùn)動(dòng)（建構(gòu)主義）。構(gòu)造主義（constructivism）類似于另一個(gè)叫做 “直覺(jué)主義” （intuitionism）的運(yùn)動(dòng)，并且確實(shí)與之糾纏不清，事實(shí)上，我所說(shuō)的那種邏輯通常被稱為直覺(jué)邏輯（intuitionistic logic）。在構(gòu)造主義的設(shè)置中，斷言“非p” 的意思更接近于斷言“我有一個(gè)程序，以給定的 p 的證明作為輸入，以 0 = 1 的證明作為輸出”（你可以用任何你喜歡的假命題替換 0 = 1）。在經(jīng)典邏輯中，“p 或非p” 是一個(gè)老生常談，稱為排除中間定律，但這個(gè)定律在直覺(jué)邏輯中不再有效。事實(shí)上，拒絕排除中間的定律（排中律）是數(shù)學(xué)直覺(jué)主義風(fēng)格的核心。在這種觀點(diǎn)下，如果你無(wú)法證明 p 是真的，也不能證明非 p 是真的，那么你就沒(méi)有理由聲稱知道 “p 或非p” 是真的。因此，如果一個(gè)不果斷的哈姆雷特說(shuō)“明天我要么生存（be），要么毀滅（not be）”，直覺(jué)主義者會(huì)反駁這個(gè)斷言，或者至少反駁哈姆雷特聲稱知道它的理由。

在直覺(jué)主義邏輯中，“非非p” 不等同于 p，但盡管如此，p 仍然蘊(yùn)含著“非非p”，盡管我將用“產(chǎn)生 yield”一詞替換“蘊(yùn)含 imply”一詞，以阻止您經(jīng)典地解釋該斷言。讓我們看看為什么 p 會(huì)產(chǎn)生“非非p”。用符號(hào)表示，p 的直覺(jué)主義否定寫為 p ? ⊥，其中 ⊥（將其視為T的顛倒，T表示True真）表示不可能是真的（有時(shí)稱為“假” falsehood——可能性為假），p ? q 表示“p 的證明產(chǎn)生 q 的證明”。因此，為了證明 p 產(chǎn)生 “非非p”，我們必須證明 p 的證明會(huì)產(chǎn)生 (p ? ⊥) ? ⊥ 的證明。在這里，我們可以使用經(jīng)典邏輯規(guī)則的直覺(jué)主義版本，稱為 modus ponens（假言推理，分離規(guī)則），它斷言如果 p 為真并且 p ? q 為真，則 q 為真，或者等價(jià)地說(shuō)，如果 p 為真，則 (p ? q) ? q 為真。直覺(jué)主義版本說(shuō)“如果你有一個(gè) p 的證明，那么你有一個(gè)程序可以將 p ? q 的每個(gè)證明都變成 q 的證明?！?將 q 替換為 ⊥，我們得到我們想要的結(jié)果。

由于 p 對(duì)所有 p 都產(chǎn)生 “非非p”，我們可以用 “非非p” 替換 p 以獲得另一個(gè)直覺(jué)上有效的斷言：“非p” 產(chǎn)生 “非非非p”。我聲稱相反的含義也成立：即，“非非非p” 產(chǎn)生 “非p”。為了證明它（非正式地），假設(shè)我們得到了 “非非非p”。我們必須產(chǎn)生“非p”，也就是說(shuō)，我們必須產(chǎn)生 p ? ⊥。要做到這一點(diǎn)，只需將 p 視為已知給定條件，看看我們是否可以產(chǎn)生 ⊥。也就是說(shuō)，我們處于這樣一種情況：我們得到了 “非非非p” 和 p，我們想用這些成分產(chǎn)生 ⊥。但在前面一段中，我們證明了 p 產(chǎn)生 “非非p”，因此我們免費(fèi)得到了第三種成分，“非非p”，我們的目標(biāo)是使用 “非非非p”、p 和 “非非p” 來(lái)產(chǎn)生 ⊥。我們似乎正在偏離軌道，但我們幾乎完成了?？纯催@三種成分中的第一種和第三種，即 “非非非p” 和 “非非p”。前者等價(jià)于 “非非p” ? ⊥，因此我們可以將其與 “非非p” 相結(jié)合得出⊥。因此，我們已經(jīng)成功地證明了 “非非非p” ? “非p”，即便如果你的大腦和我一樣，你也不太明白這個(gè)技巧是如何完成的。

（這個(gè)證明讓我想起了小說(shuō)《好兆頭》Good Omens的開(kāi)頭，其中三個(gè)嬰兒被調(diào)換得如此頻繁，以至于我永遠(yuǎn)無(wú)法理解它！）

無(wú)論如何，既然我們已經(jīng)證明了 “非p” 蘊(yùn)含著 “非非非p”，反之亦然，我們已經(jīng)證明了 “非p” 和 “非非非p” 在邏輯上是直覺(jué)主義意義的等價(jià)物，所以直覺(jué)主義否定是“三次等于一次”操作的另一個(gè)例子。?

網(wǎng)絡(luò) Networks

我們的最后一個(gè)例子來(lái)自組合學(xué)，更具體地說(shuō)是圖論，但我會(huì)把它表述為人們?cè)谏缃痪W(wǎng)絡(luò)中相互聯(lián)系的方式。想象一個(gè)網(wǎng)絡(luò)，其中節(jié)點(diǎn)對(duì)應(yīng)于人，兩個(gè)節(jié)點(diǎn)之間的鏈接表明兩個(gè)鏈接的人彼此認(rèn)識(shí)。（我將假設(shè)如果 A 認(rèn)識(shí) B ，那么 B 就認(rèn)識(shí) A 。）然后，對(duì)于網(wǎng)絡(luò)中的任何一組人員的集合S，我們可以將 K(S) 定義為認(rèn)識(shí) S 中每個(gè)人的一組人員的集合。

很容易將 K(S) 與認(rèn)識(shí) S 中某個(gè)人的那群人的集合混淆，所以讓我舉一個(gè)例子來(lái)幫助消除混淆。

假設(shè)我們的網(wǎng)絡(luò)由六個(gè)人 a、b、c、d、e 和 f 組成，如上圖所示，當(dāng)兩個(gè)相應(yīng)的人彼此認(rèn)識(shí)時(shí)，兩個(gè)節(jié)點(diǎn)通過(guò)鏈接連接起來(lái)。設(shè)集合 S 為，其唯一元素為 b 。那么 K(S) 由 b 認(rèn)識(shí)的每個(gè)人組成，所以 K(S) 由 d 和 e 組成。現(xiàn)在，在它們兩個(gè)之間，d 和 e 認(rèn)識(shí) a、b 和 c，但 b 和 c 是 d 和 e 都認(rèn)識(shí)的，所以它們是 K(K(S)) 中僅含有的元素。也就是說(shuō)，K(K(S)) 是 {b，c}，而不是 {a，b，c}。那么 K(K(K(S))) 呢？你應(yīng)該檢查它是否為 {d，e} —— 與 K(S) 相同。

我第一次遇到這種 K-運(yùn)算時(shí)，我還是伯克利的一名數(shù)學(xué)研究生，當(dāng)時(shí)我正在為我的預(yù)考做準(zhǔn)備；其中一個(gè)練習(xí)題要求我們（用圖論術(shù)語(yǔ)）證明 K(K(K(S))) 等于 K(S)，而不管網(wǎng)絡(luò)的細(xì)節(jié)如何。我想這個(gè)問(wèn)題一定是某種“栗子”（盡管它長(zhǎng)在一棵相當(dāng)特殊的“樹”上），而且我在職業(yè)生涯的后期會(huì)遇到它，然而我從來(lái)沒(méi)有遇到過(guò)。大約三十年后，我判斷這樣一個(gè)好問(wèn)題值得廣泛的讀者關(guān)注，如果還沒(méi)有人寫過(guò)關(guān)于它的文章，那么這個(gè)責(zé)任就落在了我身上。因此，我發(fā)表了一篇名為“社交網(wǎng)絡(luò)中的伽羅瓦連接”（A Galois Connection in the Social Network，《數(shù)學(xué)雜志》 Mathematics Magazine 85卷，34-36頁(yè) https://faculty./jpropp/galois.pdf ）的文章，描述了這個(gè)問(wèn)題，證明了結(jié)果，并將其與一些更高級(jí)的數(shù)學(xué)聯(lián)系起來(lái)。（上圖改編自該文章）。

斷言 K(K(K(S))) 的每個(gè)元素都是 K(S) 的一個(gè)元素，反之， K(S) 的每個(gè)元素都是 K(K(K(S))) 的一個(gè)元素，可以在 S 僅包含一個(gè)人的特殊情況下表示為：“認(rèn)識(shí)所有認(rèn)識(shí)所有認(rèn)識(shí)你的人都是你認(rèn)識(shí)的人，而你認(rèn)識(shí)的人都是認(rèn)識(shí)所有認(rèn)識(shí)所有認(rèn)識(shí)你的人。” 按照吉格舞曲“The Irish Washerwoman”的曲調(diào)唱出這些詞的練習(xí)留給喜歡音樂(lè)的讀者。

相同還是不同？

由于這篇文章是關(guān)于 “一等于三 ”的情況，所以第1個(gè)例子實(shí)際上是偽裝的第3個(gè)例子，這種說(shuō)法再合適不過(guò)的了。你可以在我的《數(shù)學(xué)雜志》文章中讀到 K(K(S)) = K(S) 的證明，其中并未假設(shè)網(wǎng)絡(luò)是有限的。因此，在第一個(gè)例子的幾何情況中，想象直線是人，而兩條直線恰好在垂直時(shí)是朋友。在此上下文中，K 是 Perp，因此 K(K(K(S))) = K(S) 意味著 Perp(Perp(Perp(S))) = Perp(S)。

第二個(gè)例子是否與其他兩個(gè)例子相同？我將讓讀者在評(píng)論部分澄清這一點(diǎn)，因?yàn)槲乙呀?jīng)晚了兩天發(fā)布這篇博客。

同時(shí)，讓我承認(rèn)這篇文章的早期版本包含一個(gè)錯(cuò)誤。在點(diǎn)集拓?fù)渲?，有一個(gè)操作（運(yùn)算）稱為取拓?fù)淇臻g的子集 S 的外部（我們將其寫為 Ext(S)），多年來(lái)，我一直認(rèn)為 Ext(Ext(Ext(S))) 始終等于 Ext(S)。但我最終意識(shí)到，這種相等性可能會(huì)失敗。幫助我弄清楚這一點(diǎn)的一件事是 Kuratowski 的閉包補(bǔ)問(wèn)題的證明百科Proof Wiki文章https:///wiki/Kuratowski%27s_Closure-Complement_Problem 。這種相等有時(shí)會(huì)失敗，但 Ext(Ext(Ext(Ext(S)))) 等于 Ext(Ext(S)) 始終是正確的。所以 Ext 是我所知道的“1+1+1+1 等于 1+1”（但1+1+1 不等于 1）的唯一例子。

說(shuō)到網(wǎng)絡(luò)資源，你可能已經(jīng)注意到，多年來(lái)我經(jīng)常向我博客的讀者推薦相關(guān)的維基百科頁(yè)面。維基媒體基金會(huì)（Wikimedia Foundation）在信息生態(tài)系統(tǒng)中發(fā)揮著至關(guān)重要的作用，因此如果您最近沒(méi)有這樣做，請(qǐng)?jiān)诖藭r(shí)支持它！捐款可以免稅，有助于保持互聯(lián)網(wǎng)健康。

尾注

#1. 在量子物理學(xué)中，如果你正在處理那種叫做費(fèi)米子（fermion）的物體，那么物體繞軸旋轉(zhuǎn)180度不是對(duì)合，而旋轉(zhuǎn)360度才是！這個(gè)話題值得一寫，而且最終會(huì)有一篇文章來(lái)介紹它，但在那之前，你可以從我過(guò)去的文章中學(xué)到更多的東西《帶鋸片、臭蟲滅火器、橡皮筋和我》和《漢密爾頓的四元數(shù)或三元數(shù)的麻煩》（參閱小樂(lè)數(shù)學(xué)科普：漢密爾頓（愛(ài)爾蘭詩(shī)人數(shù)學(xué)家）的四元數(shù)，或三元數(shù)的麻煩）。

#2. 據(jù)我所知，最接近描述此類操作的技術(shù)術(shù)語(yǔ)是“三階的冪等”。

#3. 在這些設(shè)置中，數(shù)字 0 的古怪狀態(tài)讓我想起了我的離散數(shù)學(xué)課程中的許多學(xué)生在吸收 0 是偶數(shù)這一事實(shí)時(shí)遇到的困難。我在上課的第一周解釋了為什么 0 是偶數(shù)，并回到了整個(gè)學(xué)期如何定義“偶數(shù)”和“奇數(shù)”的話題，但是，到了考試時(shí)，我還是會(huì)收到一兩個(gè)學(xué)生的電子郵件，說(shuō)“我一直忘記，零是偶數(shù)還是奇數(shù)？在數(shù)學(xué)上未經(jīng)訓(xùn)練的大腦中，有一些東西抵制將 0 與 2、4、6、8······分類因?yàn)?0 似乎與正偶數(shù)整數(shù)截然不同。我今天談?wù)摰倪\(yùn)算并不能驗(yàn)證學(xué)生認(rèn)為 0 可能很奇怪的傾向，但它們確實(shí)驗(yàn)證了學(xué)生認(rèn)為 0 是有所不同的潛在感覺(jué)。

#4. 閉包操作（運(yùn)算）的另一個(gè)詞是 “二階的冪等”，通常簡(jiǎn)稱為冪等（idempotent）。

#5. 有關(guān)直覺(jué)主義三重否定的更多信息，請(qǐng)參閱在Stackexchange網(wǎng)站的討論。 https://math./questions/2453533/triple-negation-in-intuitionistic-logic