首個世界邏輯日︰連結起20世紀兩大邏輯學家的日期

首個世界邏輯日︰連結起20世紀兩大邏輯學家的日期
我們想讓你知道的是

2019年1月14日是首個「世界邏輯日」,1月14日同時是邏輯學家哥德爾離世及塔斯基出生的日子。

邏輯學期刊《Logica Universalis》在今年1月14日舉辦首個「世界邏輯日」(World Logic Day),期刊主編北炯(Jean-Yves Béziau)希望能藉此推廣邏輯研究。據期刊網站資料,不同國家的多家大學均會在當日安排活動響應,例如以邏輯學為主題的演講或研討會等。

把「世界邏輯日」訂在1月14日,其中一個原因是這日子巧合地跟20世紀兩大邏輯學家有關︰哥德爾(Kurt Gödel)在1978年這一天逝世,而塔斯基(Alfred Tarski)於1901年該日出生。

這兩位同於1900年代出生(哥德爾生於1906年)的邏輯學巨人對上世紀數理邏輯發展舉足輕重。哥德爾證明的「不完備性定理」(incompleteness theorems)揭示了數學系統的限制,其證明亦屬「可計算性理論」(computability theory,又稱遞歸論 recursion theory)早期發展的重要結果。塔斯基則提出了形式語言中「真」和「邏輯後果」的定義,奠下了模型論(model theory)的基礎,並跟其學生將此領域發展成現代數理邏輯的一大支柱。

哥德爾不完備性定理常被詮釋成「存在真但不可證明的命題」,塔斯基也有一個跟不完備性定理有關的結果,稱為「真的不可定義」(undefinability of truth)。如果不熟悉邏輯學中對「真」的嚴格定義,很容易會望文生義,借題發揮。本文希望藉此機會,盡量不使用符號去解釋,響應「世界邏輯日」推廣邏輯學研究的宗旨。

AlfredTarski1968
Photo Credit: George Bergman, GNU Free Documentation License,
塔斯基

如何定義及理解「真理」是哲學長久以來的一大問題,哲學家發展出不同的「真理理論」嘗試解釋何謂「真理」。「真」這個看似普通的概念之所以難纏,一大原因是面臨各種悖論挑戰,當中最重要的相信是「說謊者悖論」——「這句話是假的」到底是不是真的?如果是的話,那句話就是假的;如果不是,又會變成真的了。

塔斯基從人工設計、有嚴格定義的形式語言着手,嘗試定義形式語言中「真」的意思。他區分了「對象語言」和討論對象語言的「後設語言」,當我們在討論某個句子是不是「真」的時候,使用的是比對象語言包含更多的後設語言。

20世紀初期,數理邏輯發展受到數學家希爾伯特(David Hilbert)的形式主義影響,出現各種邏輯及數學的形式系統。粗略來說,形式系統是嘗試把數學、邏輯系統化約為符號的產物,在形式系統之中,有嚴格定義的語法、明確的公理和推理規則,這些系統中的「定理」就是從公理出發,一步一步按照規則變換符號而得出的語句。理論上,任何人只要懂得按規則辦事,即使完全不明白符號代表甚麼意思,都能夠證明定理。

這一類只處理符號問題的研究,在邏輯學中屬於「語法」(syntax)範疇。例如形式主義的一項計劃,就是希望透過證明數學的形式系統不會透過規則變換得出「0=1」這類引起矛盾的句子,來證明數學系統並無矛盾,這就屬於語法的進路。

但單看符號不會有真假的問題,只有詮釋了符號才能討論真假,這屬於邏輯學中的「語意」(semantics)範疇。塔斯基的研究進路,令邏輯學家逐漸擺脫希爾伯特的影響,開始使用集合論等數學工具來研究邏輯問題。(當然這並非塔斯基一人的影響,在他以前亦有其他邏輯學家發展及使用相關概念。)

AP_510314018
Photo Credit: AP Photo
1951年,哥德爾(右二)與物理學家許文格(右一)同獲首屆愛因斯坦獎,愛因斯坦(左一)於其72歲生日(3月14日)頒發獎項。

而哥德爾證明的不完備定理,同樣對形式主義影響深遠。透過把算術的形式系統編碼,哥德爾找到一個讓算術系統描述自身的方法︰透過描述數字之間的關係,再「翻譯」成對應的形式系統語句。

假設這個算術形式系統一致——即不會同時證明A和¬A(「¬」在邏輯系統中代表「非」或「否定」)兩條定理——哥德爾構造了一個形式上類似說謊者悖論的「不可判定句」G,而這個系統既無法證明G,也無法證明¬G。這代表該算術系統「不完備」,而且其他更強的算術系統同樣受此限制。哥德爾的定理打擊了希爾伯特的形式主義計劃,但詳情涉及技術細節,在此略過。

塔斯基在提出形式語言中「真」的定義時,利用了哥德爾的編碼技巧,證明在一些算術系統中無法定義「算術真理」而不引致矛盾,原因同樣跟說謊者悖論有關,這項定理稱為「真的不可定義」。不過必須注意這項結果只局限於形式系統之中,而非我們平日使用的自然語言。

回到算術系統的問題,數學家可以利用集合論定義自然數及其加法和乘法,這個結構滿足我們對自然數的直覺及理解,稱為「標準模型」。在構想算術系統的公理和推理規則時,數學家也是按照以往研究自然數的特性來設計,而且我們能夠透過詮釋系統的符號,令形式系統跟標準模型對應。

透過算術系統證明出來的定理,經詮釋後都符合上述「標準模型」,通常會稱為「真」的算術語句——此處「真」的意思其實是「在標準模型中為真」。然而透過不完備定理,我們知道並非所有「真」的算術語句都能夠透過算術系統證明,甚至不存在一個能完整描述標準模型的算術系統。這就是坊間常稱不完備定理表示「存在真但無法證明的算術命題」的意思。

哥德爾另一項重要的數學結果,是證明了集合論中的「連續統假設」(Continuum Hypothesis)及「選擇公理」(Axiom of Choice)跟集合論的其他公理一致——即不會產生矛盾。後來數學家寇恩(Paul Cohen)則證明了集合論公理無法推論出這兩個命題,換言之,兩個命題均是集合論的「不可判定句」。這兩項結果的證明方法令集合論迅速發展。

哥德爾跟塔斯基一樣,在二次大戰期間由歐洲移居美國,逃過納粹魔掌。哥德爾本來住在維也納,於納粹德國佔領奧地利一年後離開,1940年抵達美國,此後任職於著名的普林斯頓高等研究所,並認識了物理學家愛因斯坦(Albert Einstein)。

塔斯基則受到哲學家及邏輯學家奎因(Willard Van Orman Quine)邀請出席一個學術會議,剛好搭上納粹德國及蘇聯入侵波蘭前最後一班開往美國的船,此後長居美國。在幾家大學短暫逗留後,塔斯基1942年起一直於加州大學柏克萊分校任教,培育出多名重要的邏輯學家。

正如塔斯基傳記作者布特曼(Anita Burdman Feferman)及其丈夫兼塔斯基學生費佛文(Solomon Feferman)在書中所言,塔斯基跟哥德爾兩人改變了20世紀邏輯學的面貌。如讀者想進一步認識兩位邏輯學家的生平,不妨閱讀兩人的傳記︰《Logical Dilemmas: The Life and Work of Kurt Gödel》及《Alfred Tarski: Life and Logic》。

相關文章︰

寫給懂一點數理邏輯的讀者的後記

由於盡量不使用符號和術語,上文省略了不少重要細節,嚴格來說甚至有錯,以下稍作補充。

一,希爾伯特的形式主義不僅是把數學化約成形式系統,其「元數學」(metamathematics)計劃是使用「有限方法」證明數學無矛盾,這項計劃發展成為數理邏輯中的證明論。

二,本文的「算術系統」其實是指「皮亞諾算術」(Peano Arithmetic),不過一些稍弱一點的系統同樣可構造不可判斷命題。

三,哥德爾不完備定理對形式系統有若干限制,其中包括定理須為遞歸可枚舉集合(recursively enumerable set)。把所有在標準模型中為真的算術語句列為公理的系統稱為「真算術」(True Arithmetic),這個系統雖然完備,但未有違反哥德爾不完備定理。

四,關於哥德爾的集合論結果,他當時使用的集合論應為NBG(Von Neumann–Bernays–Gödel)集合論,而非現時主流的ZF(Zermelo–Fraenkel)。此外,所謂「不會產生矛盾」的前提,是原本的公理沒有矛盾。

核稿編輯:歐嘉俊

或許你會想看
更多『評論』文章 更多『科學』文章 更多『Kayue』文章
Loader