Теорема об изоморфизме Майхилла - Myhill isomorphism theorem

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

Теорема об изоморфизме Майхилла

Наборы А и B из натуральные числа как говорят рекурсивно изоморфный если есть общий вычислимый биекция ж из набора натуральных чисел к себе так, что ж(А) = B.

Множество А натуральных чисел называется один-один сводимый к набору B если есть полная вычислимая инъекция ж на натуральные числа такие, что и .

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

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

Следствие теоремы Майхилла состоит в том, что два общая нумерация находятся один эквивалент если и только если они вычислимо изоморфный.

Смотрите также

Рекомендации

  • Myhill, Джон (1955), «Творческие наборы», Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, 1: 97–108, Дои:10.1002 / malq.19550010205, МИСТЕР  0071379.
  • Роджерс, Хартли младший (1987), Теория рекурсивных функций и эффективная вычислимость (2-е изд.), Кембридж, Массачусетс: MIT Press, ISBN  0-262-68052-1, МИСТЕР  0886890.