第O章 §Φ元數學引論

§Φ1字母與詞 歸納定義與遞迴定義

(

Φ

1.1

)

(

1

)

我們任意固定兩個圖案：§，，並稱形如

§…§

的圖案為

字母

．

(

2)

形如

a

1…

a

n

的圖案

í

a

i

是字母

，稱為

詞

。自然，字母也是詞．

(

3)

設

w

為詞．則

w

可表為

w

≡

a

1…

a

n

í

a

i

是字母

——此表示式稱為

w

的

字母分解

．

[

Φ

1.2]

（

字母分解的唯一存在性

）詞必有唯一的字母分解．

【證】施歸納於詞中出現的次數．l

(

Φ

1.3)

(

1)

設

a

為字母，

w

為詞且它有字母分解

w

≡

a

1…

a

n

í

a

i

是字母

．則：

n

稱為

w

的

長度

，記為 （

w

） ．

由［F1。2］知，存在唯一的長度為零的詞，稱為

空詞

，記為 q ．

使

a

i

＝

a

的

i

的個數稱為

a

在

w

中的

出現次數

，記為 （

a

，

w

） ．

如果（

a

，

w

）≠0，則說

a

在

w

中

[

出現

]

。

F

由［F1。2］知，本定義是合法的，且顯然（

w

）＝‘

w

中的出現次數’．

(

2)

設

w

，

w

1為詞．如果存在詞

x

，

y

使

w

＝

xw

1

y

，則說

w

1

在

w

中

[

出現

]

。

F

本定義相容於（1）．

[

Φ

1.4]

設

a

，

b

為字母，

x

，

y

為詞．則：

[

1]

（

a

）＝1．

[

2]

（

x

y

）＝（

x

）+（

y

）．

[

3]

（

a

，

a

）＝1；若

a

≠

b

則（

a

，

b

）＝0．

[

4]

（

a

，

x

y

）＝（

a

，

x

）+（

a

，

y

）．

[

Φ

1.5]

設

a

，

b

為字母，

x

，

y

，

z

，

x

1，

y

1為詞．則：

[

1]

（

結合律

）（

x

y

）

z

＝

x

（

y

z

）．

[

2]

（

恆等律

）q

x

＝

x

q＝

x

．

[

3]

xy

＝q

x

＝

y

＝q

．

[

4]

（

消去律

）若

xy

＝

xz

則

y

＝

z

；

若

yx

＝

zx

則

y

＝

z

．

[

5]

（

強消去律

）如果

xy

＝

x

1

y

1，且：（

x

）＝（

x

1）或（

y

）＝（

y

1），則：

x

＝

x

1且

y

＝

y

1．

[

6]

如果

ax

＝

by

，則

a

＝

b

且

x

＝

y

；

如果

xa

＝

yb

，則

x

＝

y

且

a

＝

b

．

[

7

]

如果

xy

＝

x

1

y

1，（

x

）＜（

x

1）

【

（

y

）＜（

y

1）

】

，則存在詞

w

≠q使

x

1＝

xw

【

y

1＝

w

y

】

．

【證】由詞之字母分解的唯一存在性定理［F1。2］易得．l

(

Φ

1.6)

我們亦可如此地定義“字母”：

設

x

為．則

x

是字母．（或直說“是字母”）

①

設

x

為字母．則§

x

是字母．

只有如上所給者才是字母．

我們亦可如此地定義“詞”：

設

x

為字母．則

x

是詞．（或直說“字母是詞”）

②

設

x

為詞，

a

為字母．則

x a

是詞．

只有如上所給者才是詞．

“詞”還可如此地定義：

設

x

為字母．則

x

是詞．（或直說“字母是詞”）

③

設

x

，

y

為詞．則

x

y

是詞．

只有如上所給者才是詞．

上述三定義與普通定義有一個根本性區別：前者並不直接說滿足怎樣條件的物件稱為

，而只是指出了的可靠而完備的生成法．這樣的定義稱為

歸納定義

．

在歸納定義中，總有保證其完備性的最後一個條款，稱為

它的

完備性條款

，它具

“只有如上所給者才是”

形．我們約定：

今後恆將其省略

．

在歸納定義中，除了保證其完備性的最後一個條款外，其餘條款稱為

它的

形成規則

．

重要的是：

對於歸納定義，我們亦可依照其形成規則而把它還原成普通定義

。

F

例如，我們可依照

②

的形成規則而給出“詞”的普通定義如下：

“

詞

”可被定義為“詞生成列之項”，而這裡的“詞生成列”是指這樣的有限列D：

D的每一項d，它或是字母（依照

②

），或具d ≡

x

a

形

í

x

是D中位於d之前的項，

a

是字母

（依照

②

）．

(

Φ

1.7)

(

1)

一個歸納定義也可視為由其形成規則構成的系統，稱為

歸納系統

。

例如，

①

，

②

，

③

又是歸納系統．

(

2)

我們舉一例說明什麼是

歸納系統

或

歸納定義的

唯一生成性命題

：

歸納系統

②

的唯一生成性命題是：

設

w

為詞，則下列二條件至多隻有一個成立：

（a°）

w

具

w

≡

x

形

í

x

是字母

．（或直說“

w

是字母”）

（b°）

w

具

w

≡

x

a

形

í

x

是詞，

a

是字母

．

④

並且有

（a）′ 若（a°）成立，則

w

唯一地具（a°）中之形．

（b）′若（b°）成立，則

w

唯一地具（b°）中之形．

根據

②

中的完備性條款，

④

中的“至多隻有一個”可加強為“恰有一個”（即“有且只有一個”）．

容易看出，

②

的唯一生成性命題

④

是成立的．但是，歸納系統的唯一生成性命題不必都成立．

例如：

③

，以及下節中“

可證公式

”的定義（F2。18），其唯一生成性命題都不成立．

一個歸納系統或歸納定義，如果其唯一生成性命題為真，則說它是

正則的

．

(

Φ

1.8)

我們亦可對詞

w

而重新定義‘（

w

）’如下：

若

w

是字母，則（

w

）＝1．

設

x

為詞，

a

為字母．則（

x a

）＝（

x

）+1．

這種型別的定義與普通定義是不同的，稱為

遞迴定義

．

遞迴定義也不同於歸納定義：它是用來定義函式的．

一個遞迴定義總是參照著一個歸納定義進行的，該歸納定義的唯一生成性命題也稱為

該遞迴定義

的

唯一生成性命題

。例如，

⑤

的唯一生成性命題就是

④

．

在給出一個遞迴定義時，我們必須充分考慮其“

合法性

”．例如，就

⑤

而言，我們必須

證明：滿足

⑤

之的，以詞的全體為定義域的函式確實是唯一存在的；易見，這個

唯一存在性可由

⑤

的唯一生成性命題

④

之為真而得出．

為了確保遞迴定義的合法性，我們規定：

遞迴定義的唯一生成命題必須為真，從而使之確實是合法地定義了一個函式

．