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

T-степінь b називають повною, якщо b=a' для деякої T-степені a. Повна T-степінь складається тільки з Т-повних множин. Множина всіх повних T-степенів є множиною значень операції скачка.

Введемо операцiю n-кратного скачка для множин та степенів

.

Для довiльної T-степенi a покладемо a(0)=a, a(k+1)=(a(k))'.

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

jn1) A(0)
jn2) a(0)
jn3) Якщо A(TB, то A(n)(mB(n) для всiх n(1.

\xF077-скачком множини A(N назвемо множину A(()={C(x, y) | x(A(y)}.

Із цього визначення випливає: х(А(() ( l(x)(А(r(x))

, то A(()(T B.

є В-РФ.

.

.

Як наслідок звідси отримуємо, що A(у)
Тeорeма 4.6. Якщо A(T B, то A(() (m B(().

Тeорeма 4.7. Існують множини A і B такi: A(() (m B(() та B