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

Ввиду

леммы 3, алгорифм

mod

является алгорифмом

типа

з>

(2)^2)).

Непосредственно

из

определений алгорифмов + , —

з> з>

и mod

устанавливается

следующая

3>

Л е м м а

4. Для

любых

КДЧ

х, у и любого я

1)

+(х,

У) (п) ~х(п)-\-у

(я);

2)

~ (х,

у) (п) =

х (я) — г/ (я);

i

I

3)

mod (х) (я) == | х(я)

L ;

з>

~

часто

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

записи

x-j-y,

х — у и | х L ,

причем

3 )

3

)

в тех

случаях,

когда это

не

ведет

к

недоразумениям,

индекс «£Z>» будет опускаться.

3.

Операции

умножения,

деления, max,

min.

О п р е-

3> 3>

д е л е н и е

3.

Будем

говорить, что ПРЧ

а является про­

изведением

ПРЧ

ai, ос2> если

при всех

п

a (п) =

а,

(п)

• а2

(п).

Л е м м а

5. Пусть

ПРЧ

а

является

произведением

ПРЧ

щ, а2 ,

ПНЧ

р ь

р2

являются

регуляторами

фунда­

ментальности

ai

и

а2 .

Пусть

далее

k —

натуральное

число

и р — ПН Ч такие, что при

любом

п

I «1 (п) I <

2\

и

| а2

(я) | <

2*

р ( я ) - т а х

(р, (п + k+

1), р2 (я + k+

1)).

да

7огс?а

р есть

регулятор

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

ПРЧ

ц,

АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД КДЧ

153

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

Фиксируем

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

п.

Пусть i, j^fi

(п).

Тогда

I а (0 — а (/) | = | а, (г) • а2

(i) — а, (/) • а2

(/) | =

= | а, (г) • (а2

(г) — а2

(/)) + а2 (/) • (а, (/) — а, (/)) | <

<1 «1 (О I • I а2

(/) -

а2 (/) | + | а2(/) | • | а, (/) -

а, (/) | <

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

< 2ft • 2~k~n~l

-(- 2k • 2~k~n~1

2~п

Л е м м а

6. Можно

построить

алгорифм

G+ типа

(2D -* Ж) такой, что для любого х и п

1)

\х\<2а+м;

2)

| х ( я ) | < 2 0 + < * > .

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

Построим

алгорифм

%\ такой,

что для любого рационального г

Ям (r) = \ L

\

(обозначения г и г введены на

стр. 121; _г обозначает

«числитель»

г).

При любом г

(4)

| г | < 2 ^ < " .

Очевидно, Я2 является

алгорифмом

типа

(3)-+&>)

и,

ввиду леммы 4,

(5)

Х2(х)>\х\.

Построим

алгорифм

G' так, что

G,(x)^X]

(%2(х)).

Этот

алгорифм является алгорифмом

типа

(2D —> Ж)

и,

ввиду

(4) — (5), при любом х

(6)

| х | < 2 ° ' М

Искомый

алгорифм

G+ строим

теперь так, чтобы вы­

полнялось

G + (л:) =

max (G' (х), Л, (х (0)),

. . . ,

А,, (х (х (0)))).

&с

-

-

154

КОНСТРУКТИВНЫЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА

ГГЛ. 2

Если же п > х(0), то

|| х (п) | - 1 х (х (0)) || <

| * (л) - * (х (0)) | < 1.

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

\х{п)\<Х2(х)<2а'Ю

< 2 0 + Ч

Построим теперь (пользуясь леммой

1) алгорифмы

умн*1' и рег(> такие, что для любых КДЧ

х

и у

умн( 1 ) (л:, у, п) ~ х(п)

-у

(п),

—

g--

рег< - ) (х, у, п) ~ max (х (п + max (G+

(.Х),

G+

(у)) + l),

Ввиду лемм 5 и 6 алгорифм

регх",у

является

регу­

лятором фундаментальности ПРЧ умн*, у .

Построим алгорифм • такой,

что для

любых

КДЧ

х, у

х • у,

если

х

и у — рацио-

9 1

нальные

числа,

J<x,y)~

| ^ умн^'уЗ О Е Per5c?i/3> е с л и

х о т

я б

ы

° Д Н 0

из х, у не является ра­

циональным

числом.

Алгорифм в• будем называть

операцией

умножения

КДЧ. Из

сказанного выше следует, что

•

является ал-

горифмом

типа (S)2 ->iZ>).

&>

Из определения алгорифма •

непосредственно

усма-

тривается

следующая

АРИФМЕТИЧЕСКИЕ ОПЕРАЦИИ НАД КДЧ

155

Л е м м а

7.

Для

любых

КДЧ х,

у и

любого

п

• (х, у) (п) ~х(п)-у

(п).

I

I

Переходим

к определению операции деления.

Л е м м а

8.

Можно

построить

алгорифмы

G~

и G~

типа (Ф т+ Ж)

так,

что для

любого

КДЧ

х

1)

Ю~(х)

=

хфО,

и если

Ю~(х),

то | х\>

2~°~(х);

2)

если

хФО,

то

Ю~ (х),

и

\ x(i)

| >

2~а~{х)

при

i > 0~

(х).

образом

алгорифма

G~

уже

фактически

установлено

в доказательстве леммы 8 §

3 (см. утверждения

(75),

(76) и (79) этого доказательства).

О п р е д е л е н и е

4. Будем

говорить,

что ПРЧ

ос

яв­

ляется

обратной

для

ПРЧ

<%ь если

при любом

п

1,

если

а, (п) =

0,

1 : aj (п),

если

а, (п) ф

0.

Л е м м а

9. Пусть

ПРЧ

а является

обратной

для

см,

ПНЧ

Pi

является

регулятором

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

а\

и

натуральные

числа п, k таковы,

что при

i ^

k

I a,

(i) I >

2-".

Пусть

далее

ПНЧ

р

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

I

р (/)=i= max

р,(/ +

2 - л ) ) .

Тогда

р

является

регулятором

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

ПРЧ

а.

i,

}S>р(/).

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

Пусть

Тогда,

так

как р ( / ) > / г

и

р (/) >

Р! (/ +

2 • п), имеет место*)

а ( / ) - а ( / ) |

=

«1 (/) — ai (О

«1 (0 • «i (/)

=

| а, (/) — ai (0|

2 ~ г - 2 - " =

,

| a i ( 0 | - | a , ( / ) |

2 - 2 ' "

что и требовалось.

Построим алгорифмы обр'1 '

и

рег( 1 )

такие,

что для

любого КДЧ х и любого п

1,

если

х(п) =

0,

Обр( 1 )

{Х, П) :

1 : х(п),

если

х(п) ф 0;

рег( 1 >

(х, n) са max (* (n + 2 • G~ (*)),

G~(*)).

Используя

лемму

8,

легко

построить

алгорифм X

так, что при любом КДЧ х

\к(х)

=

хф0,

и если \К(х),

то К(х) == Л .

Построим теперь алгорифм обр так, что**)

обр (х) ~ к (*) £ обр'1* 3 О £

3-

Из леммы 9 и определения

К получаем

следующее

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

Л е м м а

10. Алгорифм

обр

является

алгорифмом

типа (3) -T*SD)

и при любом

КДЧ

х

!обр (х)=*хф

0.

Кроме того, из леммы 8 следует

*)

Запись

—

понимается

как л, : г2.

Г2

<р

**)

Алгорифм

К введен для того, чтобы алгорифм

обр (а

затем

и

алгорифм

деления) оказался

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

функцией (см. § 1

гл.

5).

160

КОНСТРУКТИВНЫЕ ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА

[ГЛ. 2

Отсюда по лемме 4 и теореме 9 § 3 получаем

\х\ —х.

Утверждение

4)

доказывается аналогично.

Т е о р е м а

3.

При

любых

КДЧ х, у

1)

min (х,

у) ^

х ^

max (х,

у);

2)

min (х,

у) ^

// ^

max (х,

у);

3)

невозможно,

чтобы

одновременно

имело

место

и

min (х, у) ф

х

min {х, у)

ф

у;

4)

то же,

что и

3 ) , с заменой

min

на

max.

Доказа­

тельство

этой

теоремы предоставляется

читателю.

§ 5. Рациональные числа в конструктивном

континууме

Введем некоторые важные

понятия.

О п р е д е л е н и е

1. Слово

вида

х А

у

(х V у), где х,

у — КДЧ

такие, что х ^

у (х <

у),

назовем

сегментом

(интервалом).

КДЧ

х и у

будем

называть

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

но левым

и правым

концами

сегмента

х А

у

(соответ­

ственно

интервала

х V у).

Сегмент

х Д у

(интервал

х V у)

назовем

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

если

х и у —

рациональ­

ные

числа.

Ниже, в тех контекстах, где речь может идти безраз­

лично о сегменте или интервале, мы будем

употреблять

термин «промежуток» и запись

х%

у.

Два

промежутка

ляются сегментами или

интервалами.

О п р е д е л е н и е

2.

Будем

говорить,

что КДЧ z

при­

надлежит

сегменту

хАу

(интервалу

xS/y),

если

х^.

<С z ^ у

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

х <

z <

у).

Принадлежность

z данному

промежутку

х X У будет

выражаться

записью

zezxXy.

Кл

и Ка,

Нетрудно построить

алгорифмы

перераба­

вый и правый

концы

(ср. пример 6 п. 4 §

1 гл.

1).

О п р е д е л е н и е

3.

Будем

говорить,

что

промежу­

ток х%у

включен

(строго включен)

в

одноименный

промежуток *iX#i»

11 писать

х X у s

хх

X У\

(соответ­

ственно

х X У с= * i

X У\),

если

х^х{

и yi^y

(соответ­

ственно

х < х{

и г/i

<

у).

Аналогично можно было бы определить включение

(строгое

включение)

и для разноименных

промежутков.