m度

自然数集在(等价关系)≡下的等价类称为m度，含有集合A的m度记作d(A)：

d(A)=｛BA≡B｝

(参见多一归约)。

设a、b为两个m度，A∈a，B∈b；如果A≤B，则记a≤b；若a≤b且a≠b，则记a＜b

以下是几个特殊的m度：

(1)d(Φ)=｛Φ｝，此度记为0；

(2)d(N)=｛N｝，此度记为n；

(3)设A为递归集且A≠Φ，N，则d(A)=｛BB是递归集且B≠Φ，N｝，此度记作O；

(4)d(K)=｛BB是m完全集｝，此度记为O＇。

其间的关系是：o＜O＜Om，n＜O＜Om。o，n是两个极小度，它们之间不可比较，因而都不是最小度，O是o、n以外的m度中的最小度。o与O之间、n与O之间再无其他m度。O与Om之间还有其他(递归可枚举的)m度，例如当A是单纯集时

O＜d(A)＜Om。

任给m度a、b，a、b有最小上界c：a≤c，b≤c，且对任意c＇，如果a≤c＇，b≤c＇，则c≤c＇。但a、b未必有最大下界(如o、n)。

m度的结构可用下图表示：

图 m度

(r．e为“递归可枚举”的缩写)。

(参见多一归约，m完全集。)