마이힐 이소모르피즘 정리

계산가능성 이론에서 존 마이힐의 이름을 딴 마이힐 이소모르프리즘 정리는 두 개의 번호에 대한 특성화를 제공하여 집합에 동일한 계산가능성의 개념을 유도한다.

마이힐 이소모르피즘 정리

자연수 집합 A와 B는 자연수 집합에서 f(A) = B로 계산 가능한 총 편향 f가 있으면 반복적으로 이형성이 있다고 한다.^{[further explanation needed]}

A set A of natural numbers is said to be one-one reducible to a set B if there is a total computable injective function f on the natural numbers such that ${\displaystyle f(A)\subseteq B}$ and ${\displaystyle f(\mathbb {N} \setminus A)\subseteq \mathbb {N} \setminus B}$.

마이힐의 이형성 정리에서는 자연수의 두 세트 A와 B가 반복적으로 이형성인 경우 A가 B로, B가 A로 1 축소 가능한 경우에만 반복적으로 이형성인 것으로 되어 있다.

그 정리는 슈뢰더-번스타인 정리를 연상시킨다.그러나 증거는 다르다.슈뢰더-베른슈타인의 증거는 두 주사제의 반전을 사용하는데, 이러한 반전은 재귀적이지 않을 수 있기 때문에 마이힐 정리의 설정에서는 불가능하다.반면 마이힐 정리의 증명은 귀납적으로 편향성을 정의하는데, 이는 슈뢰더-베른슈타인의 설정에서 한 사람이 (증명에 필요치 않은) 악시오머(Axiom of Choice)를 사용하지 않는 한 불가능하다.

마이힐의 정리의 한 가지 진리는 두 개의 총수가 반복적으로 이형성인 경우에만 1등분한다는 것이다.

참고 항목

• 베르만-하트마니스의 추측, 계산 복잡성 이론의 유사성 진술

참조

• Myhill, John (1955), "Creative sets", Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1: 97–108, doi:10.1002/malq.19550010205, MR 0071379.
• Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.
• Soare, Robert I. (1987) 재귀적으로 열거된 세트와 도 : 계산 가능한 기능과 계산적으로 생성된 세트의 연구, 수학 논리에서의 관점, 베를린 하이델베르크 : 스프링거-Verlag, ISBN 978-3-540-66681-3, MR 0882921