Нумерації. Теореми про нерухому точку, Детальна інформація

Розглянемо приклади застосування s-m-n-теореми.

Приклад 2. Існує РФ s(x, y) така, що для всіх х, y, z\xF0CEN маємо (s(x,y)(z)=(x(z)+(y(z).

Розглянемо функцію f(x, y, z)=(x(z)+(y(z). Функція f є ЧРФ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, z\xF0CEN маємо f(x, y, z)=(s(x,y)(z)=(x(z)+(y(z).

Приклад 3. Для кожної 1-арної ЧРФ f існує РФ s(x) така, що для всіх х\xF0CEN маємо Ds(x)= f-1(Dx).

Розглянемо функцію g(x, y)=(x(f(y)). Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x) така, що для всіх х, y\xF0CEN маємо g(x, y)=(s(x)(у). Зафіксуємо х. Mаємо у(Ds(x) ( (s(x)(у)( ( g(x, y)( ( (x(f(y))( ( f(y)(Dx ( y(f-1(Dx). Звідси Ds(x)= f-1(Dx).

Приклад 4. Існує РФ s(x) така, що для всіх х\xF0CEN маємо Еs(x)=Dx .

Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x) така, що для всіх х, y\xF0CEN маємо f(x, y)=(s(x)(у). Зафіксуємо х. За побудовою функції f маємо Ds(x)=Еs(x). Тепер у(Еs(x) ( у(Ds(x) ( (s(x)(у)( ( f(x, y)( ( у(Dx . Звідси Еs(x)=Dx .

Приклад 5. Існує РФ t(x) така, що для всіх х\xF0CEN маємо Dt(x)=Еx .

Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ t(x) така, що для всіх х, y\xF0CEN f(x, y)=(t(x)(у). Зафіксуємо х. Mаємо у(Dt(x) ( (t(x)(у)( ( f(x, y)( ( у(Ex . Звідси Dt(x)=Ex .

={(u, v) | x=2u+3v}.

={(u, v) | x=2u+3v}.

Приклад 7. Існує РФ s(x, y) така, що для всіх х, y\xF0CEN маємо Ds(x,y)=Dx(Dy .

Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, z\xF0CEN маємо f(x, y, z)=(s(x,y)(z). Зафіксуємо х та y. Маємо z(Ds(x,y) ( (s(x,y)(z)( ( f(x, y, z)( ( z(Dx(Dy . Звідси випливає Ds(x,y)=Dx(Dy .

Приклад 8. Існує РФ s(x, y) така, що для всіх х, y\xF0CEN маємо Ds(x,y)=Еs(x,y)=Dx(Dy .

Така функція є ЧРФ за ТЧ, тому за s-m-n-теоремою існує РФ s(x, y) така, що для всіх х, y, z\xF0CEN маємо f(x, y, z)=(s(x,y)(z). Зафіксуємо х та y. За побудовою функції f маємо Ds(x,y)=Еs(x,y). Тепер z(Еs(x,y) ( z(Ds(x,y) ( (s(x,y)(z)( ( f(x, y, z)( ( z(Dx(Dy . Звідси отримуємо Ds(x,y)=Еs(x,y)=Dx(Dy .

4. ТЕОРЕМИ КЛІНІ ПРО НЕРУХОМУ ТОЧКУ

для всiх значень x1, ..., xп.

Переформулюємо теорему 7.4.1 для випадку n=0.

Теорема 4.2. Нехай f(x) \xF02D РФ. Тодi iснує n\xF0CEN таке, що (n = (f(n).

Первісне формулювання самого С.Кліні теореми про нерухому точку має наступний вигляд:

Теорема 4.3. Нехай h(z, x) \xF02D ЧРФ. Тодi iснує n\xF0CEN таке, що для всiх x маємо h(n, x)=(n(x).

Теорему Клiнi про нерухому точку краще називати теоремою про псевдонерухому точку. Справдi, умова (n=(f(n) зовсім не означає, що n=f(n), a свiдчить тiльки про те, що n та f(n) \xF02D iндекси однієї i тої ж ЧРФ.

Приклад 1. МНР-програму P назвемо самотворною, якщо для довiльного x\xF0CEN маємо P(x)(((P), де \xF074(P) \xF02D код програми P. На перший погляд, таких програм бути не може, бо для побудови P треба знати \xF074(P) тобто саму програму P. Проте МНР-програма P така, що P(x)(((P) для всiх значень x, таки існує.

Справді, вiзьмемо функцiю h(z, x)=z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)=(n(x). Отже, (n(x)=h(n, x)=n для всiх x. Тому програма P з кодом n \xF02D шукана.

Приклад 2. Існує n\xF0CEN таке, що для всiх x маємо (n(x)=2n+x3n.

Вiзьмемо функцiю h(z, x)=2z+x3z. За теоремою 7.4.3 iснує таке n, що для всiх x h(n, x)=(n(x). Отже, (n(x)=h(n, x)=2n+x3n для всiх x.

Приклад 3. Існує n\xF0CEN таке, що Dn=En={n}.

Звідси Dп=Еп={n}.

Приклад 5. Існує n\xF0CEN таке, що Dп=En=N\{n, 2n}.

Звідси Dп=En=N\{n, 2n}.