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

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

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

Множество А натуральных чисел называется один-один сводимый к набору B если есть полная вычислимая инъекция ж на натуральные числа такие, что ${ displaystyle f (A) substeq B}$ и ${ Displaystyle е ( mathbb {N} setminus A) substeq mathbb {N} setminus B}$ .

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

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

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

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

Гипотеза Бермана – Хартманиса, аналогичное утверждение в теория сложности вычислений

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

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

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

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