Файл: Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf

236

КОНСТРУКТИВНЫЕ ФУНКЦИИ

[ГЛ. S

Интересным

следствием

аппроксимационной

теоремы

Г. С. Цейтина

является

теорема И. Д. Заславского и

Г. С. Цейтина

( Ц е й т и н

[8]), утверждающая, что всякая

конструктивная

функция является на всей своей обла­

сти определения пределом

некоторой последовательно­

сюда, в частности, следует, что любая

конструктивная

функция является на всей своей области

определения

пределом некоторой

последовательности

полиномов.

1. Выполним

некоторые

предварительные

построения.

Л е м м а

1.

Можно

построить алгорифм

Рз*1),

пере­

рабатывающий

всякое

слово

Т вида

х0 * .. . * хп, х,

где

Хо * ... * хп

— положительное

дробление,

х — КДЧ

та­

кие, что п ^

2 и х0 Й=: х ^

хп,

в натуральное

число,

при­

чем

0 < Р з ' , ) ( 7 , ) < « - 2

и

хр3М

(Т) ^

х

^

*рэ (1) (Г)+2*

Кроме

того,

если

х0

< х < хп, то

*Рз*')(Г)

<

х

<

XP3<1UT)+2'

Д о к а з а т е л ь с т в о .

Построим

искомый

алгорифм

Рз*1), пользуясь теоремами сочетания алгорифмов

так,

чтобы при всяком п ^

2 для любых

КДЧ х0,

...,

хп, х

выполнялось

Рз ( 1 ) (х0 * . . . * Хп, X) ~

О,

если

Рз (rc ,

v,, *) = 1,

п — 2,

если

Рз (Xi, xi+1,

х) = 2 для всех г таких, что

~ <

0 < г < п — I ,

/,

если

0 < / < д

—2, Р з ( х , + 1 ,

х / + 2 , х ) = 1 и

при

0

Рз(х А ,

x k

+ u

х) =

2.

Пусть

теперь 5 =*= Хо * .. . * хп — положительное

дро­

бление, х — КДЧ. Тогда,

очевидно, Рз*1) перерабатывает

слово S, х

в натуральное

число, заключенное

между 0 и

п — 2. Предположим

далее, что х е х0

Д

хп.

а) Если

Рз(х0 , х ь х) =

1, то P3*1)(S,

х) == 0. В

рас­

сматриваемом случае х <

х ь

Следовательно,

подавно

288

КОНСТРУКТИВНЫЕ ФУНКЦИИ

[ГЛ. 5

и

Кл

(Ф (V, (х, т)))

<х<К"(Ф

(Y2 (х,

т))) *);

5)

если

последовательность

W

такова,

что

осущест­

вимы

алгорифмы

Ки

Х2

типа

(Ж-+Ж),

для

которых

при

всяком

п

выполняется

Г ( Т ( и ) ) е ? ( 1 ,

(п)),

r ( ¥ ( n ) ) e f ( A 2 ( a ) ) ,

то

алгорифм Ф арифметически

полн

(т. е.

применим

к

любому

натуральному

числу)

и осуществимы

алго­

рифмы

Х'и

^2

типа (Ж —* Ж)

такие, что при

любом п

Кл(Ф(п))

=

КП(ф(1[(п))),

Кп

(Ф

(«))

=

Кл

(Ф

(Я,2

(П))).

(Другими

словами,

для

всякого

интервала последова­

Будем для краткости обозначать левый и правый

концы интервала

W(п) через гп

и s„.

Положим

Пусть уже построена система рациональных интер­

валов

Кп-

Систему

Kn+i

строим

следующим

образом.

Рассмотрим

интервал x F ( n + l ) .

Возможны

случаи***):

1)

Ч ' ( / г + 1)

не

имеет

общих

внутренних

точек

с ин­

тервалами

системы Кп',

2) W(n-\-l)

включен

в один

из

интервалов

систе­

мы

Кп\,

*) Напомним, что алгорифмы КП

и Кл

перерабатывают вся­

кий

промежуток соответственно в его правый и левый

концы.

**) Более строгое доказательство можно

найти

в работе Ц е й-

т и н а [5].

***) Здесь и в дальнейшем следует

иметь в виду, что отноше­

ния

порядка и равенства рациональных чисел разрешимы.

СТРУКТУРА КОНСТРУКТИВНЫХ ФУНКЦИИ

239

3)

l F ( n + l )

имеет

общие

внутренние

точки

с

ин­

тервалами системы Кп,

но не включен

ни

в один

из

ин­

тервалов Кп-

В первом

и втором

случаях

соответственно

полагаем

К

К

*

Г

V 7

Г п + 1

~*~ S n + l

*

+ S r c + i

Art+i — А/г* 'n+l

V

2

2"

^

"+1

И

Кп+\ =г= Яя-

В

третьем

случае

пусть/о^Лг+ь ^„+i^=s «+i и

• • •

tpn — все

различные концы интервалов системы

Кп>

попавшие в интервал

Ч?(п-\- 1) и занумерованные

в по­

рядке возрастания

так, что

А) = fn+i < t\

<

t2

<

...

<

<

sn+x

=

^prt +i.

Пусть

далее

tix

V

^2

V U2+\,

/ i , V

— те

из

интервалов t t \/t i + x

( 0 ^ г <[/)„),

которые

не

включены

в

интервалы

системы

Кп

(отметим,

что таких

интерва­

лов может и не быть).

Систему

Кп+\

определяем

при­

соединением этих интервалов к системе Кп,

т. е.

Kn+i =т= Кп. * u x

V

t i l

+ x

* ti2 v

t{2+i

* . . . * tct

v

ti[+i

(и

A^t+i =?= Л'п,

если

все

интервалы

tt

у

( 0 < i < P n )

можно построить алгорифм, перерабатывающий

вся­

кое п в систему Кп-

Нетрудно убедиться (индукцией по п), что при

лю­

бом п

мере в один из интервалов ^ ( О ) ,

Чг (п).

Покажем теперь, что

(3) для каждого х и п таких, что

н е ? ( п ) ,

можно

найти

интервалы

ах

V bx,

а2 V Ь2,

входящие

в

Кп,

такие, что Ьх =

а2

и ах

<с х <с Ь2.

очевидно.

Действительно,

при

п = 0

утверждение

Пусть мы умеем находить требуемые

интервалы

для

всех г и

k таких,

что

k

п

и г Е

?

(fc).

Пусть

х е=

e l F ( r t +

1). При переходе

от

системы

Кп к

Кп+\

могли

представиться случаи

1) — 3) .

Рассмотрим

эти

случаи.