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

§ II

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

165

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

Пусть

Х\ >

х2.

Тогда

по

по­

строению алгорифма G (лемма 8 § 3 гл. 2)

(1)

Х1-х2>2-а(х'-х>\

Пусть б,, б2

— регуляторы сходимости соответственно at

и а2

к

Хх и

х2.

произвольное

/ такое,

что

Рассмотрим

i >

max

(б! (G (хх

— х2)

+

1), б2 (G (л:, — д;2) - f

1),

т).

Тогда

(2)

\al(D-xl\<2-G{x^)-\

(3)

I ог (о — ж3

к

г - 0

^ - ^ - 1 .

Из

(1) — (3)

получаем

<*i (0 — а2

(0

>

О,

что

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

условию.

С л е д с т в и е

1.

Если

ПДЧ

а,

сходится

к

х

и

осу­

ществимо m такое,

что при

любом

п^т

а(п)^.

у, то

х =g: у.

(Аналогично,

если

при

п^т

<х(п)^у,

то

х >

у.)

Нетрудно

также

доказать

следующее

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

Т е о р е м а

5.

Если

ПДЧ

cci,

сс2

сходятся

к

одному и

тому же КДЧ

и ПДЧ

а

такова,

что при любом п

min (ctj (п),

а2 (п)) ^

а (п)

^

max (а, (п),

щ

(п)),

то а сходится

к этому же

КДЧ.

О п р е д е л е н и е

8.

Пусть а — ПДЧ.

1)

Назовем

а

возрастающей

(неубывающей),

если

при

любом

п

а(п+

1) >

а(п)

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

а(п

- f 1 ) ^

а

( л ) ) .

2)

Назовем

а

убывающей

(невозрастающей),

если

при

любом

п

а(п

+

1) <

а(п)

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

а ( п + 1 )

^ а ( ' 0 ) -

3)

Назовем,

а

монотонной,

если

а

является

неубы­

вающей

или

невозрастающей

ПДЧ.

166

КОНСТРУКТИВНАЯ

СХОДИМОСТЬ

[ГЛ. 3

Т е о р е м а

6.

Если

неубывающая

(невозрастающая)

ПДЧ

а сходится

к КДЧ х, то для любого

п

а(п)^.х

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

а ( п ) ^ х ) .

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

Пусть

при

некотором п0

(4)

х<а{щ).

Тогда

при

i^n0

(5)

х < а (n0) ^

а (г).

Отсюда по следствию

1 получаем

что невозможно.

х < а (n0) ^

х,

р является

Л е м м а 1. Пусть

алгорифм

регулятором

фундаментальности ПДЧ

а.

Тогда

если

а

сходится к

КДЧ

х, то при любом

р(/г)

|а(/г)

— * K 2 " f t .

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

Пусть

k,

г ^ р ( п ) .

Тогда

данной ПДЧ.

р и р' — ПНЧ

Т е о р е м а 7. Пусть

такие,

что при

любом

п р'(«) ==р(л + 1).

Тогда

1)

если

р есть регулятор

фундаментальности

ПДЧ а

и а сходится к некоторому

КДЧ,

то р'

есть

регулятор

сходимости

а к этому

КДЧ;

а к некоторому

2)

если

р есть регулятор

сходимости

КДЧ,

то р' является

регулятором

фундаментальности

а.

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

1)

Пусть р — регулятор

фун­

даментальности ПДЧ а

и а

сходится к КДЧ х.

Согласно

ОСНОВНЫЕ

ОПРЕДЕЛЕНИЯ

167

лемме 1 при любом я и А ^

8(п)

|a(Jfe)

— * | < 2 ~ \

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

если

i ^

6'(n)

== P(n +

1),

то

| a ( 0 - x | < 2 " n _ 1

<2~п,

т. е. 8' является регулятором сходимости

а

к

х.

2) Пусть 6 — регулятор сходимости а к х.

Фиксируем

произвольное п. При i, j ^

S'(n)

IJC — a (О

I < 2 - " -

1 ,

откуда

\x-a(j)\<2-n-\

| a ( / ) - a ( i ) | < 2 - " ,

что и требуется.

Т е о р е м а 8. Для любого

КДЧ

х ПРЧ

х

сходится

к х.

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

Пусть

Вж —алгорифм та­

кой, что при любом п

(л) =

£(л +

1).

Тогда при любых i, / ^ Вж (п)

(7)

U ( / ) - x ( i ) | < 2 - " - ' .

Фиксируем /. Ввиду леммы 4

§

4 гл.

2

(7) можно

записать так:

U - * ( / ) l ( 0 < 2 - " - 1 .

I

1

Отсюда по теореме 11 § 3 гл. 2 следует, что

\x

— x(j)

| < 2 ~ я ~ '

< 2 ~ " .

$

2]

ПОЛНОТА КОНСТРУКТИВНОГО КОНТИНУУМА

169

§

2.

Полнота конструктивного континуума. Теорема

о вложенных сегментах

1. Нам будут полезны следующие леммы.

Л е м м а 1. Для

любого

КД Ч х при любом

п

\х

—

х(х(п))\^2~п.

Л е м м а 2. Можно построить

алгорифмы

D~ и

D+

типа

такие, что

для

любого

КДЧ

х и

любого п

D~(х,

n)<x<D+

(х,

п)

и

D+ (х,

п) — D~ (х, п) <

2~п.

D+ (х,

п) ~ х (х (п +

3)) +

2 " " - 2 .

Очевидно,

D~

и

D+

являются

алгорифмами

типа

({Ф X Щ -> 9>) и для любых х, п

D+

(х, п) -

D~ (х, п) =

2~п~1

< 2~п.

Далее ввиду леммы 1

х(х (п +

3)) - 2~п~3 <

х ^

х (х (п +

3)) +

2~"~3 .

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

D~(х,

n)<x<D+

{х,

п).

Алгорифмы D~ и D+ обладают требуемыми свой­

ствами.

Имеет место следующая важная

Т е о р е м а

1 (теорема

о

полноте

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

континуума).

Можно

построить

алгорифмы

Игр и

НтМ

170

КОНСТРУКТИВНАЯ

с х о д и м о с т ь

[ГЛ. 3

такие,

что для

любых

ПДЧ

а

и

ПНЧ

р, если

р—

регу­

лятор

фундаментальности

а, то

£аЗ, 6РЗ

1)

алгорифм

lim

перерабатывает

слово

в КДЧ;

^

2)

алгорифм

П т д а

является

регулятором

сходимо­

сти а к КДЧ

lim

( £ов,

£РЗ).

(Таким

образом,

для

каждой

фундаментальной

по­

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

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

действительных

чисел

можно

построить

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

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

число,

к которому

сходится

эта

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

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

Используя теоремы

сочетания

алгорифмов

и

теорему

об

универсальном

алгорифме,

можно построить алгорифмы 91', 2Г2,

2Г3

такие, что для

любой ПДЧ а,

ПНЧ

р

и любого п

91'(6РЗ. n)~max ( P (0),

p(n +

1)),

да

Я2 (саЗ,

№,n)~a(W(m,n)),

?13(£аЗ, £ рЗ , « ) ~ £ Г ( 2 1 2 ( 6 с в ,

£РЗ,«), я +

2).

Построим далее алгорифмы lim и lim( 1 ) такие, что

Нт(£аЗ, ЕРЗ)^=Е«£аз.

Е Р З З О Е И З

(напомним,

что

Id — алгорифм

такой,

что

Ы(л) = «

при любом

«),

НтОЧЕРЗ, п)са

р ( л +

О-

Покажем, что эти алгорифмы обладают требуемыми

свойствами.

р — ПНЧ,

Пусть а — П Д Ч

и

являющаяся

регулято­

ром фундаментальности

а.

91](ЕРЗ> п)

Тогда, очевидно, при любом п

е с

т ь

нату­

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

212(£аЗ,

£ Р З ,

га)

—конструктивное дей­

ствительное

число

и

913(£аЗ, £РЗ

» п ) — р а ц и о н а л ь н о е

ства эти

числа соответственно через kn, ап и гп.

Очевидно, при любых m, п

U)

& w > p ( n + l ) ,

и если m

я, то

§ 2]

ПОЛНОТА КОНСТРУКТИВНОГО КОНТИНУУМА

171

Следовательно, при т ^

п выполняется

(2)

\ a m - a n \ =

\a(km)~a{kn)\<2-n-\

Далее

по построению алгорифма D~

(3)

\гя-ап\<

2 - " - 2 ,

(4)

I гт -

Из (2)—(4) следует, что при т^п

(5)

I/•„-/•„

| < 2"".

то

х (п) = Id (п) ~ п,

х(х(п)) = гп.

Тогда по лемме 1

(6)

1 Г . И - Х К 2 - 1 .

Ввиду (3)

(7)

к я + 1 - а ( * я + 1 ) | < 2 - я - 3 .

Ввиду (1) при любом

i ^ k n + l

\a(i)-a(kn+l)\<2-n-2.

Следовательно, при любом

i ^ k n + l

(8)

| а (г) -

х | < 2 -

" - 1

+ 2~п~2

+ 2~" _ 3 < 2~п.

Построим

алгорифм

914 такой, что