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

402

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

ПРОСТРАНСТВА

[ГЛ. g

натурального

п

Р,

п,

Q ) ~ G ( 2 - ' t - I - p 2

( T ( P ) ) W(Q))),

%2(т,

Р,

п,

Q)~G(p2(4{P),

^ ( Q ) ) - 2 - " - ' ) .

H n ( m ,

Р, n)~sep(P,

б ^ з . р . п З ) ,

где

sep

— алгорифм, построенный по теореме 8.

Фиксируем

произвольный

алгорифмический

опера­

тор

V

типа

М{ т* М2,

точку X е= Мх,

в

которой

опре­

делен 4f , и натуральное

п.

Обозначим

для краткости

через Т

слово

£ 4 ^ . X,

п.

Пусть 5£'т и ^'/—множества

точек Мх,

определяемые

условиями

У <= 2?'т =

'Д1

(Г, У),

:

Е

Я

=

!212(Г, У).

Ясно, что

K s S ' r

(У s

i??)

тогда

и

только

тогда,

когда \XY{Y)

и

р2

1 Р ( У ) ) < 2 - № - 1

(соответственно р2 (Чг

(J),

^(У)) > 2 - " -

1 ) .

Кроме

того,

Z е

i ^ f . Нетрудно

также

убедиться, что

множества 3?'т

и 9?т согласованные,

причем 21г и Щ—их

согласующие

алгорифмы. Тогда

по

теореме 9 алгорифм Щ просле­

живает множество ST.

Поскольку 9?т П %'т= 0 и X е

5 г ,

для

X,

^ г , 21г,

выполняются

все

условия

се-

тывает

слово Е^З, :Х,

п в шар с центром в

точке X,

внутри

которого нет

точек множества 2?т*

Следова-

§ 3] ВЫБОР

ПЕРЕЧИСЛИМОГО ПОКРЫТИЯ. НЕПРЕРЫВНОСТЬ

4Q3

тельно, если

\W(Y)

и У е Н п

X, п), то

Y ф. 9'т-

Отсюда р2 (W (X), У (У)) <

2~л-х

< 2~п, что и требовалось.

С л е д с т в и е

13.

Всякая

конструктивная

функция

непрерывна

(ср. § 2 гл. 5).

С л е д с т в и е

14.

Всякий

эффективный

функционал

непрерывен.

Остановимся несколько подробнее на следствии 14.

Пусть

W — эффективный

функционал, т. е. алгорифми-

ческий

оператор

из

бэровского пространства в

про­

странство натуральных

р ,

р (()

=

—

такая

ПНЧ,

чисел.

Пусть

р,

что !Ч^(EPi3) - Тогда можно указать

такое

натуральное

N, что для любой ПНЧ

2 если

2

Pi(0

при

i^N

и ^(ЕРгЗ), то X F(EP,3)^1 F(EP2 3).

Таким

образом,

основной теоремы работы Ц е й т и н а [5].

О п р е д е л е н и е

1. Пусть Mi — КМП и 9?<=Mi.

Ал­

горифм а будем называть эффективным

покрытием

мно­

жества

9?, если он

перерабатывает всякий

элемент

9?

в шар,

содержащий

этот элемент.

О п р е д е л е н и е

2. Будем

говорить,

что из эффектив­

ного

покрытия а множества 9

можно

выбрать

перечис­

лимое покрытие множества 9, если осуществимы

алго­

рифмы

у и б такие, что

1)

у

перечисляет

некоторое

подмножество

Ж

множе­

ства

9;

i

3]

ВЫБОР

ПЕРЕЧИСЛИМОГО

ПОКРЫТИЯ. НЕПРЕРЫВНОСТЬ

4Q5

Построим

алгорифм у2

такой,

что

0)),

если

[Щ(Я,п)фА,

у 2

(

Р ' Q ' П ) ~

I

Р ( Y 1 (Р, V (Q), 0)),

если

[Щ (Q, я) =

Л

Из

(2) — (4)

получаем

(6)

если

Р е=

и Q — непредельное

слово,

то

у | Q

есть регулярная последовательность

точек М, схо­

дящаяся к

]°>{у1{Р, V(Q), 0)).

Пусть

Lim — алгорифм

слабого предельного

пере­

хода

в пространстве М. Построим алгорифмы

у3

и у4

так,

чтобы

(7)

У 3 ( Л Q ) ~ L i m ( E y | > Q 3 ) ,

(8)

у4

(Р, Q) ^

а (у3 (Р, Q)).

Пусть

Ро,

Р\,

Рп — список

слов

(в алфавите

А).

Назовем

этот

список

регулярным,

если

при любых

i г=Г

\G{2-l-9(Ph

Р,)).

ности упорядоченных списков точек КМП.)

Рассмотрим множество 9t (в алфавите А\)

слов

вида

Р, Q такое, что Р, Q GE 91 тогда и только тогда,

когда

(9)

Q — непредельное

слово;

(10)

при

i^V(Q)

!у2(Р,

Q,

/)

и

слова

у2 (^>

Q. 0),

Y2 (Р, Q,

1),

. •., Y 2 ( Л Q ,

V(Q))

образуют

регу­

лярный

список.

Нетрудно

убедиться,

что

(11)

если

слово

Р, Q

принадлежит 91,

то

! Y 3 ( P ,

Q) И

Y 3 ( P ,

QJeS' .

В

самом

деле, поскольку

Q—непредельное слово,

то

2

f

p(v'(P,

п. 0))

П Р И

K ^ ( Q ) ,

Y

(Р, Q> rt) — J

р ( Y i ( р >

т/ ( Q ) >

0

) )

п р и

n

^

т/ ( Q

) -