查看“︁字元集 (數理邏輯)”︁的源代码

{{暫定名稱}}
{{NoteTA
|G1=Math
|1=zh-cn:数学对象;zh-tw:數學物件;
}}
'''字元集'''在不同領域中有不同意義。在[[邏輯學]]（特別是[[數理邏輯]]中）代表的是列舉出[[形式語言]]中{{link-en|非邏輯符號|non-logical symbol}}的一組集合；在[[泛代數]]中則是列舉出[[代數結構]]具代表性的運算。另外，在[[模型論]]中兩種用法皆有使用。

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

== 定義 ==

一個（單域）'''字元集'''在形式上定義為四元組<math> \sigma = \left(S_{\operatorname{func}}, S_{\operatorname{rel}}, S_{\operatorname{const}}, \operatorname{ar}\right)</math>，當中<math> S_{\operatorname{func}}</math>與<math> S_{\operatorname{rel}}</math>是不包含其他基本邏輯符號的[[集合 (数学)|不相交集合]]，分別稱作

* [[泛函谓词|函數符號]]（例如: <math> +, \times, 0, 1</math>）
* {{visible anchor|關係符號}}或[[谓词逻辑|謂詞]]（例如: <math> \,\leq, \, \in</math>）
* {{link-en|常數符號|Logical constant}}（例如: <math> 0, 1</math>）

以及一個函數<math> \operatorname{ar} : S_{\operatorname{func}} \cup S_{\operatorname{rel}} \to \N</math>用來為各個關係符號和邏輯符號指定一個自然數，稱為該符號的'''[[元数|元數]]'''。元數為<math> n</math>的符號稱為<math> n</math>-元的。有些作者會將常數符號定為0-元的函數符號，其它則將常數符號分開定義。

不含函數符號的字元集稱為'''{{visible anchor|關係字元集}}'''，而不含關係符號的字元集稱作'''{{visible anchor|代數字元集}}'''。<ref name="FastN-Gram-BasedStringSearch">{{cite web|author2=Litwin, Witold|author3=Rigaux, Philippe|author4=Schwarz, Thomas|last1=Mokadem|first1=Riad|date=September 2007|title=Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures|url=http://www.cse.scu.edu/~tschwarz/Papers/vldb07_final.pdf|accessdate=27 February 2019|website=33rd International Conference on Very Large Data Bases (VLDB)|format=PDF|archive-date=2017-08-09|archive-url=https://web.archive.org/web/20170809092717/http://www.cse.scu.edu/~tschwarz//Papers/vldb07_final.pdf|dead-url=no}}</ref>
如果<math> S_{\operatorname{func}}</math>與<math> S_{\operatorname{rel}}</math>皆為[[有限集合]]，則稱為'''{{visible anchor|有限字元集}}'''。更廣泛的說，字元集<math> \sigma = \left(S_{\operatorname{func}}, S_{\operatorname{rel}}, S_{\operatorname{const}}, \operatorname{ar}\right)</math>的'''勢'''定義為<math> |\sigma| = \left|S_{\operatorname{func}}\right| + \left|S_{\operatorname{rel}}\right| + \left|S_{\operatorname{const}}\right|</math>。

字元集的'''{{visible anchor|語言}}'''是字元集和邏輯系統中的所有符號形成的合式公式的集合

== 其他記號 ==

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

: 「[[阿貝爾群]]的標準字元集是 <math> \sigma = (+, -, 0)</math>，當中<math> -</math>是一個一元算符。」

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

: 「阿貝爾群的相似類型（原文：similarity type）是<math> \sigma = (2, 1, 0)</math>。」

這在形式上將函數符號定義為類似於<math> f_0</math>（2-元）、<math> f_1</math>（1-元）和<math> f_2</math>（0-元）的樣子，但也有機會看到以這種方式命名的關係符號。

在[[數理邏輯]]中通常不會允許0-元的符號，{{Citation needed|date=January 2017}}因此常數符號就必須得被分開處理。<math> S_{\operatorname{const}}</math>形成一個集合，並與<math> S_{\operatorname{func}}</math>沒有交集，且元數函數<math> \operatorname{ar}</math>在這集合上沒有定義。然而這只會讓事情變得複雜，尤其在用歸納法證明一個公式的結構時會需要考慮到額外的情況。雖然在此定義下0-元關係符號也是不被允許的，但我們依舊能用一個1-元關係符號，額外加上一個說明此關係的值對所有元素都相同的表達句來模擬。這種模擬方式只會在空結構中失效（但空結構照慣例通常會被排除在外）。如果允許0-元符號，則[[命题逻辑|命題邏輯]]的公式也都會是[[一階邏輯]]的公式。

無限字元集的一個例子是使用<math> S_{\operatorname{func}} = \{+\} \cup \left\{f_a : a \in F\right\}</math>與<math> S_{\operatorname{rel}} = \{=\}</math>來形式化無限純量體<math> F</math>上[[向量空間]]的表達式和方程，當中<math> f_a</math>代表乘以純量<math> a</math>的1-元算符。如此便能維持單域的字元集和邏輯，論域只包含向量。<ref>{{cite book|editor=James C. Abbot|title=Trends in Lattice Theory|location=Princeton/NJ|publisher=Van Nostrand|year=1967|author=George Grätzer|authorlink=George Grätzer|contribution=IV. Universal Algebra|pages=173&ndash;210}} Here: p.173.</ref>

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

在[[一階邏輯]]的語境下，字元集中的符號又被稱作{{link-en|非邏輯符號|non-logical symbol}}，因為字元集配上邏輯符號便構成了基礎的字母表，可以用於歸納的定義出兩種[[形式語言]]：字元集上'''項'''的集合與（合式）'''公式'''的集合。

在討論[[結構 (數理邏輯)|結構]]時，'''詮釋'''將函數符號和關係符號聯繫到與它們名字相襯的[[數學物件]]：一個<math> n</math>-元函數符號<math> f</math>在以<math> A</math>為論域的結構<math> \mathbf{A}</math>中的詮釋是一個函數<math> f^\mathbf{A} : A^n \to A</math>，而一個<math> n</math>-元關係符號的詮釋是一個[[关系 (数学)|關係]] <math> R^\mathbf{A} \subseteq A^n</math>。當中<math> A^n = A \times A \times \cdots \times A</math>代表論域<math> A</math>和自己的<math> n</math>次[[笛卡兒積]]，如此<math> f</math>便成為了一個<math> n</math>-元函數，而<math> R</math>則是一個<math> n</math>-元關係。

== 多域字元集 ==

多域邏輯和{{link-en|多域結構|structure (mathematical logic)#Many-sorted structures}}的字元集必須包含論域的訊息。最直接的做法便是透過'''{{visible anchor|符號類型}}'''。<ref>[https://web.archive.org/web/20070929131504/http://react.cs.uni-sb.de/%7Ezarba/snow/ch01.pdf Many-Sorted Logic], the first chapter in [https://web.archive.org/web/20081006212815/http://react.cs.uni-sb.de/~zarba/notes.html Lecture notes on Decision Procedures], written by [http://theory.stanford.edu/~zarba/ Calogero G. Zarba] {{Wayback|url=http://theory.stanford.edu/~zarba/ |date=20110927095649 }}.</ref>

=== 符號類型 ===

令<math> S</math>為一個不包含符號<math> \times</math> 和<math> \to</math>的（論域的）集合。

<math> S</math>上的符號類型是字母表<math> S \cup \{\times, \to\}</math>上的特定詞彙：關係符號類型<math> s_1 \times \cdots \times s_n</math>，和函數符號類型<math> s_1 \times \cdots \times s_n \to s^\prime</math>，其中<math> n</math>為非負整數且<math> s_1, s_2, \ldots, s_n, s^\prime \in S</math> （如果<math> n = 0</math>，則表達式<math> s_1 \times \cdots \times s_n</math>表示空詞彙)

=== 字元集 ===

（多域）字元集是一個三元組<math> (S, P, \operatorname{type})</math>包含

* 論域的集合<math> S</math>
* 符號的集合<math> P</math>
* 一個將<math> P</math>中的每個符號送到<math> S</math>上的符號類型的映射<math> \operatorname{type}</math>。

== 參見 ==

* {{link-en|項代數|Term algebra}}

== 附錄 ==

{{reflist}}

== 參考文獻 ==

* {{cite book|last=Burris|first=Stanley N.|author2=Sankappanavar, H.P.|title=A Course in Universal Algebra|url=https://archive.org/details/courseinuniversa00stan|year=1981|publisher=[[Springer Science+Business Media|Springer]]|isbn=3-540-90578-2}} [http://www.thoralf.uwaterloo.ca/htdocs/ualg.html Free online edition] {{Wayback|url=http://www.thoralf.uwaterloo.ca/htdocs/ualg.html |date=20050123031934 }}.
* {{cite book|last=Hodges|first=Wilfrid|title=A Shorter Model Theory|url=https://archive.org/details/shortermodeltheo0000hodg|year=1997|publisher=[[Cambridge University Press]]|isbn=0-521-58713-1}}

== 外部連結 ==

* [http://plato.stanford.edu/entries/model-theory/ Stanford Encyclopedia of Philosophy] {{Wayback|url=http://plato.stanford.edu/entries/model-theory/ |date=20230710172346 }}: "[http://plato.stanford.edu/entries/model-theory/ Model theory] {{Wayback|url=http://plato.stanford.edu/entries/model-theory/ |date=20230710172346 }}"—by [[Wilfred Hodges]].
* [http://planetmath.org/ PlanetMath:] {{Wayback|url=http://planetmath.org/ |date=20050607002330 }}的頁面"[http://planetmath.org/signature Signature] {{Wayback|url=http://planetmath.org/signature |date=20230223005125 }}"介紹了此概念，但沒有提到論域的事情。
* [http://homepages.feis.herts.ac.uk/~comqejb/algspec/pr.html Baillie, Jean] {{Wayback|url=http://homepages.feis.herts.ac.uk/~comqejb/algspec/pr.html |date=20040903183501 }}, "[http://homepages.feis.herts.ac.uk/~comqejb/algspec/pr.html An Introduction to the Algebraic Specification of Abstract Data Types.] {{Wayback|url=http://homepages.feis.herts.ac.uk/~comqejb/algspec/pr.html |date=20040903183501 }}"

{{Mathematical logic}}

[[Category:數理邏輯]]
[[Category:模型論]]
[[Category:泛代數]]