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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 146

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

§2] СОГЛАСОВАННЫЕ МНОЖЕСТВА. ОПЕРАТОРЫ 379

получены обычные приложения этой теоремы к диф­

ференциальным и интегральным

уравнениям (см.,

на­

пример, К о л м о г о р о в ,

Ф о м и н

[1],

Л ю с т е р н и к ,

С о б о л е в

[1]).

 

 

 

 

 

 

 

 

 

§

2 .

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

множества.

 

 

 

 

 

Алгорифмические операторы.

 

 

 

 

 

 

Теорема непрерывности (первая формулировка)

 

 

 

В

этом

параграфе

через

М,

Mi,

М2

обозначаются

некоторые фиксированные КМП с носителями

Л,

Ми

Ж% и метрическими

алгорифмами

р, рь р2 .

говорить,

 

1. О п р е д е л е н и е

1. Пусть X G E M .

Будем

что алгорифм

% согласован

в

точке X, если для

любого

F e = M

такого,

что Y = X,

выполняется

!2l(J)==

!91(У).

 

Таким

образом,

м

 

 

 

 

алгорифма

в

дай­

 

согласованность

ной

точке

означает,

что

этот

алгорифм

одновременно

применим или неприменим ко всем элементам М, сов­

падающим

с данной

точкой в

смысле

метрики

М.

 

О п р е д е л е н и е

2.

Будем

говорить, что

алгорифм

Ш. согласован

на множестве Ж s

JI,

если

31

согласован

в каждой

точке Ж.

Алгорифм,

согласованный

на

всем

множестве

М,

будем

называть

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

в

КМП

М или, короче,

просто

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

 

 

 

 

О п р е д е л е н и е

3.

Множество

Ж<=^М

назовем

со­

гласованным*),

если

осуществим

согласованный

 

алго­

рифм % такой,

что для

любого

X из М

 

 

 

 

Хе=Х^Ш{Х).

Про алгорифм % мы будем говорить, что он согла­ сует множество Ж; это обстоятельство будет также вы­ ражаться записью

Согл (Ж, %).

Согласованное множество полностью характери­ зуется своим согласующим алгорифмом. Поэтому в тех ситуациях, когда речь идет о построении согласованных множеств с тем или иным свойством, подразумевается построение соответствующего согласованного алгорифма.

*)

М о с к о в а к и с

[1]

использует

для аналогичного

понятия

термин

listable

set; в

близком смысле

употребляется также

иногда

термин

вполне

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

множество.

 

 

380

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

Обратно, если требуется построить по согласованному множеству какой-нибудь конструктивный объект, то в качестве исходных данных такого построения высту­ пает соответствующий согласованный алгорифм. Ана­ логичное замечание можно сделать и по поводу вво­ димых ниже последовательностей согласованных мно­ жеств.

В пространстве натуральных чисел Н согласованные множества совпадают, очевидно, с перечислимыми.

Непосредственно из

определения 3

получается

 

Т е о р е м а

1. Всякое

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

множество

пра­

вильно.

 

 

 

 

 

 

 

 

Простейшие примеры

согласованных

множеств

дает

Т е о р е м а

2.

1)

Пустое множество

и

носитель

КМП

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

множества;

 

 

 

 

2)

любой

шар

является

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

множеством.

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

Утверждение

1)

очевидно:

для пустого множества согласующим является алго­ рифм, не применимый ни к какому слову, носитель же пространства согласуется всюду применимым алгориф­ мом. Докажем утверждение 2). Поскольку (в силу ут­ верждения 3) теоремы 1 § 1) всякий шар является пра­ вильным множеством, достаточно построить такой ал­ горифм у, что для любого шара S и любого X GE М

\y(S,

I ) s Z e S .

Построим алгорифмы

Yi И у 2 так, что для любого шара

Х{*п

 

Y i ( * i

y2(Xl*n)=F2-n.

В § 3 гл. 2 приведен алгорифм G такой, что для лю­ бого КДЧ х

\G(X)E=X>0.

Искомый алгорифм у строим теперь так, чтобы для любого шара S и любого X *)

y(S, X) ~

G ( Y 2

(5) -

р (у, (5),

X)).

 

*) Для произвольных

слов

Р и

Q запись

Р — Q следует

пони­

мать как сокращение более точной записи —

(Р,

Q), где

алго-

рифм вычитания КДЧ.

 

 

 

СОГЛАСОВАННЫЕ

МНОЖЕСТВА. ОПЕРАТОРЫ

 

38!

Очевидно, для

любого

шара

S^X^n

 

и I

E

M

 

 

 

 

!Y (S,

X) =

р(Xl t

X) <

2 " "

s l

e

5 ,

 

 

 

что и

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

 

 

 

Последовательность

множеств

О п р е д е л е н и е

4.

 

{Жп} {У?п s Ж)

назовем

 

последовательностью

согласо­

ванных

 

множеств,

если

осуществим

алгорифм

%

такой,

что при

любом

п

выполняется

С о г л ( Х п , $ п ) .

 

 

 

Т е о р е м а

3.

1)

Пересечение

 

любого

 

конечного

числа

согласованных

 

множеств

является

 

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

множеством.

 

 

 

 

 

 

 

 

 

 

 

 

 

2)

Объединение

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

 

согласованных

множеств

является

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

множеством.

 

 

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

Пусть Ж\,

 

Ж%

 

Жп

— со­

гласованные множества

и уь

Y" — и

х

согласующие

алгорифмы. Построим алгорифм у так, что

 

 

 

 

 

 

 

у(Р)с*У1(Р)у2(Р)

...

 

уп(Р).

 

 

 

 

Очевидно, для любого X е М

 

 

 

 

 

 

 

 

 

 

1у(Х)=в

&

1у,(Х)^

& ( 1 е 1 г ) .

 

 

 

Далее,

если

X = Y,

то X <= Ж{^У

^

Ж{

и

потому

 

 

 

 

 

ж

 

 

 

 

 

 

 

у

 

 

 

!у(Х) =

!у(К).

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

алгорифм

согласует

пересечение множеств Ж

,

Ж„.

 

 

 

 

 

 

 

Пусть теперь {Жп}

— последовательность

согласован­

ных множеств,

Ж — ее

объединение,

91 — такой

алго­

рифм, что при любом

п

 

 

 

 

 

 

 

 

 

 

(1)

 

 

 

 

Согл (Жп,

in).

 

 

 

 

 

 

 

Построим алгорифм

б

так,

что при

любом

слове

Р

 

 

 

б ( Р ) ~ р л ( [ 2 1 ] ( / 2 ( Л Р, Ш

 

- Л )

 

 

 

(использованные здесь обозначения введены в §§

1 и

3

гл. 1).

 

 

 

 

 

 

 

 

 

 

 

Ж. Поскольку

Покажем, что б согласует множество

для любого X <= М

 

 

 

 

 

 

 

 

 

 

 

Х*=Ж=~\~}Зп{Х<=Жп)

382

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

[ГЛ. 9

и все множества Ж п правильные (теорема 1), то мно­ жество Ж правильное. Поэтому достаточно доказать, что для любого X <= М

(2)

 

 

 

 

! б ( X ) s X e

Ж .

 

 

 

 

 

 

 

 

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

пусть

!б(Х).

Тогда

Ь(Х),

 

l\(6(Х)\

l\ (б (X))

— натуральные числа. Обозначим

последние два

 

числа

соответственно

через

пх

 

и

п2.

Очевидно,

 

 

 

 

 

 

 

 

[91] (я,,

X,

п2)

=

Л ,

 

 

 

 

 

 

т. е.

91 заканчивает

работу

над

словом

пи

X

не

более

 

чем за

п2

шагов. Поэтому

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Ш(пи

 

X),

 

 

 

 

 

 

 

 

откуда,

ввиду (1),

получаем

 

 

 

 

 

 

 

 

 

 

 

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

 

X

€==

Жrtf

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Предположим

теперь,

что

 

Х

^

Ж .

Если

1\8(Х),

т

при всех i

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

[91](4(0,

X,

it (0) ф

Л ,

 

 

 

 

 

откуда,

очевидно,

следует,

что

при каждом

п

 

 

 

 

 

 

 

 

 

11% (п,

X).

 

 

 

 

 

 

 

 

Таким образом, X не принадлежит ни одному из мно­

 

жеств

Ж п , что невозможно.

Поэтому

выполняется

 

 

 

 

 

 

 

11\Ь(Х).

 

 

 

 

 

 

 

 

 

 

 

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

\Ь(Х),

 

чем

 

заканчивается

доказа­

 

тельство

эквивалентности

(2).

Теорема

доказана.

 

 

 

Теорема 3 обобщает теорему о перечислимости объ­

 

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

 

числа перечислимых множеств, которая получается из

 

теоремы 3, если в качестве М взять пространство нату­

 

ральных

чисел.

 

5. Алгорифм

 

W

назовем

 

алгориф-

 

 

О п р е д е л е н и е

 

 

 

мическим

оператором,

действующим

из

КМП

Мх в

КМП

 

М2

или,

короче,

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

 

оператором

типа

 

Мх

-7+М2,

если

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Смотрите также файлы