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

388

КОНСТРУКТИВНЫЕ МЕТРИЧЕСКИЕ ПРОСТРАНСТВА [ГЛ. 9

Построим теперь алгорифм (S так, что

ным и только положительным КДЧ.)

Пусть

~~|!&(Р). Тогда у(Р) = Х.

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

и поэтому

p2 (9l(Z),9t(Y(P))) = 0,

ЩР).

Если

!•§> (Р), то при некотором

k

у{Р) — $ [k) и, сле-

довательно,

м1

р2(%{Х),Щ(Р)))>г,

откуда

следует

1 ! 6 ( Р ) .

Поэтому если !(S(P), то ~1!ф(Р).

Таким образом, при любом Р

\&(P)=s~ll${P).

Это, однако, невозможно. Теорема

доказана.

С л е д с т в и е

2.

Пусть

Mi — слабо полное

КМП,

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

КМП.

Никакой

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

оператор

типа

Mi ~? М2

не

может

иметь

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

ного

разрыва.

Никакая

С л е д с т в и е

3

(теорема

А. А. Маркова).

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

функция

не

может

иметь

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

ного

разрыва.

Это

утверждение

получается

из

следствия

2, если

в качестве Mi и М2

взять пространство КДЧ.

3. Значительная часть наших

дальнейших результа­

тов

(в

частности, теорема

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

будет полу­

чаться

с

помощью

одного

общего

принципа,

который

мы,

следуя

терминологии

Ц е й т и н а

[9],

назовем

«принципом захвата».

Пусть по-прежнему фиксирован

некоторый

алфавит

А (содержащий

буквы

0 и

| ) , и пусть Ж— перечисли­

мое

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

алфавите, дополнение Ж ко-

СОГЛАСОВАННЫЕ МНОЖЕСТВА.

ОПЕРАТОРЫ

389

торого

до

множества

всех слов

в

А неперечислимо * ) .

Пусть,

далее^ Жх — перечислимое

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

в Л)

такое,

что

Ж<=Ж\.

Тогда можно найти слово Р,

при­

надлежащее ЖПЖх

(принцип захвата). Другими

сло­

дополнение

множества

Ж, «за­

хватывает»

и

некоторый

эле­

мент

Ж,

причем соответствую­

щий элемент может быть эф­

фективно найден (рис. 21).

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

высказан­

ного

утверждения

почти

оче­

видно.

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

множе­

ство

Ж[\Ж\

как

пересечение

Рис. 21. Заштриховано пе­

перечислимых

множеств

пере­

речислимое

множество

числимо.

Построим

стройный

Жх

( I s ! ,

) .

алгорифм

у>

перечисляющий

ЖГ\Ж\.

Если П1у(0), то

множество ЖС\Ж\

пусто

и, сле­

довательно, Ж\ совпадает

с Ж,

что невозможно из-за не­

куда

по

принципу Маркова получаем

!у(0). Очевидно,

у(0) е

Ж Л Ж и т. е. является искомым

общим элемен­

том Ж и

Жх.

стями применения метода захвата в

этой

главе**).

Пусть

ЗУ — некоторое

множество

слов

в

алфавите

А

и £Ф — какое-нибудь

свойство

элементов

этого

множе­

ства. Свойство s& назовем потенциально

перечислимым

на множестве 3?, если можно указать

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

свойство

(множество)

s4-' слов в

алфавите

А,

выпол­

няющееся для тех и только тех элементов 2,

которые

обладают

свойством

s4-. Например,

свойство

точек

*)

Ясно,

что Ж неперечислимо тогда

и только

тогда,

когда

Ж

не является

разрешимым множеством.

**) Мы рекомендуем вернуться к этим пояснениям после озна­

комления

с

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

7 и

сепарационнои

теорему.

390

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

[ГЛ.8

конструктивного метрического

пространства отличаться

(в

смысле метрики) от данной

его точки является

по­

можность

(ср. лемму 1)

в случае

слабо полных КМП

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

(непринадлежность)

слов пе­

речислимому

множеству

к различию (эквивалентности)

точек

КМП

весьма

существенны

при

создании

ситуа­

ций для применения

принципа захвата.

Метод

захвата

применяется

нами

по

следующим

двум

схемам.

КМП М,

а)

Пусть

2 — некоторое множество

точек

si- — потенциальное

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

свойство

точек

2 , и

Пусть s4-'— перечислимое

множество

слов, пересечение

которого

с 2 состоит

из тех и только

тех элементов 9?,

которые обладают

свойством si-. Предположим, что нам

удалось

построить

алгорифм у так, что (Ж — перечис­

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

с неперечислимым

дополнением)

(4)

если

Ре=Ж,

то

\у(Р)

и

у{Р)е=&,

(5)

если

P e l ,

то

\у(Р)

и

у(Р)е=а'.

Очевидно, 2л

перечислимо

и ((5.)) Ж s 2 Л

. Следова­

тельно,

можно

указать

Q е

Ж(]2л-

Ввиду

(4)

и (6)

у (Q) е 2

и у (Q) обладает свойством si.

Схему а) можно

проследить в доказательстве

теоремы

7 (а также

в тео­

реме § 3 о выборе перечислимого

покрытия).

Более тонкой является схема б), применяемая

в се-

парационной

теореме.

КМП М

б) Пусть

2\

— некоторое

множество точек

и X — точка

М.

Скажем,

что точка X

перечислимо от­

делима

от 2\,

если

существует

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

множе­

ство 31 такое, что всякая

точка, эквивалентная

X,

при­

надлежит 31, а лк}бая точка

из 2\

не принадлежит 31.

(Напомним,

что 2\

получается из 2\

присоединением

всех точек, эквивалентных

в М точках 2\.)

Пусть 2 2 —

некоторое множество-шаров

М, и мы хотим

найти шар

8 2]

СОГЛАСОВАННЫЕ МНОЖЕСТВА.

ОПЕРАТОРЫ

391

из 2*

не пересекающийся с S V ) .

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

что

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

у2 со следующими

свойствами

от

2£\. Рассмотрим множество

такое,

что

P e ^ , s ! Y 2 ( P ) & ( Y 2 ( P ) e | ) .

Очевидно,

3iXl

перечислимо

и

((8)) Ж s & S x . Сле­

довательно, можно найти

слово

Q, общее

множествам

Ж

и

&<ev Согласно

(9)

шар

у\(0)

не

пересека­

ется

с S\,

что

и

требует­

ся

(рис.

22).

j{.

Главную

трудность

при

проведении

этой

схе­

мы

составляет,

конечно,

построение

алгорифмов

Yi

и,

в

особенности,

у2.

Ясно,

что

это

построение

Рис. 22.

Заштриховано

перечис­

выглядело

бы

более

ре­

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

91 а .

альным, если бы мы рас­

полагали

алгорифмом,

находящим

по каждому

шару из

9?2,

пересекающемуся

с 2?и

точку,

общую

2?\

и этому

пересекаемости

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

шара с 3?\ потенциаль­

но перечислимым

(на множестве всех шаров), что обес­

печивает существование искомого «алгорифма

выбора».

*) Например,

при

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

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

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

ной функции / в нуле

нужно (при данном фиксированном п) найти

окрестность нуля,

не

пересекающуюся с множеством тех х, для

которых \{(х) и | /

( * ) —

/(0) | > 2 - " .