книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

232

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

ФУНКЦИИ

[ГЛ. 5

О п р е д е л е н и е

11.

1)

П-оператором

назовем

алгорифм,

пе­

реводящий

псевдочисла

в

псевдочисла

так,

что

равные

псевдочисла

переводятся

в

равные

псевдочисла.

2)

П-оператор

назовем

продолжением

функции

f,

если

при

любом

КДЧ

х

(из

ОД 1)

и любом псевдочисле

q таких, что х

= q,

выполняется

} (х) =

W (<?).

Почти

очевидна

Т е о р е м а

8.

Для

всякой равномерно

непрерывной

функции

можно построить П-оператор,

являющийся

ее

продолжением.

Для равномерно непрерывной функции / обозначим

через J

продолжающий ее Я-оператор.

Имеет

место следующая

теорема

(здесь и

ниже

мы

формули­

Т е о р е м а

9. ( Л и ф ш и ц

[4]). Для

каждой

равномерно

непре­

рывной

функции

f можно

построить

псевдочисло

q

(из

0Д1) так,

что f(q)

равно

точной верхней

грани

f на

0 Д 1 .

В силу уже упоминавшихся результатов § 2

гл.

8

для

некото­

рых функций построенное

согласно теореме 9 псевдочисло

заведомо

теорема, представляющая собой конструктивную

версию результатов

Г ж е г о р ч и к а

[2] и Л а к о м б а

[4]*).

Т е о р е м а

10.

Пусть

f — равномерно

непрерывная

функция,

КДЧ

х — ее точная

верхняя

грань

на 0 Д 1 . Если

псевдочисло

q та­

ково,

что

2)

можно

указать

рациональную

окрестность

точки

q такую,

что

для

всех

псевдочисел

q\

из этой

окрестности,

отличных

от q,

имеет место

f(qi) Ф

х,

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

КДЧ

у, равное

q.

Теорема

10 показывает, таким образом, что изолированный

экс­

тремум равномерно непрерывной функции вычислим.

Для

читателя,

придерживающегося

традиционной

ориентации,

заметим,

что

из первоначального варианта теоремы 10

(сформули­

рованного применительно к классическому континууму)

легко

сле­

дует вычислимость корней полиномов с вычислимыми

коэффициен­

тами**) .

4. Введенное в предыдущем пункте понятие /7-оператора

отли­

чается

от

понятия

всюду

определенной

конструктивной

функции

*) Гжегорчик и Лакомб используют

традиционное понятие дей­

ствительного

числа. В

работе

Л а к о м б а

[4]

приведена

также

про­

стая

и

исчерпывающая

характеристика

тех

множеств

действитель­

зультаты также могут быть

интерпретированы

конструктивно,

но

мы не имеем возможности углубляться в этот вопрос.

**) Заметим попутно, что основная теорема

алгебры

имеет

ме­

сто в следующей, гораздо более сильной формулировке

(очевидное

определение конструктивных

комплексных чисел

(ККЧ)

предостав-

СВОЙСТВА

НЕПРЕРЫВНОСТИ

233

только

выбором

другой

числовой

системы (псевдочисел

вместо

К Д Ч ) . Аналогично примем

К-оператором

называется

алгорифм,

О п р е д е л е н и е

12.

1)

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

квазичисла

в квазичисла

так, что равные

квази­

числа

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

в

равные

квазичисла.

2)

К-оператор

W

назовем

продолжением

функции

/, если при

любом

КДЧ х и

любом

квазичисле

р таких,

что х = р,

выполняется

f{x)=V(p).

П- и К-операторы могут наряду с конструктивными

функциями

рассматриваться

как уточнения

интуитивной

концепции

вычислимой

порождается

некоторой конструктивной функцией.)

В этом

пункте мы сформулируем некоторые результаты

автора

( К у ш н е р

[4]—[5]; [11]) о К- и Л-операторах.

Сравнительный объем понятий конструктивной функции

и К- и

ция», как и выше, используется в качестве сокращения

термина

«всюду

определенная конструктивная

функция».)

Т е о р е м а

11.

1)

Для

каждой

функции

можно

построить

К-оператор, являющийся

ее

продолжением.

' 2)

Можно

построить

К-оператор,

не

являющийся

продолжением

никакой

функции.

Можно

построить

функцию,

для

которой

не­

Т е о р е м а

12.

1)

возможен

продолжающий

ее

П-оператор.

2)

Можно

построить

П-оператор,

не

являющийся

продолжением

никакой

функции.

Заметим, что

свойством,

указанным

в утверждении

1) теоре­

мы 12, обладает, например, эффективно

неравномерно

непрерывная

функция,

построенная

в

доказательстве

теоремы 3 § 2 гл. 8.

По

аналогии

с

определением 2

п. 1

можно ввести

понятие

не­

всякий

полином

Р„ (t) — a0tn +

...

+

ап

(где at

— ККЧ

и

а0 Ф

0)

в список ККЧ

zi,

2„

так,

что

Рп

(t)

— ай-(t

— Zi)

.. .• (t —

z„)

(см. О р е в

к о

в

[3],

в а н

д е р

К о р п у т

[1], Г у д с т е й н

[3]—[4],

Ш п е к е р

[3]).

*)

Для

читателя,

не заинтересованного в конструктивной

специ­

дящихся

последовательностей рациональных

чисел,

во

втором

(Л-операторы)—коды вычислимых, сходящихся (в

традиционном

смысле

этого

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

рациональных

чисел.

(В обоих случаях дополнительно требуется, чтобы оператор

сохра­

нял некоторое

естественное отношение равенства.\

Обозначим через Ж~ множество квазичисел

таких, что р е Ж~

тогда и только тогда, когда ПРЧ £ не возрастает

и

~] ~13«V//' (i, j> п => р (i) = р

(/))

Ясно, что

любое р е Ж'

не может не равняться некоторому

рациональному

числу.

Следующее

определение

мы сформулируем для краткости лишь

ности

вводится

совершенно

аналогично.

О п р е д е л е н и е

13.

П-оператор

Ч

назовем

почти

непрерыв­

ным,

если

можно

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

91, перерабатывающий

вся­

кое слово

вида

q, п

(q — псевдочисло,

п — натуральное

число)

в

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

квазичисло,

принадлежащее

Ж~

и такое,

что

при

любом

псевдочисле

qi,

удовлетворяющем

неравенству

данной точке

q

при данном

е =

2~п , эффективно

находится в

виде

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

квазичисла

из

Ж'.)

Т е о р е м а

13. 1) Всякий

К-оператор

почти

непрерывен.

2) Всякий

П-оператор почти

непрерывен.

Заметим, что доказательство теоремы 13 опирается на теорему

Клини о неподвижной точке

(см. К л и н и

[4; § 66], М а л ь ц е в

[1])

Например, в работе

К у ш н е р а [5]

указан пример /(-оператора

(почти

непрерывного

в силу теоремы

13), принимающего на еди­

ничном

сегменте в точности два значения (ср. § 4 гл. 5). Для Я-опе­

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

235

Согласно

этой теореме (см. Ц е й т и н

[5])

всякая

непу­

стая (т.

е. определенная хотя бы в

одной

точке)

кон­

на нем не более одной угловой

точки (рис.

10).

^ \

Таким

образом,

область

у

\

определения

псевдополигональ­

ной функции

получается

объ­

единением

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

рациональных

интервалов. В

х

п. 3 § 3 гл.

9

будет показано,

что область

определения

про­

извольной

конструктивной

Рис.

10.

функции может иметь

гораздо

ными с точки зрения традиционного

анализа свойства­

ми— например, построенная

в § 2 гл. 8 всюду опреде­

ленная и неограниченная на

сегменте

0 Л 1 функция яв­

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) .

Рассмотрим

эти

случаи.

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

ФУНКЦИЙ

241

ким образом,

что !<D(&i), !Ф(£2 ) и

s'k, — r'k'

s k ~ r

k , -

(Через

s^.

мы

обозначаем

левый и правый

концы

ин­

тервала

Ф(0

(в

случае, если

!Ф(0-)

Пусть !Ф(£).

По­

нием

3), найдем / такое, что Ф(&)

включен

в W(l).

Если

rt<r'k,

то r^ex F(Z). Если

же

/'/ =

^ ,

то

по

условиям

утверждения

5)

мы

можем

найти т,

при

котором

г £ е

е Ч ^ т ) . Следовательно,

всегда

можно

найти/такое,

что

f j e f ( l ) .

Тогда

в силу

утверждения

4)

можно

найти

/ь

h

так,

что !<D(/i),

!Ф(/2 )

и

S:

=

rr.,

Г'п < Г'* < SU-

Отсюда и из утверждения 2) леммы без труда сле­

дует,

что

r'k — s'/-

Таким образом,

в качестве

k\

можно

взять

/ i . Лемма

доказана.

Алгорифм

F

назовем

после­

2.

О п р е д е л е н и е

2.

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

конструктивных

функций

(или,

короче,

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

КФ),

если

при

всяком

п

алго­

рифм

Рп

является

конструктивной

функцией*).

О п р е д е л е н и е

3.

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

конструк­

тивных

функций

F назовем

согласованной,

если

при

вся­

ких п,

ш,

х

таких,

что \F(n,

х)

и \F(m,

х),

выполняется

F(n,

х) =

F(m,

х).

КФ

f назовем

объединением

со­

О п р е д е л е н и е

4.

гласованной

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

КФ F,

если

1)

при

всяком

m u x ,

если

\F(m,

х), то \f(x)

и

f(x)

=

F(m,

х);

2)

при

всяком

х

КФ f

определена

в

точке

х

только

в

том

случае,

когда

осуществимо

ш,

для

которого

\F(m,

х).