第一章：集合論的形式語言（3）

1.5. 易字變形

直觀上，公式的「易字變形」是把公式中的「約束變元」替換為其他變元得到的公式。為了給出「易字變形」的嚴格定義，我們不需要事先定義「約束變元」。事實上，我們自始至終都不會用到「出現」、「約束出現」、「約束變元」的嚴格定義；有「自由出現」的嚴格定義就足夠了。我們秉承「奧卡姆剃刀」原則，在保證「嚴格性」的前提下，儘力把所需的語法概念壓縮到最少（上一節中我們對「代入」的處理方式使得我們不需要定義「可自由代入」、「規範易字變形」，也體現了這一原則）。

然而，為了定義「易字變形」，按照公式的長度遞歸定義是不行的（原因稍後說明）。我們需要首先定義「φ 中出現的蘊含符號和全稱量詞符號的數目」（記作 ρ(φ) ）。我們按照公式 φ 的長度遞歸定義如下：

（i） ；

（ii） ；

（iii） ；

（iv） 。

1.5.1. 引理：

設 是兩兩不同的變元。

。

證明：對 φ 的長度歸納。

使用這個引理，我們按照 ρ(φ) 遞歸定義「ψ 是 φ 的易字變形」如下：

（i） 是 的易字變形當且僅當 ；

（ii） 是 的易字變形當且僅當 ；

（iii） 是 的易字變形當且僅當 ， 是 的易字變形，並且 是 的易字變形；

（iv） 是 的易字變形當且僅當 ，並且 是 的易字變形，其中 是不在 和 中自由出現的第一個變元。

關於這個定義，我們說明以下兩點：

第一，之所以不能按照公式 φ 的長度遞歸定義，是因為在（iv）中， 的長度未必比 短（注意，我們的變元不是一個「單獨的」符號，而是一個符號串；如果 很長，那麼 的長度可能遠大於 ）。而如果按照 ρ(φ) 遞歸定義，就不存在這個問題：根據引理1.5.1， 。

第二，Bell and Machover 著 A Course in Mathematical Logic 中「易字變形」的遞歸定義中的量詞步驟是錯誤的（見 62 頁定義3.7）；那裡定義的「易字變形」是沒有「傳遞性」的（雖然作者聲稱它具有傳遞性）。反例的構造留給讀者。因為這裡的「代入」定義和 Bell and Machover 的定義不同，我們這裡的「易字變形」定義不能作為對他們的錯誤定義的直接修正；對於他們錯誤定義的一個修正，見徐明老師的博文：

《符號邏輯講義》勘誤

中第358頁的修正。（徐老師的書在習題中使用了 Bell and Machover 的定義（見 358 頁習題9.20）。）

1.5.2. 引理：

如果 是 的易字變形，那麼 。

證明：對 ρ(φ) 歸納，用到引理1.5.1.

1.5.3. 引理：

設 是 的易字變形。

對所有的變元 ， 在 中自由出現當且僅當 在 中自由出現。

證明：對 ρ(φ) 歸納，用到引理1.4.2.

1.5.4. 引理：

（i） 是 的易字變形；

（ii） 是 的易字變形當且僅當 是 的易字變形。

證明：對 ρ(φ) 歸納。

1.5.5. 引理：

（i）如果 是 的易字變形，並且 是 的易字變形，那麼 是 的易字變形。

（ii）設 是兩兩不同的變元。如果 是 的易字變形，那麼 是 的易字變形。

（iii）設 是兩兩不同的變元， 是兩兩不同的變元，並且 也是兩兩不同的變元。如果對所有在 中自由出現的變元 ，

，

那麼 是 的易字變形。

引理1.5.5 的證明是 straightforward 的，但是極為繁瑣：需要對 ρ(φ) 歸納同時證明（i）（ii）和（iii）。我們將在下一篇文章中給出這個引理的完整證明，作為「歸納同時證明」的第一個例子，它也將是該系列文章中的第一個完整的證明。