マイヒル同型定理

計算可能性理論において、ジョン・マイヒルにちなんで名付けられたマイヒル同型定理は、2つの番号付けが集合上の同一の計算可能性の概念を導く特徴付けを提供する。これは集合論におけるシュレーダー・ベルンシュタイン定理を彷彿とさせ、その構成的版と呼ばれている。^{[1] : 320}

定理

集合から集合への多対一還元は、となる全計算可能関数です。一対一還元は単射還元であり、計算可能同型は全単射還元です。 ${\displaystyle A\subseteq \mathbb {N} }$ ${\displaystyle B\subseteq \mathbb {N} }$ ${\displaystyle f:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle \forall x\in \mathbb {N} ,x\in A\iff f(x)\in B}$

マイヒルの同型定理: 2 つの集合が計算可能に同型であるためには、AがBに 1 対 1 還元可能であり、かつ BがAに 1 対 1 還元可能であることが必要である。 ${\displaystyle A,B\subseteq \mathbb {N} }$

結果として、2 つの全番号付けが 1 同値となるのは、それらが計算可能同型である場合のみです。

証明の概要

を2つの集合とし、すべての に対して、と が成り立つような、単射で全計算可能な関数が存在すると仮定します。 すべてのに対して、 が成り立つような、全計算可能かつ単射な関数を構築したいとします。${\displaystyle A,B\subseteq \mathbb {N} }$ ${\displaystyle f,g:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle x\in \mathbb {N} }$ ${\displaystyle x\in A\iff f(x)\in B}$ ${\displaystyle x\in B\iff g(x)\in A}$ ${\displaystyle h:\mathbb {N} \to \mathbb {N} }$ ${\displaystyle x\in \mathbb {N} }$ ${\displaystyle x\in A\iff h(x)\in B}$

ℕの最初のコピーから始まる片側チェーン

ℕの2番目のコピーから始まる片側チェーン

両面チェーン

サイクル

シュレーダー・ベルンシュタインの定理のほとんどの証明と同様に、と を連続的に適用することで形成される「連鎖」の解析を用います。非公式には、 の2つの「コピー」を考え、それらの間に一対一の関係を構築します。最初のコピーの数値を考え、それを によって2番目のコピーの数値に渡し、さらに によって最初のコピーの数値に渡し、といった具合です（これらのコピーは反対側の図では青と緑で示されています）。と は単射であるため、これらの連鎖は「重なり合う」ことはありません（2つの連鎖が併合されることはありません）。ある要素から開始して連鎖をたどっていくときに何が起こるかによって、3種類の連鎖が考えられます。 ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle \mathbb {N} }$ ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$ ${\displaystyle g}$

• 一方的な連鎖。これは最終的に、またはによる原像を持たない要素で停止します。${\displaystyle f}$ ${\displaystyle g}$
• 両側チェーン。ループバックせずに無限に継続します。
• サイクルでは、最終的にはすでに見た要素が生成されます。

各チェーンについて、すべての青い要素がAにあり、すべての緑の要素がBにあるか、または青い要素がAになく、緑の要素がBにないことに注目してください。

シュレーダー＝ベルンシュタインの定理の文脈において全単射を構築するには、各連鎖の要素をペアにするだけで十分である。片側連鎖では最初の要素の色に応じてまたはを使用し、両側連鎖または閉路ではどちらでも使用できる。マイヒルの定理では、構築された全単射は計算可能である必要がないため、この方法は機能しない。 ${\displaystyle f}$ ${\displaystyle g}$

代わりに、要素を順にペアリングすることで一対一対一の関係を構築します。各段階で、青いコピーから次のペアになっていない要素を取り出し、それを緑のコピーのペアになっていない要素とペアリングします。次に、緑のコピーから次のペアになっていない要素を取り出し、同じことをします。これにより、両方のコピーのすべての要素が、ある時点でペアリングされることが保証されます。 ${\displaystyle \mathbb {N} }$

青色の要素をペアにしたいとします（緑色の要素の場合は対称的です）。考え方としては、チェーン上の次の緑色の要素を取得するために適用し、この要素がペアになっていない場合は、それを青色の要素とペアにします。ペアになっている場合は、チェーン上の次の緑色の要素に進み、ペアになっていない緑色の要素が見つかるまでこれを繰り返します。 ${\displaystyle f}$ ${\displaystyle g}$ ${\displaystyle f}$

この一対一表現を効果的に計算するために、アルゴリズムは入力がペアになるまでペアを計算し、ペアのもう一方の要素を返すことができます。

参照

• 計算複雑性理論における類似の記述であるバーマン・ハルトマニス予想。

参考文献

1. Odifreddi, P. (1989).古典的再帰理論：関数と自然数集合の理論. 論理学と数学の基礎研究. 第125巻. エルゼビア. ISBN 0-444-87295-7。

• Myhill、John (1955)、「クリエイティブ セット」、Zeitschrift für Mathematische Logik und Grundlagen der Mathematik、1 (2): 97–108、doi :10.1002/malq.19550010205、MR  0071379。
• ロジャース、ハートレー・ジュニア（1987年）、再帰関数と実効計算可能性の理論（第2版）、ケンブリッジ、マサチューセッツ州：MITプレス、ISBN 0-262-68052-1、MR  0886890。
• Soare, Robert I. (1987),再帰的に列挙可能な集合と次数：計算可能関数と計算可能生成集合の研究, Perspectives in Mathematical Logic, Berlin Heidelberg : Springer-Verlag, ISBN 978-3-540-66681-3, MR 0882921