記號系統

要滿足以下三個條件:

為遞歸的，則稱S為遞歸相關的;若對任何可構造序數a,S中都有a的記號，則稱S為極大的;若對任何記號系統S，都存在部分遞歸函數P: Ds,---＞Ds，使二E Dsvs (x) ws抓(x)，則稱S為完全的.對任何記號系統S，若S為遞歸相關的，則S為遞歸的;若S為完全的，則S為極大的.此外，以下的完全系統O在超算術分層等的定義中扮演了重要角色.系統O的定義域D,與偏序＜0歸納定義如下:

1. 0的記號為1.

2.若Y=月-1，則對任何月的記號二，令2為Y的記號，並且若z=x或(z,x)已在＜。中，將＜z,(2)加入關係＜n中.

3.若Y為極限序數，則對任何y，若Py＜(n)“-o為以Y為極限的無窮上升序數序列的記號集，並且d(t)＜(d)CzG.7Wy＜＜,p,＜＞已經在＜。中，則令3X5''為Y的記號;對任何滿足(3n)C＜二，Py(n)＞已＜。中的z，將＜2,3X5'＞放人＜。中.ko(1)=0,ko(2r)一l;ko(3X 5y)一2;ps， (2=)一x;qsl (3 X 5y)一y，對未給出定義的值，令其為無定義.

最早對記號系統進行研究的是美國數學家、邏輯學家丘奇(Church , A.)與美國邏輯學家、數學家林(Kleene,S. C. )，以上的定義是克林給出的，他人稱這樣的系統為r系統.