多一化歸(many-one reducibility)是一種較強的化歸關係，概念是波蘭一美國數理邏輯學家波斯特((Post , E. I_.)於1944年引入的。
假設,證明,
假設
多一化歸(many-one reducibility)一種較強的化歸關係.對任意兩個自然數集A,B，若存在遞
歸函式f，使對所有x,xEAHf(x)EB.則稱A可多一化歸到B，記為AGmB.特別地，若f還是一一的函式，則稱A可一一化歸到B，記為B毛,B.所謂A多一化歸到B，實際上是在判定“xEA?”時，只要用到一次B的信息(f(x> EB?>，而對一一化歸，則進一步要求每次使用的信息不同.一一化歸和多一化歸是遞歸論中常見的化歸關係中最強的.
歸函式f，使對所有x,xEAHf(x)EB.則稱A可多一化歸到B，記為AGmB.特別地，若f還是一一的函式，則稱A可一一化歸到B，記為B毛,B.所謂A多一化歸到B，實際上是在判定“xEA?”時，只要用到一次B的信息(f(x> EB?>，而對一一化歸，則進一步要求每次使用的信息不同.一一化歸和多一化歸是遞歸論中常見的化歸關係中最強的.
證明
如果A毛mB，且B毛mA，則稱A, B m等價，記為A三。B.類似地，若A蕊,B且B蕊,A，則稱A,B為1等價，並記為A=, B.除了在“可化歸性”條目中提到的各種P化歸共有的性質外，多一化歸和一一化歸還有一些特殊的性質，如遞歸集不一定能化歸到其他集合;能夠多一或一一化歸到遞歸可枚舉集的集合，也一定是遞歸可枚舉的，並且A毛，兀與A1 A並不普遍成立.此外，一一等價的集合一定是遞歸同構的.由此還可推得若A三;B，則}A}一}B }.多一化歸與一一化歸的概念是波蘭一美國數理邏輯學家波斯特((Post , E. I_.)於1944年引人的.
