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

406

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

МЕТРИЧЕСКИЕ

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

[ГЛ. 9

Отсюда ((10))

получаем,

что

y p Q

является

регуляр­

ной последовательностью, сходящейся к р (у1

(Р,

V (Q), 0)).

Поэтому ((7))

\y3(P,Q)

и

уЦР,

Q) = ?>(yl(P,

V(Q),

0)).

Так как Р ( у ' ( Л

V(Q)> О й е ^

м

и SB — правильное

мно­

жество, то у3(Р,

Q) е

SB, что и

требуется.

Множество

5?

перечислимо,

поскольку

можно

'по­

вам в алфавите Аи

которые

принадлежат Ш. Построим

алгорифм

у5, перечисляющий

31, и алгорифм

у такой,

что

(12)

у(п)~уЦуЦп)).

Ввиду

(11) у перечисляет некоторое подмножество Ж

множества

SB'. Для

завершения доказательства

осталось

Построим

алгорифм

а так, что для любого шара S

в М и

XZEM

(13)

!or(S,

I ) s I e S .

(15)

62(P) =

Wp3-

Искомый алгорифм б строим так, что

(16)

д ( Я ) ~ уЦР,

б 2 (Я)).

Фиксируем

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

Р ^2?

и

покажем,

что

1б(Р),

8(Р)ЕЕЖ

И

Р е а ( 8 ( Р ) ) .

Действительно,

имеет место

(17)

если

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

слово,

то

!б'(Р, Q)

(см.

(5), ( 7 ) - ( 8 )

и (13)—(14));

(18)

б 2

(Р) — непредельное

слово

и

! б ! ( Л б 2 ( Я ) )

((17),

(15)

и лемма 2 §

2).

Ввиду

(18),

(6),

(9) —(10)

слово

Р,

б 2 (Р )

принад­

лежит

Отсюда согласно

(11)

получаем

1у3(Р,

82(Р)),

т. е.

((16))

16 (Р).

Тогда

по

определению у5

и

(12)

408

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

МЕТРИЧЕСКИЕ

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

[ГЛ.9

С л е д с т в и е

2.

В

слабо

полном

КМП

всякое

эф­

фективно

открытое

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

множество

лаком-

бово.

В

слабо

полном

КМП

всякое

эф­

С л е д с т в и е

3.

фективно

открытое

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

множество является

согласованным.

[1]). В

слабо

пол­

С л е д с т в и е

4

( М о с к о в а к и с

ном

сепарабельном

КМП

всякое

эффективно

открытое

согласованное

множество

является

лакомбовым.

Для

доказательства

следствия

2

достаточно

заме­

множества. Следствие

3 вытекает из следствия 2 и тео­

ремы

2. Следствие 4

вытекает из следствия 2 и лем­

мы 5

§ 2.

тывающий всякое КДЧ х в шар (в

пространстве КДЧ

Ei) с центром в точке х и радиусом,

меньшим 2 - " - Y ( * ) - 2 .

горифмы

р ь

р2 так," что Pi перечисляет

некоторое мно­

жество

КДЧ Ж, а

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

всякое КДЧ х в

натуральное

число,

причем всегда

!Pi(p2 (x))

и

х е

^ 0(Pi(P2(*)))• Поскольку, очевидно,

множество

Ж бес­

конечно,

то

pi можно заменить

арифметически

полным

алгорифмом

рз, перечисляющим

без

повторений

то

же

самое множество Ж. При любом k

k

k

оо

21 е (Рз (0) I < 2

2 - " - у ( Р з ( ' ) Ь 2 <

2

2 " 1 - ' - 2 = 2 ~ п - \

*=о

г=о

г=о

§ з] В Ы Б О Р П Е Р Е Ч И С Л И М О Г О П О К Р Ы Т И Й .

Н Е П Р Е Р Ы В Н О С Т Ь 409

рациональное покрытие конструктивной прямой (в смыс­

ле определений § 1 гл. 8).

Существование сингулярных покрытий показывает,

что теорема 1 не может быть усилена

до теоремы о воз­

покрытиях)

изучался

в

последнее время

Л и ф ш и-

ц е м

[4].

Можно

показать

(см. Н о г и н а [3] и К у ш н е р

[10]),

что ни одно из условий теоремы

1 не может быть опу­

щено (даже при сохранении остальных условий).

2.

Докажем теперь

основную

теорему работы

Ц е й -

т и н а [5], усиливающую теорему

непрерывности

§

2.

Т е о р е м а 3 (Г. С. Цейтин). Пусть Мх — слабо

пол­

ное

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

КМП,

М2— произвольное

КМП

и

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

а

оператор

типа М\-т*М2.

Можно

построить алгорифмы

и

% такие, что при

любых

m,

п

1)

если

\а{т,п),

то

о(ш,п)

— шар в

Мг

и

h(m,n);

2)

если

\x(m,n),

то x(m,ri)

Е ^ ;

.3)

если

\o(m,n),

X е= а(ш,п)

и

\W(X),

то

р2(Ч>(Х),

x(m,

п))<2-т;

4)

если

\W(X),

то осуществимо

k

такое,

что

\a(m,k)

и

X e o ( m , k). (Здесь р2

— метрический

алгорифм

М2.)

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

Обозначим

через

2?

область

определения оператора Vf. Очевидно, ^

— согласован­

ное множество. По теореме непрерывности

(теорема

И

§

2),

построим алгорифм а так, что при

любых

m

и

(19)

если №(Х)

(т. е. X

£),

то

\a(m,

X), a(m,

X)-

шар с центром в точке

X,

причем

для

любого

У е = а ( т , X) такого,

что

\Ч (Y),

выполняется

410

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

[ГЛ. 9

(21)

если

то

!у (т, X),

у(т,Х)^Жт

и

X е= а (т, у (т,

X)).

Искомые

алгорифмы

т

и а

строим

теперь так,

что

(22)

х{т,

п)~Ч?(х'(т,

я)),

(23)

а(т,

« ) ~ а ( я г ,

т'(/я, я)).

утверждение 2) из (20) и (22), утверждение 3)

из (19),

(20)

и (22) — (23). Наконец, утверждение 4)

вытекает

из

(21).

ная нами в § 2

гл.

5 усиленная теорема непрерывности

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

функций и теорема Крайзела — Лаком­

ба — Шёнфилда

—

Цейтина

( К р а й з е л , Л а к о м б,

Ш ё н ф и л д [1]—[2],

Ц е й т и н

[3]—{5]) о продолжимости

ремы 3 (ср. §

1 гл.

1 работы

Ц е й т и н а (5]) * ) .

Существуют

два

подхода

к определению вычислимых операто­

ров. Мы поясним

эти

подходы

на

примере операторов, аргументами

и значениями которых

являются

арифметические функции (т. е.