Звідності. Відносна обчислюваність , Детальна інформація

Наслідок 1. A(T B \xF0DB DA (m DB.

Наслідок 2. Якщо A(T B, то DA (T DB.

Зворотне до наслiдку 2 твердження невiрне (див.[9]). Можливi випадки A
Ефективним варіантом теореми 9.4.3 є

, то (f(z) : DA(m DB;

.

Вiдношення (T є вiдношенням еквiвалентностi, тому вводимо класи еквiвалентностi dT(A)={B | A(T B} вiдносно (T. Такi класи будемо називати T-степенями, або степенями нерозв'язностi.

На множинi T-степенiв введемо вiдношення часткового порядку, яке також будемо позначати ( :

a(b, якщо A(T B для деяких A(a, B(b.

Зрозумiло, що a(b \xF0DB A(T B для всiх A(a, B(b.

Будемо писати a
Будемо писати a | b, якщо невірно a(b та невірно b(a.

T-степiнь назвається рекурсивною, якщо вона мiстить РМ.

T-степiнь назвається рекурсивно перелiчною (РП-T-степiнню), якщо вона мiстить РПМ.

Вкажемо деякi властивостi T-степенiв:

s1) Існує єдина рекурсивна T-степiнь 0, яка складається iз всiх РМ. Вона є найменшою T-степiнню: 0
s2) Існує найбiльша рекурсивно перелiчна T-степiнь 0'=dT(D) така, що b(0' для кожної рекурсивно перелiчної T-степенi b.

s3) Кожна нерекурсивна РП-степiнь мiстить множини, якi не є РПМ.

s4) Якщо dm(A)(m dm(В), то dТ(A)(Т dТ(В).

s5) dm(A)( dТ(A) для довiльної множини A.

Тeорeма 4.5. Для кожної пари T-степенiв a та b iснує єдина точна верхня грань a(b=dT(A(B), де A(a, B(b.

Oперацiю скачка поширимо на множину T-степенiв.

Скачком T-степенi b називають степiнь b'=dT(DB), де B(b.

Таке визначення коректне, бо за наслiдком 2 теореми 9.4.3 b' не залежить вiд вибору конкретного представника B(b.

Вкажемо деякi властивостi операцiї скачка.

jm1) b
jm2) Якщо a
jm3) 0
jm4) Якщо a=b, то a'=b'.

jm5) Якщо A(a, B(b та B є A-РПМ, то b