可構造序數是一種特殊的序數。α為可構造序數，是指存在一個記號系統S，使得S中有α的記號。可構造序數都是可數序數，可構造序數的全體構成序數的一個前節，並且可構造序數只有可數多個。
遞歸序數(recursive ordinal)是一種可構造序數。α為遞歸序數是指存在(某個自然數集上的)遞歸關係R，使得R為良序，並且R給出良序與α同構。
基本介紹
- 中文名：遞歸序數
- 外文名：recursive ordinal
- 領域：數學
- 性質：可構造序數
- 本質：特殊的序數
- 特點：良序
概念,序數,良序,可構造序數,遞歸,
概念
遞歸序數(recursive ordinal)是一種可構造序數。α為遞歸序數是指存在(某個自然數集上的)遞歸關係R，使得R為良序，並且R給出良序與α同構。事實上，一個序數為遞歸序數，若且唯若該序數為可構造序數。因此，遞歸序數與可構造序數的定義是一致的。
序數
序數是良序集之 “長度” 的一種度量。在樸素集論中，我們視序數為相似的良序集全體或其屬性的一種抽象 (即良序集之序型)。序數常用希臘字母α、β、γ等來表示。任何兩個序數可比較大小；任一序數集合中必有一個最小的序數。在公理集論中，我們在相似的良序集中取出唯一的具典型構造(序數之集論構造即數集二重性的超限拓廣)的代表元作為相應的序數，把序數α與序數集 {β： β<α} 視為同一 (數集二重性); 進而把基數定義為互相對等的序數中最小的一個。在有限場合，序數與基數是重合的，即自然數。ω是第一個無限序數，ω=0=|N|。其後依次是ω+1，ω+2，…，ω+n，…，ω+ω=ω2，ω2+1，…，ωn，…，ω·ω=ω2，…，ωω，…第一個不可數序數記為ω1(N1)，其後是ω1+1，…依次類推。非0序數全體分為兩大類：一類形如α+1，稱為(α的)後繼序數，常記為α；另一類序數恰是它前面序數的不可達到的上確界，如ω，ω，ω，ω1等，稱為極限序數。
序數α加β，其和α+β是指視α，β為良序集先α後β首尾連線而得的良序集所對應的序數。α乘β其積αβ，是指β個良序集α的拷貝按β的序型前後連線而得的良序集所對應的序數。序數算術中有結合律，但交換律不成立(1+ω=ω+1，2ω=2+2+…+2+…即可列個2相加=ωω2)，只有左分配律 (α(β+γ) =αβ+αγ)，左消去律 (α+β=α+γ⇒β=γ)及左單調性(β<γ⇌α+β≤α+γ) 等。其他與基數算術不同處，如ω2=ω·ω>ω+ω=ω2 (而0=0+0=0);2(序數冪)： =2·2…2…(ω個2自乘)=ω=3=n(而)。進一步還可引入序數的減法、除法及對數運算，它們的一些性質也有單側性限制。
自然數集ω上的數學歸納法 (包括證明與定義) 可以自然地拓廣到任一極限序數(甚至全體序數類) 上去，稱為超窮歸納法。後者除後繼序數場合外，還須考察極限序數的場合。歸納法定義又稱遞歸定義，下以序數算術中的加法、乘法與冪的遞歸定義為例說明之。α+0=α;α+β=(α+β)+;當λ為極限序數時α+λ=sup {α+β： β<λ}。α·0=0; α (β) =αβ+α;αλ=sup {αβ; β<λ}。α=1; α=(α) α; α=sup{α： β<λ}。
良序
亦稱“整序”。一種非常重要的序關係。設(x≤)是全序集，如果x的任一非空子集u總有最小元素，則x稱為一個良序集，≤稱為良序關係。由於良序集x的任一非空子集u必有最小元素，因此u必有極小元素，所以良序集既是全序集又是基序集。良序關係是建立序數理論的基礎，因而也是研究集合分層理論與基數理論的必要前提。良序集具有非常整齊的結構，任何兩個良序集或者彼此序同構;或者其中之一序同構於另一個的某一截段，即小於某一元素的一切元素所成之集。良序化定理可以表述為：“每一個集合都可以通過賦予一種次序，使之成為良序集。”良序化定理作為選擇公理的一個等價命題，是集合論中的一個重要定理。
可構造序數
可構造序數是一種特殊的序數。α為可構造序數，是指存在一個記號系統S，使得S中有α的記號。可構造序數都是可數序數，可構造序數的全體構成序數的一個前節，並且可構造序數只有可數多個。從直觀上說，可構造序數是可以在自然數上能行表示的序數。事實上，對任何可構造序數，都存在遞歸相關的單一的記號系統S，使得S中有該序數的記號。此外，可構造序數也恰為遞歸序數。最早定義可構造序數並對之進行研究的是美國數學家、邏輯學家丘奇(Church，A.)。
遞歸
一個函式、過程或者數據結構，如果在它們定義的內部又出現有定義本身的套用，則稱它們是遞歸的，或者是遞歸定義的。例如，一個過程的某一步要用到它自身的上一步的結果。
遞歸是一種強有力的數學工具，它給程式設計帶來方便。一個算法採用遞歸的方法來描述，往往比較精練和明晰，但是，在程式中無限制地使用遞歸會使程式的效率非常低。因為每次遞歸調用，都必須首先做諸如參數替換，環境保護等事情。另外，大量的重複計算也是造成效率低下的一個重要原因，所以有個別高級語言禁止使用遞歸。由於遞歸特別符合人們的思維習慣，遞歸算法的設計要比遞歸程式的設計容易。因此多數語言還允許使用遞歸，或者將遞歸算法變換成遞歸程式去執行。
