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

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

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