Введение

Теорема Гудмана — Михилла в конструктивной теории множеств. В теории вычислимости теорема изоморфизма Михилла, названная в честь Джона Михилла, предоставляет характеристику для двух нумераций, индуцирующих одно и то же понятие вычислимости на множестве.

Определения

Множества A и B натуральных чисел называются рекурсивно изоморфными, если существует тотальная вычислимая биективная функция f на натуральных числах такая, что для любого n, n ∈ A тогда и только тогда, когда f(n) ∈ B.

Множество A натуральных чисел называется одно-к-одно сводимым к множеству B, если существует тотальная вычислимая инъективная функция f на натуральных числах такая, что n ∈ A тогда и только тогда, когда f(n) ∈ B.

Заявление

Теорема изоморфизма Майхилла утверждает, что два множества натуральных чисел A и B рекурсивно изоморфны тогда и только тогда, когда A одноредуктивно к B, и B одноредуктивно к A.

Королярии

Две полные нумерации эквивалентны тогда и только тогда, когда они рекурсивно изоморфны.

Обсуждение

Теорема подразумевает, что для любых двух инъективных редукций в противоположных направлениях существует вычислимая биекция на множестве натуральных чисел, устанавливающая биективное соответствие между рассматриваемыми множествами. Это напоминает теорему Шредера — Бернштейна об общих множествах, и теорему Майхилла иногда называют ее конструктивной версией. Однако их доказательства различны. Доказательство теоремы Шредера — Бернштейна использует обратные к двум инъекциям, что невозможно в контексте теоремы Майхилла, поскольку эти обратные функции могут не быть рекурсивными. С другой стороны, доказательство теоремы Майхилла определяет биекцию индуктивно, что невозможно в контексте теоремы Шредера — Бернштейна без использования аксиомы выбора (которая не требуется для доказательства теоремы Майхилла).