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

242

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

ФУНКЦИИ

[ГЛ. 5

Мы

будем

использовать

следующий

сокращенный

оборот

речи. Пусть F — последовательность

КФ,

причем

при каждом

п Рп

есть КФ некоторого типа. В такой

си­

туации мы будем называть F последовательностью

КФ

данного типа.

Для

всякой

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

последова­

Л е м м а

3.

тельности КФ можно построить КФ, являющуюся

ее

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

Пусть F — согласованная

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

по­

следовательность КФ. Обозначим через Жх

множество

натуральных

чисел таких, что

п е Мх

=

IF {п,

х).

Очевидно, множества

Жх

перечислимы. Построим

ал­

горифм 91 так, чтобы при всяком х алгорифм

91ж

был

стройным

алгорифмом, перечисляющим

Жх

(теорема 7

§ 3 гл.

1). Построим

далее

алгорифм /

так,

чтобы

f{x)~F{%{x,

0),

х).

Покажем, что / и есть искомая конструктивная

функ­

ция.

m,

х

\F(m,

х).

1) Пусть

при

некоторых

Тогда

т<^Мх.

Следовательно, !21(х, 0), и так как

91 (х,

0)^ЖХ,

то \F(%(x,

0),

х),

т. е. lf(x).

Ввиду

согласованности

по­

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

F получаем

откуда

f(x)

= F{%(x,

0), x) =

F(m,

х),

f(x)

=

F(m,

х).

2) Пусть

\f(x).

Тогда

!91(х,

0)

и 91 (х, 0)

есть

нату­

ральное число, причем

f(x)

=

F{%(x,

0),

х).

Для

завершения

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

осталось

показать,

что / есть КФ. Пусть при некотором х lf(x)

и

у

— х.

Тогда !/7(91(л:, 0), х).

Отсюда,

так

как F — последова­

тельность КФ, следует, что !F(9I(x, 0), у).

Следова­

тельно,

Ш(х,

0)^ЖУ.

Поэтому

\F(%(y,

0), у),

т. е.

\f(y).

Далее, ввиду согласованности

F,

F{%{y,

0), y) =

F(%{x,

0),

0) =

0

)

,

х).

СТРУКТУРА

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

ФУНКЦИЙ

243

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

f{x)

—

f{y),

чем

и

заканчивается

дока­

зательство.

Конструктивную

функцию

ср на­

О п р е д е л е н и е

5.

зовем

угловой,

если

можно

найти

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

числа

r\,

г2,

г3, г4 ,

г5 ,

г6

такие, что гх <. г2

и

при

всяком

х

1)

если

т1 <С х <С г2, то

<Q(x) = r4-\x

— r3\

+ r5-x

+

r6;

2)

алгорифм

ф

применим

к

х только

в

том

случае,

когда

r\ <

х <

г2 .

Интервал r\ V г2

будем

называть носителем

угловой

функции ф, а значения функции г4-

\х

— г3\-\-

г5-х&

-\- г5

на

концах

r\ V г2

— пре­

У,

дельными

значениями

ф

в точках Т\ и г2 .

сле­

h

Вполне

очевидна

1

N .

дующая

X

1

N .

Л е м м а

4.

Для

вся­

tf

1

X

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

чисел

t2

т

1

!

-

г\,

r2,

r3, tu

t2,

U

таких,

что

Г\ <

г3

<; г2 ,

можно

п

построить

угловую

функ­

цию

с

носителем

г\ V

г2 ,

Рис.

11.

предельными

значениями

t\, t2 в точках

ги г2,

принимающую

в

точке

г3

значение,

равное

t3

(рис.

11).

положим

В

самом деле,

Аз — г,

k\ +

k2

2

'

5

'

2

'

и

рассмотрим

К Ф Ф' такую,

что

q>'(*"l) =

' l .

244

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

[ГЛ. 5

Далее,

пользуясь

алгорифмом

sgn,

нетрудно

по­

строить КФ ч; такую, что

(ср. пример

г)

§ 1)

1)

если

lty(x),

то $(х)

=

х;

2)

!г|з (х)

=

х е

г,

V

г2-

Пользуясь теоремой композиции алгорифмов, по­

строим

алгорифм

ф так, что

ф(л;)~ф' (•ф(лг)).

Очевидно, ф является искомой угловой

функцией.

О п р е д е л е н и е

6.

КФ

ф назовем

псевдополиго­

нальной,

если

ф является

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

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

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

угловых

функций.

О п р е д е л е н и е

7.

КФ

ф назовем

непустой,

если

ф

не

является

нигде

не

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

функцией

(т.

е.

-]V*(-|!<p (*))).

Сформулируем

теперь

аппроксимационную

теорему

Ц е й т и н а

[5].

Для

всякой

непустой

КФ f и

всякого

Т е о р е м а

1.

п

можно

построить

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

функцию

ц>

так, что при

любом

КДЧ

х,

если \f(x),

то !ф(х)

и

число в рациональное число, причем

при любых

k

и х, если х принадлежит сегменту rkAsh

и \f(x),

то

| / ( х ) - т ( * ) К 2 - " - '

СТРУКТУРА

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

ФУНКЦИЙ

245

(т. е. осуществимы алгорифмы,

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

всякий х, для которого

lf(x),

в

искомые

натураль­

ные числа *) ) .

(7) Для всякого т

можно

найти

натуральные

числа к

и / так, что

и

sk —

гт

X{2-k)

=

rk,

( )

X(2-k+\)

=

sk.

ности Ф.

k

через k\ и k2 обозначим

Для

каждого натурального

натуральные числа такие, что

skl = Я

(k),

rk^X{k).

(Такие

числа можно найти ввиду

(7).)

Назовем число k числом первого типа, если

(9)

| T ( f t , ) - T ( f e 2 ) | < 2 - B .

Число k назовем числом второго типа, если

(10)

\r(k1)-x(k2)\>2-n**).

(11)

Если k — число

1-го типа, то

f{k==zfk—

T(fei) +

T(ft2 )

(12)

Если k — число 2-го типа, то

ti

=

r(k\),

Очевидно,

(13)

если A(0 = 4/) .

то

t\ —

t)

и

t\=t).

Кроме того,

ввиду (9) — (12), независимо от

типа к,

(14)

K - T ( f c i ) | < 2 - " - !

и

(15)

\ А - х ( Ы \ ^ Т п - \

Сопоставим

теперь каждому

k

две угловые

функции

\\ и

\\

следующим

образом

(построение

этих

функций

может быть выполнено с помощью леммы 4).

Если

k — число

1-го

типа,

то

f\=f\

и f\

является

угловой

функцией с

носителем

rf e l

v skl,

принимающей

1

1

1

A(2k,hrhj

Ф1к,) \'Mhrie

Ф(кг)

Рис.

12.

в

точке

X(k)

значение

4 =

4

и предельные

значения

tlk,,

tlk2+i

в

точках

rkl

и

sk2

(рис.

12). (Очевидно,

A(2-fe,) =

rf c l

и Я (2 - / г 2 +

l ) = s f t

2 . )

Если

& — число

2-ГО типа,

то f[

имеет

носитель

r f t l V M & ) >

линейна на этом интервале

и принимает пре-

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

247

дельные значения t \ k , t\ на его концах,

f2k имеет носи­

тель A,(&)vs &2 >

линейна на этом интервале и принимает

на его концах

предельные

значения t\,

t\.k2+i (рис. 13).

У

i

>

>-t

t

1

l

i

1

1

i

1

i

(16)

если k — число

1-го типа,

то из rki

<xs^ski

следует lf[(x) и

\f(x)-flk(x)\<\f(x)-x(kl)\

+

\x(kl)-fi(x)\^

лигональную

функцию

ф,

являющуюся

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

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

F. Покажем, что ф — искомая

функ­

ция. Пусть при

некотором х

\f(x).

Пользуясь

(6),

най­

дем k таким

образом, что

rk,<x< sfe2.

Рассмотрим

случаи.

1) k — число

1-го типа. Тогда всюду на rki V

s b

Ф(0 =

Д(0 -

Предположим,

что

| < р ( * ) - / ( * ) | > 2 - я .

Тогда

ввиду

(16) не

выполняется

ни rkl

<x^.skl,

ни

skl ^.x<ski,

что невозможно. Следовательно,

| Ф ( * ) - / ( * ) | < 2 " \

2)

k—число

2-го типа. Предположим, что х =

X(k).

Тогда, ввиду

(5),

и

1 / ( * ) - т ( * , Ж 2 - я - 1

откуда

| т ( А , ) - т ( А 2 ) | < 2 " " ,

что противоречит

(10). Следовательно, хф%(к),

и

мы

можем

(используя

принцип Маркова)

указать тот из ин­

тервалов

0 ( & i ) ,

Ф(&г),

которому

принадлежит

х.

Пусть,

например,

1 б Ф ( ^ ) .

Тогда

\f[(x),

<p(x) = flk(x)

и со­

гласно

(17)

| / ( * ) - Ф ( * ) | < 2 - я .

Таким образом, если \f(x),

то 1ф(х) и

260

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

[гл. s

(23)

0<ak

, m

- X k < 2 - m ,

(24)

0 <

ук

-

bk, т <

2~т,

где через а&,m , Ьи,т

обозначены

левый

и правый

концы

интервала

(5 (k,

т).

Пусть

/ 2 ,

h — алгорифмы,

введенные

в п.

1 § 3 гл. 1

(эти алгорифмы осуществляют взаимно однозначное ото­

бражение множества натуральных чисел на множество

пар натуральных чисел, т. е. для любой пары т, k

можно

найти

i

так,

что 12 (/) =т= т,

Ц (/) =?= я). С

помощью

алгорифмов

it,

l\

объединим

интервалы

вида

(5 (k,

I)

в одну последовательность, т. е. построим алгорифм

Т

такой, что

4^(m)~S(/ 2 (m),

l\(m)).

Ввиду

(23) — (24)

для

всякого

х,

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

Wiik),

можно

найти

т

так, что

x^(&k(m).

(Действи­

тельно,

в

качестве

т

можно

взять,

например,

число

max(G {х — xk),

G(yk

— х)).)

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

для

всякого

эс

таких,

что х е

Wi (k),

можно

найти /, при котором

х и k

j ; e f

(I).

Из

этого

замечания также следует, что для

всякого

т

можно

найти

/ так,

что

концы

интервала

1 F(m)

принадлежат X F(/).

Построим алгорифм f i так, чтобы

т1

(т) с- т, (/'

(т)).

Обозначим

через

ат, Бт концы

интервала W(m).

Сде­

ланные

выше

замечания,

определение

алгорифма

х{

и

(21) — (22)

позволяют

сформулировать

следующие

свой­

ства W и

f|:

(25)

для

любого

и х,

если lf(x)

и х

принадлежит

сег­

менту

ak

A

bh,

то

\f{x)-x1(k)\<2-n-];

(26)

для

всякого х

такого, что

lf(x),

можно

найти

k,

при котором

x^W(k);

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

ФУНКЦИЙ

251

(27) для всякого k

можно найти / так, что

а*

и

ft*

Искомый алгорифм Ф получаем теперь применением

леммы 2 к алгорифму х ¥. При

этом,

ввиду (27),

будет

Таким образом, Ф действительно обладает

свойствами

(4) и (6) — (7). Алгорифм

т построим

следующим

обра­

зом. Пусть к — алгорифм, фигурирующий

в

утвержде­

нии 3) леммы 2. В рассматриваемом

случае

к арифме­

тически полн и при всяком

k

Ф (&)<=¥ (А (£)).

Алгорифм т

строим

как

композицию

алгорифмов к

и т{:

x(k)

~ т ,

(k(k)).

Ввиду

(25)

для Ф и т

выполняется

(5), чем и

закан­

чивается

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

Предлагаем

читателю

убедиться,

что

условие

непу­

такой, что для любой КФ /

F^

есть

псевдополиго­

нальная

функция,

причем

при

всяком

х,

если

\f(x),

то

\FiB(x)

и

x)-f{x)\<l.

3. О п р е д е л е н и е

8.

Всюду

определенную

КФ f

назовем

полной полигональной

функцией,

если

осуще­

ствимо

рациональное

дробление

г0

* . . . * г п

такое,

что:

1) f линейна

при

х s=: г0

и

х ^

гп, причем имеет рацио­

нальные

угловые

коэффициенты;

2)

f

линейна

на

каж­

дом сегменте

r{ A ri+l

(О ^

i sg; п — I)

и

принимает

ра­

циональные

значения

в

точках

г4 (0 ^

i ^

п).

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

на

всяком

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

сегменте,

не содержащем точек ru

f

является

линейной

функцией

с рациональными

коэффициентами.

О п р е д е л е н и е

9.

Пусть

F —

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

всюду

определенных

КФ, f — КФ. Будем

говорить,

что f

является

пределом

F (или

что F

сходится

к / ) , и

писать

f = LimFn,

если

осуществим

алгорифм

W

такой,

что

rt-»oe