跳至內容

字元集 (數理邏輯)

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書

字元集在不同領域中有不同意義。在邏輯學(特別是數理邏輯中)代表的是列舉出形式語言非邏輯符號英語non-logical symbol的一組集合;在泛代數中則是列舉出代數結構具代表性的運算。另外,在模型論中兩種用法皆有使用。

對邏輯學更哲學性的討論中,字元集的概念較少被提及。

定義

一個(單域)字元集在形式上定義為四元組,當中是不包含其他基本邏輯符號的不相交集合,分別稱作

  • 函數符號(例如:
  • 關係符號謂詞(例如:
  • 常數符號英語Logical constant(例如:

以及一個函數用來為各個關係符號和邏輯符號指定一個自然數,稱為該符號的元數。元數為的符號稱為-元的。有些作者會將常數符號定為0-元的函數符號,其它則將常數符號分開定義。

不含函數符號的字元集稱為關係字元集,而不含關係符號的字元集稱作代數字元集[1] 如果皆為有限集合,則稱為有限字元集。更廣泛的說,字元集定義為

字元集的語言是字元集和邏輯系統中的所有符號形成的合式公式的集合

其他記號

由於其形式定義對日常使用來說過於繁瑣,一些字元集的定義經常以一種非正式的方式縮寫,例如:

阿貝爾群的標準字元集是 ,當中是一個一元算符。」

有時一個代數字元集會被視為元數的列表,例如:

「阿貝爾群的相似類型(原文:similarity type)是。」

這在形式上將函數符號定義為類似於(2-元)、(1-元)和(0-元)的樣子,但也有機會看到以這種方式命名的關係符號。

數理邏輯中通常不會允許0-元的符號,[來源請求]因此常數符號就必須得被分開處理。形成一個集合,並與沒有交集,且元數函數在這集合上沒有定義。然而這只會讓事情變得複雜,尤其在用歸納法證明一個公式的結構時會需要考慮到額外的情況。雖然在此定義下0-元關係符號也是不被允許的,但我們依舊能用一個1-元關係符號,額外加上一個說明此關係的值對所有元素都相同的表達句來模擬。這種模擬方式只會在空結構中失效(但空結構照慣例通常會被排除在外)。如果允許0-元符號,則命題邏輯的公式也都會是一階邏輯的公式。

無限字元集的一個例子是使用來形式化無限純量體向量空間的表達式和方程,當中代表乘以純量的1-元算符。如此便能維持單域的字元集和邏輯,論域只包含向量。[2]

字元集在邏輯學和代數中的應用

一階邏輯的語境下,字元集中的符號又被稱作非邏輯符號英語non-logical symbol,因為字元集配上邏輯符號便構成了基礎的字母表,可以用於歸納的定義出兩種形式語言:字元集上的集合與(合式)公式的集合。

在討論結構時,詮釋將函數符號和關係符號聯繫到與它們名字相襯的數學物件:一個-元函數符號在以為論域的結構中的詮釋是一個函數,而一個-元關係符號的詮釋是一個關係 。當中代表論域和自己的笛卡爾積,如此便成為了一個-元函數,而則是一個-元關係。

多域字元集

多域邏輯和多域結構英語structure (mathematical logic)#Many-sorted structures的字元集必須包含論域的訊息。最直接的做法便是透過符號類型[3]

符號類型

為一個不包含符號的(論域的)集合。

上的符號類型是字母表上的特定詞彙:關係符號類型,和函數符號類型,其中為非負整數且 (如果,則表達式表示空詞彙)

字元集

(多域)字元集是一個三元組包含

  • 論域的集合
  • 符號的集合
  • 一個將中的每個符號送到上的符號類型的映射

參見

附錄

  1. ^ Mokadem, Riad; Litwin, Witold; Rigaux, Philippe; Schwarz, Thomas. Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures (PDF). 33rd International Conference on Very Large Data Bases (VLDB). September 2007 [27 February 2019]. (原始內容存檔 (PDF)於2017-08-09). 
  2. ^ George Grätzer. IV. Universal Algebra. James C. Abbot (編). Trends in Lattice Theory. Princeton/NJ: Van Nostrand. 1967: 173–210.  Here: p.173.
  3. ^ Many-Sorted Logic, the first chapter in Lecture notes on Decision Procedures, written by Calogero G. Zarba頁面存檔備份,存於互聯網檔案館).

參考文獻

外部連結