Logic-based analogical proportions

基于邏輯的類比比例

https://arxiv.org/abs/2406.14402

摘要

作者最近在泛代數 （universal algebra）的一般框架下，提出了一種關于類比比例的抽象代數框架。本文的目的在于將該框架從泛代數提升到表達能力更強的全一階邏輯 （full first-order logic）的設定中。我們展示了所獲得的基于邏輯的框架保留了所有期望的性質，并在該擴展設定下證明了一些新結果。

1. 引言

作者近期在泛代數 的一般設定下引入了一個基于解釋的、形式為“a 對 b 就像 c 對 d”——寫作 a : b :: c : d ——的類比比例 抽象代數框架（Anti?, 2022）。該框架已在 Anti? (2023b) 中應用于邏輯程序合成，并在布爾代數（Anti?, 2024）和單目代數（monounary algebras）（Anti?, 2023a）的背景下進行了研究。

本文的目的是將這一模型從泛代數提升到全一階邏輯 的設定中，其動機在于某些推理任務必然涉及量詞和關系。

切入點是 Anti? (2022, §6) 中對類比比例的邏輯解釋 。將那種有限的邏輯解釋——僅限于表示規則式解釋的所謂重寫公式（rewrite formulas）——轉化為一個完整的、充分發展的類比比例邏輯描述，這一過程被發現并不簡單。原因在于，一種天真的擴展很容易導致過度泛化，使得太多元素之間都處于類比比例關系中：

例如，考慮結構 (N, S, 0) ，其中 S 是后繼函數；在這個結構中，我們可以將每一個自然數 a 與數符（numeral）ā := S?0 相對應。給定一些自然數 a, b, c, d ∈ N ，公式：

因此，主要的挑戰在于找到一個合適的一階邏輯片段，用以表達兩個給定元素之間的關系。本文通過引入“連通公式 ”（connected formulas）的概念（見 §3）來實現這一點。

從那時起，本文在精神上與 Anti? (2022) 相似，但在技術層面上有所不同，因為現在的解釋可以包含關系符號以及原子的合取。

在 §4 中，我們證明：本文所擴展的框架保留了 Anti? (2022, 定理 28) 中證明的所有期望性質（這些性質基于 Lepage (2003) 的公理化方法），因此在這方面它與原始框架是一致的。此后，一些結果被推廣到新的設定中，其中最重要的是第 §5 節中的同構定理 （Isomorphism Theorems）。

在 §6 中，我們展示了一個有趣的新結果，將等式依賴性 （equational dependencies）與類比比例聯系起來。需要強調的是，由于之前的框架無法通過重寫解釋顯式地表示方程，這類結果在早期版本的框架中是無法得出的。

在 §7 中，我們重新證明了 Anti? (2023a) 中的差異比例定理 （Difference Proportion Theorem），該定理指出：在由自然數和一元后繼函數構成的結構 (N, S) 中，我們有：

最初該定理是相對于形式為 s → t 的重寫解釋進行證明的，其所在的等式片段僅包含形式為 s = t 的解釋。

在 §8 中，我們研究了圖結構，所使用的路徑片段（path fragment）僅包含某種特定形式的路徑解釋，這些解釋編碼了路徑長度的信息。

2. 預備知識

我們主要按照 Hinman (2005, §2) 的方式來回顧一階邏輯的語法與語義 。

2.1 語法

一個（一階）語言 L 包含以下組成部分：

• 一組 L-關系符號 （L-relational symbols），記作 Rs? ；

• 一組 L-函數符號 （L-function symbols），記作 Fs? ；

• 一組 L-常量符號 （L-constant symbols），記作 Cs? ；

• 一個函數 r : Fs? ∪ Rs? → N ，用于為每個函數或關系符號指派 元數 （arity）。

其中集合 Rs?、Fs? 和 Cs? 是兩兩不相交的。
Rs? ∪ Fs? ∪ Cs? 中的元素被稱為語言 L 的非邏輯符號 （non-logical symbols）。

此外，每種語言都包含如下邏輯符號 （logical symbols）：

• 一個可數無限的 變量集 X ；

• 等號符號 = ；

• 聯結詞： ?（非）、∨（析取）、∧（合取） ；

• 量詞： ?（存在量詞）、?（全稱量詞） 。

一個 L-原子項 （L-atomic term）是語言 L 中的一個常量符號或一個變量。

一個 L-項 （L-term）歸納定義如下：

• 每個 L-原子項 都是一個 L-項 ；

• 對于任意函數符號 f 和任意 L-項 t?, ..., t??? ，表達式 f t? ... t??? 也是一個 L-項 。

我們用 X? 表示出現在項 t 中的所有變量的集合。
一個項的秩 （rank）由它所包含的變量個數給出。

一個 L-原子公式 （L-atomic formula）具有以下形式之一：

• s = t

  ，其中 s、t 是 L-項 ；

• p t? ... t???

  ，其中 p 是一個 L-關系符號 ，而 t?, ..., t??? 是 L-項 。

一個 L-公式 （L-formula）歸納定義如下：

• 每個 L-原子公式 是一個 L-公式 ；

• 如果 α 和 ψ 是 L-公式 ，那么 ?α、α ∨ ψ、α ∧ ψ 也是 L-公式 ；

• 如果 α 是一個 L-公式 ，且 x ∈ X 是一個變量，那么 (?x)α 和 (?x)α 也是 L-公式 。

一個 L-公式 的秩 （rank）是指它的自由變量 （free variables）的數量。
如果一個變量不在任何量詞的作用域內，則稱為自由變量 。
我們用 X? 表示出現在公式 α 中的所有變量的集合（不一定是自由變量）。

我們假設所有被量化的變量都是不同的，這意味著我們不允許出現如下形式的公式：
(?x)Px ∧ (?x)Rx 。

2.2 語義

一個 L-結構 （L-structure）由以下部分組成：

• 一個非空集合 A ，稱為 A 的論域 （universe）；

• 對于每個關系符號 p ∈ Rs? ，指定一個關系 p? ? A???? ，稱為 A 中的 p 的解釋 ；

• 對于每個函數符號 f ∈ Fs? ，指定一個函數 f? : A??? → A ，稱為 A 中的 f 的解釋 ；

• 對于每個常量符號 c ∈ Cs? ，指定一個元素 c? ∈ A ，稱為 A 中的特殊元素 。

每個項 s 按照通常方式誘導出一個函數 s? : A???? → A 。

我們歸納地定義邏輯蘊含關系 （logical entailment relation）如下：
對于任意 L-結構 A、L-項 s, t、L-公式 α, ψ ，以及 a ∈ A??α??1 ，我們有：

引理 1 . 同構保持 L-項 和 L-公式 的解釋。

3. 類比比例

在本節中，我們將 Anti? (2022) 中提出的類比比例的代數框架從泛代數 提升到一階邏輯 中。
在下文中，設 L 是一個一階語言，A 和 B 是 L-結構 。

切入點是 Anti? (2022, §6) 中關于類比比例的模型論類型 （model-theoretic types）意義上的邏輯解釋。

主要難點在于找到一個合適的一階公式片段，用以表達兩個給定元素之間的關系，使得所有相關性質都可以被表達出來，同時排除不合適的元素關系，從而避免出現過度泛化的問題——即太多元素之間被認為處于類比比例關系中（參見 §1 中的討論）。

本文通過引入“連通公式 ”（connected formula）的概念解決了這一問題：

定義 2 . 一個 2-L-公式 （2-L-formula）是指恰好包含兩個自由變量 x 和 y 的公式。

合取 L-公式 （conjunctive L-formula）的集合由不包含否定（?）或析取（∨）的 L-公式組成。

我們如下定義一個合取的 2-L-公式的無向依賴圖 （undirected dependency graph）：

• 其頂點集是由該公式中出現的所有變量組成的集合 X? ；

• 對于兩個變量 w, z ∈ X? ，如果它們同時出現在該公式的某個原子公式中，則在它們之間存在一條（無向）邊 {w, z} 。

我們稱一個合取 L-公式 α 為一個連通 L-公式 （connected L-formula），或簡稱 c-公式 （c-formula），當且僅當它的依賴圖是一個連通圖 （connected graph），即：圖中任意兩個頂點之間都存在路徑，并且該圖必須包含變量 x 和 y 。

我們將 L 上所有 c-公式 的集合記作 c-Fm? 。

一個 c-項 （c-term）（或 c-原子公式 ，c-atom）是指一個既包含變量 x 又包含變量 y 的 L-項（或 L-原子公式）。

這表明該公式不是一個連通公式 。粗略地說，子公式 w = z 沒有包含任何關于 x 和 y 之間關系的信息，因此被認為是冗余的。而簡化后的公式 x = y 則顯然是一個連通公式。

以下定義——它是對在泛代數框架下給出的一個更受限定義（Anti?, 2022, 定義 8）的一種推廣——其動機來自于如下觀察：形式為 a : b :: c : d 的類比比例最好通過箭頭比例 （arrow proportions）a → b : · c → d 來定義，后者形式化了有向關系，并在解釋集合上施加了一個極大性條件 （maximality condition）。更確切地說，“a 與 b 的關系正如 c 與 d 的關系”意味著所有形如 α(a, b) 和 α(c, d) 的連通公式 α 所組成的解釋集合相對于 d 是極大的，直觀上這意味著關系 a → b 與關系 c → d 是最大程度相似 的。

4. 性質

沿襲古希臘的傳統，Lepage（2003）在語言學背景下提出了一組性質，作為類比比例形式化模型的指導原則。此后，許多學者對他的列表進行了擴展，目前包含以下性質：

請注意，中心 p-傳遞性 （central p-transitivity）可由 p-傳遞性 （p-transitivity）推出。

下面的定理表明，本文所提出的一階邏輯框架具有與原始泛代數框架相同的性質（參見 Anti?, 2022, 定理 28）：

定理 6 . 如定義 4 所定義的類比比例關系滿足以下性質：

• p-對稱性

  （p-symmetry），

• 內 p-對稱性

  （inner p-symmetry），

• 內 p-自反性

  （inner p-reflexivity），

• p-自反性

  （p-reflexivity），

• p-確定性

  （p-determinism）；

而一般來說，它不滿足 以下性質：

• 中心置換性

  （central permutation），

• 強內 p-自反性

  （strong inner p-reflexivity），

• 強 p-自反性

  （strong p-reflexivity），

• p-交換性

  （p-commutativity），

• p-傳遞性

  （p-transitivity），

• 內 p-傳遞性

  （inner p-transitivity），

• 中心 p-傳遞性

  （central p-transitivity）。

證明 . 我們有如下證明（其中一些與 Anti? (2022) 中定理 28 的原始證明非常相似，為完整起見在此重復給出）：

• 對稱性和內對稱性 成立是顯然的，因為該框架設計之初就旨在滿足這些性質。

• 內自反性 成立是因為 x = y 是形如 a → a : · c → c 和 c → c : · a → a 的比例的一個特征解釋。

• 接下來我們證明自反性 。我們首先證明：

5. 同構定理

我們有理由期望同構映射 （即結構保持的雙射映射）與類比比例是相容的。在本節中，我們將 Anti? (2022) 中的第一同構定理 和第二同構定理 提升到本文所討論的框架中。

6. 等式比例定理

在本節中，我們證明在某些條件下，等式依賴性 （equational dependencies）會導致一個類比比例 （analogical proportion）的成立。也就是說，在某些情況下，如果我們有 t(a, b) = t(c, d) （其中 t 是某個項函數），那么我們期望 a : b :: c : d 成立——請注意，為了使這個等式有意義，t(a, b) 和 t(c, d) 必須屬于同一個域。

下一個定理建立了一個使得該蘊含關系成立的情境：

7. 等式片段

在許多情況下，通過對解釋 （justifications）進行句法上的限制，來研究完整框架的一個受限片段 （restricted fragment），這是有意義的。在本節中，我們考察僅包含簡單形式 s = t （其中 s 和 t 是項）的解釋所組成的等式片段（equational fragment），并從這一視角重新證明 Anti? (2023a) 中的差異比例定理 （Difference Proportion Theorem）（定理 17）。這為底層框架的穩健性 （robustness）提供了進一步的概念性佐證。

8. 圖

一個（無向）圖是一個關系結構 G = (V?, E?) ，其中：

如果在圖 G 中頂點 a 和 b 之間有一條邊，我們寫作 a —? b 。

如果一個圖 F 滿足 V? ? V? 且 E? ? E? ，則稱 F 是 G 的子圖。

圖中的一條路徑 （path）是指連接一系列頂點的有限或無限邊序列。

我們寫作 a —?? b 表示在圖 G 中 a 和 b 之間存在一條長度為 n 的無向路徑；
我們寫作 *a —? b 表示存在某個 n ≥ 0 ，使得 a —?? b 成立。

如果一個圖中任意兩個頂點之間都存在路徑，則稱該圖是連通的 （connected）。

給定一個一階公式 α ，如果 α 在圖 G 中成立，我們寫作 G ? α 。

需要指出的是，每一個 路徑公式 π(x, y) 在 §3 的意義上都是一個 連通公式 （connected formula），因為它僅包含合取（conjunction），并且變量 x 和 y 是相互連接的，這意味著在 π 的依賴圖中，頂點為 x, z?, ..., z?, y ，且對于任意兩個變量 v, v′ ，只要在 π 中存在關系 vEv′ ，它們之間就有一條邊，從而在 x 和 y 之間存在一條路徑。

9. 結論

本文的目的是將一個關于類比比例的抽象代數框架從泛代數 提升到表達能力更強的全一階邏輯 （full first-order logic）的設定中。這一目標通過將抽象重寫擴展為包含任意量詞和關系的連通解釋 （connected justifications）而得以實現，同時禁止使用析取和否定。

我們已經證明了擴展后的框架保留了所有期望的性質，并展示了全新的等式比例定理 （Equational Proportion Theorem 13），該定理在純代數設定下是無法證明的。此外，我們還分析了圖結構中類比比例的表現。

未來研究的主要方向是進一步將本文的概念和結果從一階邏輯 提升到二階邏輯 ，并最終推廣至包含量化函數與關系的高階邏輯 （如 Leivant, 1994 所述）。這是值得追求的方向，因為某些類比比例無法在一階邏輯中表達。例如，在給定兩個由以下方式定義的關系 P 和 R 的結構中：

a → b : · c → d 的所有解釋集合是空的，而在二階邏輯中，該比例包含解釋 (?S) S(x, y) 。也就是說，二階邏輯和更高階的邏輯使我們能夠發現那些在一階邏輯中無法被識別的相似性。

原文鏈接：https://arxiv.org/abs/2406.14402