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

ОТНОШЕНИЯ ПОРЯДКА НА МНОЖЕСТВЕ КДЧ

145

Построим

(пользуясь леммой 2) алгорифм В, пере­

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

такое, что

(65)

уп -

хп >

2~п+\

в натуральное число, для которого

(66)

у п - х а > 2 - п + 1

+

2-*0е-у-а\

Построим

далее алгорифм

93 такой,

что для

любого

слова вида х,

у, п, z, для которого

выполняется

(65),

j l ,

если

z p u . g , n ) + 2 < Х п

+ У п ,

93 (х, у,

п, z) ~ '

,

| 2 ,

если

г${х,у,п)+2>

Х

п

\

ы

(алгорифм 93 нетрудно

построить,

используя

теорему об

мов и разрешимость отношений

> ) .

з>

з

Покажем,

что 93 обладает

требуемыми

свойствами.

Пусть х, у, z,

п — слово такое, что выполняется

(65).

Тогда

ф(х,

у, п).

Следовательно, !93(х,

у, п,

z)

и

93(х, у,

п,

z)

=?= 1 или 93(Л;, у,

п, z)

= 2 . Обозначим

ня

время доказательства

р(х, у, п)

через /.

Пусть

93{х, у,

п,

2 )

= 1. Тогда,

очевидно,

(67)

Z t + 2 < I n + I l L ,

Пусть

теперь

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

натуральное

число,

Тогда

max (г/(л), г (/ + 2)).

(68)

\yji)-yn\<2~n,

(69)

\z(i)-zl+2\<2-'-2.

(70)

y n - z l + 2 > 2 - n + 2-1-1.

(71)

у (i) - г (0 > 2~п + 2"'"' - 2~п - 2~'~2 =

2~'~2,

146

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

ЧИСЛА

[ГЛ. 2

Из

(71)

по теореме

10 следует, что у

>

г.

Аналогично доказывается, что из 23(х, у, п, z) ==2

вытекает z

>

х.

Лемма

4

позволяет

следующим

образом

усилить

только что доказанную

теорему.

Т е о р е м а

21. Можно построить

алгорифм

Рз,

пере­

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

всякое

слово

вида

х,

у,

z, где х

< у,

в 1 или в

2

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

любого

слова

указанного

вида,

если

Рз (х, y,z) =?= 1, то z

< у, и

если

Рз(х,у,г)

=р 2,

то z

>

х.

<»

3>

Для любых КДЧ

х,

у имеет место

3)

3)

~] ~\(хЬу)

=

хЬу.

достаточно ограничиться

отношениями

= ,

< .

з>

з>

з>

1)

По определению

~] ~] (х^.у)

означает

~\~]~](х>у).

Предположим, что х > у. Тогда выполняется

~] ~] (х >

у),

что приводит к противоречию. Следовательно,

~] {х >

у),

т. е. х ^

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

2) = .

По определению 1 ~]~]{х

= у) означает

3)

3>

(72)

l l V n ( \ x n - y n \ ^ 2 - n + l ) .

Из

(72)

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

(73)

~]3n{\xn-yn\>2-n+l).

Из

(73)

получаем

148

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

[ГЛ. 2

(771

х

>

2 - N r ( 0 - * > + i

\ ' 1 >

X N r ( 0 , х)

^

При любом i ^

x(Nr(0,

х))

(78)

| x ( 0 - x N r ( 0 , x ) | < 2 - N r ( 0 - ' .

Из

(77) и (78)

получаем, что при таких i

(79)

х (0 > 2 ~ N r ( 0 > х ) + х

-

2~ N r ( 0 , х ) = 2~ N r ф - х ) .

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

х — КДЧ

такое,

что

при

лю­

Т е о р е м а

23.

/7г/сть

бом

и

<

2~п.

Тогда

х ^

0.

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

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

что

л; >

0. Тог­

да

\G(x),

G(x)—натуральное

число

и

х

> 2-G W,

что

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

условию. Следовательно,

1(х>0),

что и

означает х ^

0.

х — КДЧ

такое,

что

х^О

и

Т е о р е м а

24.

Яг/сть

при

любом

п х sg:

2 _ п . Тогда

х =

0.

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

По

теореме

23

имеем л: ^

0.

Отсюда и

из

л: ^

0 по теореме

17

следует

л: =

0.

Аналогично теореме 23 может быть доказана

следую­

щая

Пусть

х — КДЧ

такое,

что

при

лю­

Т е о р е м а

25.

бом

п имеет место — 2 _ п

х. Тогда

х >

0.

Из теорем 23, 25 и 17 вытекает следующее

утверж­

дение.

Пусть

х — КДЧ

такое,

что

при

лю­

Т е о р е м а

26.

бом

п

имеет место —2~п

*С х -<! 2~п.

Тогда

х = 0 * ) .