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

Скачать файл (14,18Мб)

Заказать решение

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

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

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

Добавлен: 15.10.2024

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

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

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

392

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

[ГЛ. В

Метод захвата впервые в явной форме использо

вался для	изучения	вычислимых операторов в работах
Ц е й т и н а	[4]—[5].	Близкий	метод был развит	также
К р а й з е л о м , Л а к о м б о м			и Ш ё н ф и л д о м	[1]—[2]

при доказательстве непрерывности эффективных функ ционалов*). Другой оригинальный подход, основанный На теореме Клини о неподвижной точке и позволяющий получить примерно тот же круг результатов, что и ме тод захвата, предложен Московакисом в работе [1]. Как в методе захвата, так и в методе Московакиса, суще ственным образом используется принцип Маркова.

Нам будет удобно фиксировать некоторое перечис лимое множество с неперечислимым дополнением. До казываемая ниже лемма 2 специфицирует принцип за хвата применительно к этому множеству.

Пользуясь универсальным алгорифмом, построим ал горифм 59 так, что для любого алгорифма 91 в алфа вите Л? и любого слова Р в Л

33(£913, Р)^Ъ(Р).

	Построим			также алгорифмы (g и V такие, что
				@(/>)~23(/>, Р),
				V	(Р)~цп([Щ(Р,		п) =		Л) .
	Очевидно,					\V(P)^№(P),

и	если	\V(P),		то (§, заканчивает				работу над		Р точно
за	V(P)	шагов.				10. Слово	Р	(в	алфавите	А)	на
	О п р е д е л е н и е
зовем предельным					(непредельным),			если
						-}№(Р)
(соответственно					\0£(Р)).
	Л е м м а			2. Если		алгорифм	91 в		алфавите	Л?	при
меним		к	любому		предельному		слову,		то £913	есть	не
предельное			слово,		к	которому	применим 91.

*) Конструкцию,	близкую к схеме применения метода	захвата
в теореме 7, можно	также найти в работе М а й х и л л а	и Ше -
п е р д с о н а [1].

СОГЛАСОВАННЫЕ	МНОЖЕСТВА. ОПЕРАТОРЫ	393
Д о к а з а т е л ь с т в о .	Предположим, что	£213—

предельное слово, т. е.

~]!»(£ЯЗ, Е«3)-

Поскольку

(ю) »(£яз.

то тогда

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

условиям

леммы.

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

место

" П ! 8 ( £ Я З ,

Е«3),

откуда

по принципу Маркова

получаем

(П)

!33(Е«3.

Е913),

Из

(10) — (11)

получаем,

что

Е^З—непредельное

слово,

причем

Лемма

показывает,

что

множество

предельных

слов

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

(в то

время как

множество

непре

дельных слов, очевидно, перечислимо).

Проиллюстрируем

применение

принципа

захвата

на

примере

следующего,

представляющего

самостоя

тельный интерес

предложения

(ср. Ц е й т и н

[5;

лемма

1 гл. 3]).

Пусть

— слабо

полное

КМП,

Т е о р е м а

52 —

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

множество

точек

Ми

1 е й

р —

после

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

точек

Ми

регулярно

сходящаяся

к X

(определение б § 1). Тогда

при

любом

можно

найти

натуральное

такое,

что

p ( / ) e i %

pi(p(/), X) <

2 _ г а .

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

С помощью леммы

1 построим

алгорифм

у так, что

(12)

если

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

слово, то

у{Р)

Х,

ж,

(13)

если

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

слово, то

y{P) =

HV{P)+l)

394

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

МЕТРИЧЕСКИЕ

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

[ГЛ.

(алгорифм

V перерабатывает всякое

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

сло

во в натуральное

число — см. стр. 392).

Пусть алгорифм % согласует множество Я

(опреде

ление 3). Построим алгорифм б так, что

6(m,

P ) ~ G ( 2 - m - P l ( Y ( P ) ,

Х))%(у(Р)).

Очевидно,

(14)

! б ( т ,

P ) ^ ( p , ( Y ( P ) ,

Х)<2-т)&(у(Р)^М).

Построим

такой

алгорифм о,

что

а(т)

£ б т 3 .

Ввиду (12) и (14) алгорифм

б т применим

любому

предельному

слову.

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

(лемма

2),

а{т)

есть непредельное слово и \8(т, о{т)).

Поэтому

((14))

(15)

M v H m ) ) ,

Х)<2-т

(16)

у(о{т))е=Я.

Построим

теперь

алгорифм 0 так,

что

8 ( m ) ~ V(o(m))+

Так

как

при

любом

о(т)

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

слово,

то 6 есть последовательность натуральных чисел,

при

чем

Y(a(m)) =

P(9(m)).

м,

Отсюда

на основании

(15) — (16)

получаем

8 (9 (m)) е= Я

р,(Р(в(т)),

Х)<2~т,

чем

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

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

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

рема

7 дает

Пусть

М{

— слабо

полное

КМП,

С л е д с т в и е

X G= Ali,

В —

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

точек

Ми

регулярно

сходящаяся

Если

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

оператор

Чг

определен

точке

X, то для

любого

можно

указать

п так, что pi(X,$(n))

2~m

и I T (В (я)),

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

395

Предлагаем читателю	в качестве	простого упражне
ния усилить следствие 4, потребовав дополнительно
р2(Ц(Х),	ар (р ( « ) ) ) <	2~т
( Ц е й т и н [5; лемма § 1 гл. 3]).
Переформулированное	таким образом следствие 4

можно рассматривать как усиление теоремы неразрывно сти для алгорифмических операторов.

Теорема 7 показывает, что в слабо полном совер шенном пространстве согласованное множество не мо

жет иметь изолированных точек. Из

нее

вытекает так

же, что в слабо полных КМП дополнения

согласован

ных

множеств

обладают

некоторыми

свойствами

замкнутости.

Пусть

— множество

точек

О п р е д е л е н и е

11.

КМП

М{

и l e

Mi.

предельной

точкой

Назовем

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

множества 9 ,

если

можно

построить

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

ность точек 9',

сходящуюся

Множество

назовем

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

замкну

тым, если

оно

содержит

все свои

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

пре

дельные

точки.

слабо

полном

КМП

дополнение

С л е д с т в и е

любого

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

множества

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

зам

кнуто * ) .

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

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

если

множество

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

точек М\,

не принадлежащих

сходящаяся

то X ф9,

поскольку

противном

случае по теореме 7 при некоторых / р(/) также при

надлежало

бы

9?.

Подпространство

полного

КМП,

ин

С л е д с т в и е

дуцированное

дополнением

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

множества,

полно.

Пусть

<=^М\. Будем

говорить,

О п р е д е л е н и е

12.

что алгорифм

прослеживает

множество

9 , если

он

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

всякий

шар,

имеющий

непустое

пере

сечение

9 ,

точку,

принадлежащую

как

9 ,

так и

*) Если

9? — множество

точек

КМП

Ми

то

дополнением

(в A l l )

мы

называем

множество,

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

условием

(Р s

A f , )

& (Р £

3S).

396	К О Н С Т Р У К Т И В Н Ы Е М Е Т Р И Ч Е С К И Е	П Р О С Т Р А Н С Т В А [ГЛ. 9
этому	шару*). Множество 2? назовем	прослеживаемым,

если можно построить прослеживающий его алгорифм.

Т е о р е м а

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

теорема;

М о с к о в а -

к и с

[1]). Пусть М\ — слабо

полное

КМП, 5?\ — согла

сованное,

2?2 —

прослеживаемое

множество

точек

Ми

причем

2?х П 3?2 =

0 • Тогда

для

каждой

точки l e ^ i

можно

найти

шар

центром

точке

не

со

держащий

точек

множества

2?2

(рис.

23).

Точнее

говоря,

можно

построить

алгорифм

sep

так,

что

Рис.

23. 5?х

— согласо

для

каждого

слова

вида

X, £9ti3»

ванное множество,

3?i—

£9t23 и любых

множеств точек 2?\,

дополнение 9?ъ

3?2—про

9?2,

если

%х

согласует

2?х,

912

слеживаемое

множество

(.г

=<?,).

прослеживает

2?2,

3?\ Л 3?2 =

и I s f ,

то !sep(J,

E2li3, №3)

sep (X,^c:%S,

Е ^ г З ) —

шаР

Центром

точке

имеющий

пустое

пересечение

с 2?2-

у такой,

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

Построим

алгорифм

что

при любых

словах

Р и Q

Очевидно,

у(Р,

Q)~P*V(Q).

(17)

при любом I G M ,

И непредельном слове Q [у (X, Q)

и у{Х,

Q) —ш а Р

с центром

в точке

Пусть

Х^Ми

9?2 — множество

точек Мх.

Скажем,

что

непредельное слово Q сцеплено с

X и

3?2,

если

у(Х,

Я)[)2?2Ф0.

у1 так, что для любых

слов Р и

Построим

алгорифм

Q, любого

алгорифма %

и любого

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

уЧР,

№3, Q, п)

Р,

если

[ ® ] ( Q , « ) # A ,

%(P*V{Q))>

если

[®](Q,

л ) = = Л .

(Алгорифм

*)	Мы говорим, что множество R пусто, и пишем R — 0 ,	если
~]ЗР	{Р е R). Множество R называется непустым Щф0),	если
неверно, что оно пусто.

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

Лебедев, Н. Н. Курс инженерной геодезии. Геодезические работы при проектировании и строительстве городов и тоннелей учебник.pdf

Лурье, Г. Б. Основы технологии абразивной доводочно-притирочной обработки учебник.pdf

Маринов, И. А. Устройство и эксплуатация преобразовательных подстанций городского электротранспорта учеб. пособие.pdf

Межотраслевые связи и народнохозяйственные пропорции Восточной Сибири и Дальнего Востока..pdf

Мирзоян, Э. Н. Развитие учения о рекапитуляции.pdf

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

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

Информация

Списки файлов

Дополнительно