多一归约
书籍:逻辑百科辞典
简称m归约。设A、B为自然数集，如果存在递归全函数f(x)使
x∈A当且仅当f(x)∈B则称A可m归约到B，记作
A≤B．
如果f(x)还是1－1函数，则称A可一一归约到B，记作
A≤B．
显然，如果A≤B，则A≤B，但反之不然(例如｛1，2｝≤｛1｝，但1｛1，2｝
｛1｝)．
m归约有以下基本性质：
(1)≤(≤)是偏序关系(自反、传递)。
(2)A≤B当且仅当
A≤B当且仅当
(3)如果A≤B(A≤B)且B是递归集，则A是递归集。
(4)如果A≤B(A≤B)且B是递归可枚举集，则A是递归可枚举集。
(5)如果A是递归集，B≠，N，则A≤B(但未必有A≤B)。
(6)如果A≤B(A≤B)，则A≤B(参见图灵归约)，但反之不然(例如对K=｛x｜φ(x)有定义｝，≤K，但)。
(7)A≤N当且仅当A=N
A≤当且仅当A=
(8)N≤A当且仅当A≠
≤A当且仅当A≠N
(其中N是由全体自然数所组成的集合)
(9)A≤B则｜A｜≤｜B｜且｜｜≤｜｜
(其中｜A｜表示集合A的基数)
如果A≤B且B≤A(A≤B且B≤A)则称A、B为m等价(1等价)的，记作A≡B(A≡B)．
≡(≡)是等价关系(自反、对称、传递)．(参见m完全集、m度。)