Eфективні операції на функціях та множинах

Приклад 3. Оператор : Fт→Fп задається умовою (f)=g для всіх fFт, де g фіксована ЧРФ. Тоді є РО.

Оператор неперервний: умова ( , у)(f) ( , у)() виконується для довільної скінченної f , адже (f)=()=g. Функція (и, )= є ЧРФ за ТЧ.

Приклад 4. Задамо оператор : F1→F1 таким співвідношенням: (f)(x)= f(f(x+2))+5x для всіх fF1. Тоді є РО.Оператор неперервний: (х, у)(f) (х, у)() виконується для кожної скінченної f такої, що x+2D та f(x+2)D. Тепер

(и, х) =

є ЧРФ за ТЧ.

Приклад 5. Оператор мінімізації М: Fп+1→Fп задається умовою М(f)( ) = у(f( , у)=0) для всіх fFп+1. Тоді М є РО.

Оператор М неперервний: у=у(f( , у)=0) у=у(( , у)=0) виконується для кожної f такої, що ( , 0), ( , 1), ..., ( , у)D ; тому y=М(f)( ) y=М()( ) для кожної такої f. Тепер функція

(и, ) = є ЧРФ за ТЧ.

Приклад 6. Нехай ФО 0 : F1→F1 задається співвідношенням 0({(0,0)})={(0,0)} та 0({(1,0)})={(0,1)}; для інших fF1 значення 0(f) невизначене. Тоді 0 розширюється до ЧРО та не розширюється до жодного РО.

Позаяк {C(0,0)}={0}=F1 та {C(1,0)}={2}=F4 , беремо z таке, що Dz ={C(0,20), C(1,22)}. Нехай ОП z задається таким Dz , тобто xz(A) u(FuА(x, u)Dz). Зрозуміло, що для кожних A 2N z(A) l(Dz)={0,1}. Маємо:

Для ЧРО , який визначається таким ОП z , маємо:

1) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))=. Отже, для таких f (f)=f .

2) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={0}=C(0,0). Отже, для таких f (f)={(0,0)};

3) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={1}=C(0,1). Отже, для таких f (f)={(0,1)};

4) Якщо (0,0)f та (1,0)f, то 0C(f) та 2C(f), звідки z(C(f))={0,1} неоднозначна множина. Отже, для таких f (f) невизначене, тому не РО.

Із 2) та 3) випливає, що ЧРО є розширенням оператора 0 .

Нехай ={(0,0), (1,0)}. Для довільного ЧРО , що є розширенням 0 , маємо: якщо (), то ()({(0,0)})=0({(0,0)})={(0,0)} та ()({(1,0)})=0({(1,0)})={(0,1)}. Але тоді () як множина не є функція, тобто (). Отже, кожний такий ЧРО нетотальний, тобто не РО. Таким чином, 0 не можна розширити до РО.

Приклад 7. ЧРО із прикладу 6 немонотонний.

Для {(0,0), (1,0)} маємо (), але ({(0,0)})={(0,0)}. Тому з умови {(0,0)} не випливає ({(0,0)}().

ЧРО називають загальнорекурсивним оператором (ЗРО), якщо Tт D та (Tт)Fn.

Теорема 11.1.5. Нехай ЧРО : Fт→Fп такий, що TтD . Тоді є РО.

Наслідок. Для класів ЗРО, РО та ЧРО маємо строгі включення ЗРОРОЧРО.

За теоремою 11.1.5 ЗРОРО. Але РО прикладу 3 не є, очевидно, ЗРО, якщо ЧРФ g взяти нетотальною, тобто не РФ. За визначенням РОЧРО. Але ЧРО із прикладу 6 немонотонний, тому не РО.