НОУ ІНТУІТ, Лекція, m-зведення та властивості перелічуваних множин

Ізоморфізм m-повних множин

У цьому розділі ми доведемо, що всі m-повні множини "влаштовані однаково" і відрізняються один від одного тільки перестановкою, що обчислюється.

Теорема 41. Нехай A і B m-повні перелічені множини. Тоді існує перестановка, що обчислюється (обчислювана взаємно однозначна відповідність) f : N -> N , коли A перетворюється на B , тобто за всіх x .

Ми використовуватимемо той самий прийом, що й у наведеному вище доказі теореми Роджерса про ізоморфізм головних нумерацій. Саме ми для початку доведемо таку лему:

Лемма. Нехай A m -повна перелічувана множина. Тоді існує спосіб за будь-яким натуральним числом n алгоритмічно вказати скільки завгодно інших натуральних чисел, які належать або не належать A одночасно з n.

Доказ леми. Як і раніше, у нас будуть два способи отримувати нові числа, які поводяться до A так само, як і вихідне. Одне з них гарантовано давати нове число, якщо , інший якщо . При цьому ми можемо застосовувати обидва, не знаючи, який із випадків має місце насправді (і можемо так і не дізнатися).

Перший спосіб полягає в наступному. Нехай P перерахована нерозв'язна множина. Розглянемо безліч пар A x P . Воно зводиться до A, тому що A є m-повним. (Взагалі-то у визначенні зведеності йшлося про безлічі натуральних чисел, а не пар, але, як завжди, це не грає ролі пари можна обчислимо нумерувати.) Іншими словами, існує обчислювана всюди певна функція f двох натуральних аргументів з такою властивістю:

Зокрема, за числа n і f(n,m) одночасно належать або не належать A . Тому, розташувавши P в обчислюванупослідовність p(0),p(1), .. ., ми можемо обчислювати числа f(n,p(0)),f(n,p(1)), .. . і отримувати нові числа, що належать або не належать A одночасно з n.

Нехай. Покажемо, що безліч X одержуваних таким чином чисел (всі вони в цьому випадку теж належать A) буде нескінченно. Насправді, при (за побудовою X) і при (оскільки в цьому випадку, а). Таким чином, функція m -> f(n,m) зводить нерозв'язну множину P до множини X , так що X нерозв'язно і тому нескінченно.

Тепер опишемо інший спосіб, який гарантує успіх, якщо . Візьмемо два перераховані невіддільні множини P і Q . Розглянемо безліч пар. Нехай функція f зводить його до A . Це означає, що і тоді, коли або . Як і раніше, за числа n і f(n,m) одночасно належать або не належать A так що ми можемо знову розглянути послідовність f(n,p(0)),f(n,p(1)). .; залишилося лише показати, що (якщо ) у цій послідовності нескінченно багато різних членів.

Нехай це не так і безліч X всіх членів цієї послідовності, звичайно. На нашу думку X не перетинається з A . Зауважимо, що при (за побудовою) і при (оскільки в цьому випадку належить нашій множині пар і f(n,m) належить A ). Таким чином, прообраз множини X при відображенні m -> f(n,m) відокремлює P від Q. Але цей прообраз дозволимо ( X можна розв'язати, бо звичайно, а зазначене відображення всюди визначено і обчислимо). А за нашим припущенням безлічі P і Q не можна відокремити розв'язаною множиною.

Отже, ми навели два способи отримувати нові елементи, які належать або не належать A одночасно з вихідним. Застосовуючи їх паралельно, ми напевно досягнемо результату. Лемма доведена.

Нехай тепер A та B два m-Повних перелічених множини. Доведемо, що вони відрізняються лише перестановкою натурального ряду, що обчислюється. Будуватимемо цю перестановку за кроками. На k-му кроці ми маємо взаємно однозначну відповідність

при якому за всіх i . На парних кроках ми беремо мінімальне число, яке не входить до лівої частини цієї відповідності. Використовуючи факт m-зведеності A до B, ми знаходимо йому компаньйона. При цьому доведена нами лема дозволяє вибрати компаньйона, який не зустрічається серед елементів, що вже є праворуч. На непарних кроках ми робимо те саме, тільки праворуч наліво.

У межі цей процес дає шукану перестановку, що обчислюється, що зв'язує A і B .

З точки зору теорії алгоритмів дві множини, що відрізняються лише обчислюваною перестановкою, мають однакові властивості. Тому доведена теорема показує, що по суті є лише одне m-повне перелічуване безліч (або, що те саме, лише одне перелічуване безліч з ефективно неперелічуваним доповненням).

Продуктивні множини

У цьому розділі ми використовуємо теорему про нерухому точку для отримання такого (несподіваного на перший погляд) результату: визначення ефективної неперелічимості множини A не зміниться, якщо ми обмежимося лише (переліченими) підмножинами множини A .

Зафіксуємо деяку головну нумерацію множин, що перераховуються (множину з номером n ми позначаємо Wn ). Кажуть, що множина A єпродуктивною, якщо існує обчислювана (не обов'язково всюди визначена) функція f з такою властивістю: вона застосовна до будь-якого номера n будь-якого підмножини Wn множини A і дає елемент у їх різниці:

49. Доведіть, що продуктивна множина не може бути імунною.

Зрозуміло, що вимоги щодо визначення продуктивності лише частинавимог з визначення ефективної неперелічуваної множини , так що будь-яка ефективно неперелічувана безліч продуктивна. Дивним чином виявляється, що вірне та протилежне.

Теорема 42. Нехай A продуктивна множина, K довільна множина, що перераховується. Тоді доповнення до K m зводиться до A .

(З цього випливає, що A є ефективно неперерахованим, див. вище.)

Нехай f функція , яка існує за визначенням продуктивності (і дає елемент поза підмножиною із зазначеним номером).

Ми побудуємо всюди визначену функцію s з такими властивостями:

(друга властивість передбачає, що f(s(x)) визначено за ). Перш ніж робити це за допомогою теореми про нерухому точку, зауважимо, що в першому випадку f(s(x)) визначено і належить A : оскільки множина з номером s(x) порожня і є підмножиною A число f(s(x) ) має бути елементом A. Навпаки, у другому випадку f(s(x)) не належить A . Справді, якби це було не так, безліч Ws(x) було б підмножиною A , і тому число f(s(x)) мало б бути елементом A , що не входить в це підмножина а воно входить.

Тому якщо нам вдасться збудувати таку функцію s , то функція x -> f(s(x)) буде m -зводити доповнення множини K до множини A, як ми і обіцяли. Як її будувати?

Якби у другому властивості (для ) стояло не f(s(x)) , а, скажімо, просто f(x) , ніякої проблеми не було. Як завжди, ми розглянули б безліч пар

перерізи цієї множини мали б необхідний вигляд і залишилося тільки скористатися тим, що нумерація головна. Але в нашому випадку, коли в правій частині другої властивості стоїть f(s(x)) , так просто вчинити не можна: як в історії про курку та яйця,побудови V нам треба мати s(x), а для побудови s(x) треба мати V.

Саме такого роду труднощі дозволяє долати теорема про нерухому точку. Побудуємо всюди певну обчислювану функцію двох аргументів h з такими властивостями:

(Подібні речі ми робили багаторазово останній раз у попередньому абзаці. Зазначимо, що f(t) може бути і не визначено, тоді під ми розуміємо порожню множину.) По теоремі про нерухому точку (для перелічуваних множин) при кожному x функція має нерухому точку , і, як ми говорили в розділі про нерухому точку з параметром, цю нерухому точку можна вибрати залежать від x . Таким чином, існує всюди певна обчислювана функція s для якої

за всіх x . Цю рівність можна продовжити:

- це те, чого ми й хотіли. Зауважимо, що значення f(s(x)) визначено за всіх x (інакше і f(s(x)) має бути визначено). Тим самим, теорема про нерухому точку дозволяє знайти взаємно узгоджені яйце і курку і завершує доказ.