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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

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

415

ральных чисел; 2) алгорифм р применим к любому на­

туральному числу

{Р)(п)\

3)

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

КМП М $ЦР)(п))

регулярна.

 

Пользуясь сепарабельностью М, нетрудно построить

алгорифм, отображающий

М в

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

как р перечисляет плотное подмножество М, можно по­

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

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

шар

Х*п (где

X e J H )

в

натуральное число

так,

что

!р(а(Х*п))

и fi(a(X*n))

е= Х*п. Построим

алгорифмы

Fl,

F2 так, что для любого X ЕЕ М

И п

 

F4X,

п)сха{Х*п+

1),

{ )

F2{X,

n)~fi{F4X,

п)).

Ясно, что Fx — последовательность натуральных чи­ сел, a Fx. — регулярная последовательность точек М (сходящаяся к X). Поэтому алгорифм F такой, что

F{X) =

iFlxl,

 

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

М в некоторый

элемент

Введем отношение ^ следующим образом

(см. (28)):

(32) PrQ^(PezJ{k)&(Qz=J(k)&(p({P}k,

{ Q } f t ) < 2 - f t + 1 ) .

Нетрудно видеть, что все отношения ^ перечислимы; другими словами, можно построить 'алгорифм % так, что для любых слов Р и Q в Ч0 и любого k

 

№(k,

Р,

 

Q)^P~Q.

 

Пусть

v — алгорифм,

перерабатывающий слова в

алфавите

Ч0 в натуральные числа, причем разные слова

в разные

натуральные

числа. Фиксируем

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

Хо её М и алгорифм g типа

(Ж -> Ж)

такой,

что

(33)

g(n+l)>g(n)

+

3.

 

Введем для краткости следующие обозначения:

(34)при ХбнЛ! через X обозначается F(X);

(35)при любом слове Р в Ч0 через пР обозначается натуральное число g(v(P)) .

416

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

 

МЕТРИЧЕСКИЕ

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

[ГЛ.9

 

Рассмотрим множества Ш\ слов

в ^о,

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

индуктивно следующим

образом ((32), (33) — (35));

(36)

Р е Й 0

=

Р

= 1 0 ,

 

 

 

 

(37)

Р е Жп+{

=

3Q ((Q s

Я„) & (Q ~

Р)).

 

Перечислимость отношений ^ позволяет без особого труда доказать, что все множества 524 перечислимы. Следовательно, перечислимо их объединение, т. е. такое множество Я , что

Обозначим теперь через 2? множество элементов М та­ кое, что для А ' е М

Установим некоторые свойства множества 3?.

 

 

Л е м м а 1. Х0

G E 3.

 

 

 

 

 

 

Для

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

достаточно

заметить, что

Х0 е=

Л е м м а

2.

Ясли

X GE Л1, то X ен .#со

и «А>« л/обол* я

Эта лемма непосредственно усматривается из опре­

делений

алгорифмов

а, 6,

F\ F и

(34).

Из

леммы

2 и

(32) немедленно

вытекает

 

 

 

 

 

Л е м м а

3.

Если

I e M ,

Y <=М

и X =

Y,

то при

лю-

бом п

X-^Y.

i? — согласованное

множество.

 

 

Л е м м а

4.

 

 

Действительно, ввиду перечислимости Я можно по­

строить

алгорифм

81

так,

что

 

 

 

 

! E ' ( P ) s P e £

Построим алгорифм 0 таким образом, что для любого X

8 (X) ~ 0! (X).

Тогда при любом X GE М

 

\в{Х)^Х(=3

и для

окончания доказательства достаточно показать,

что 3

— правильное множество.

§ 3]

ВЫБОР

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

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

417

Пусть

Х е ? .

Тогда

при

некотором

п

X е 5?п-

На

основании

леммы

3 из

Y = X

 

вытекает

тогда

f Е Й В + | ,

 

 

 

 

 

 

 

 

 

т

 

 

 

 

 

 

 

 

 

т. е. У е ^ ,

что

и

требуется.

 

 

 

 

 

 

 

 

 

Л е м м а

5.

Пополнение

множества

2

(в

простран­

стве М)

эффективно

открыто.

 

 

 

 

 

 

 

у

 

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

Рассмотрим

алгорифм

та­

кой, что при любом

1 е М

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

y(X)~g(v(X)).

 

 

 

 

 

 

 

 

Очевидно,

при

X е

М

\у(Х)

и

у(Х)—натуральное

 

чис­

ло.

Покажем,

что

если

Хф2,

 

то

все

точки

шара

Х*у(Х)

не

принадлежат

2 .

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

пусть

F e

e X « v ( X ) . Тогда

((35))

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

р(Х, К ) < 2 - г ^ < Т

) ) =

2 ~ Х

 

 

 

 

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

что

F e S " .

 

Тогда

при

некотором п

 

 

 

 

 

 

 

 

Г

е й

,

 

 

 

 

 

 

 

 

Согласно лемме 2 при любом i

 

 

 

 

 

 

 

 

 

 

 

 

 

p([X}h

 

Х)<2'1-\

 

 

 

 

 

 

 

 

 

 

 

 

p({Y}h

П < 2 " ' " ' .

 

 

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

р № ,

 

 

{Yh)<2~nx+2-1.

 

 

 

 

Полагая

i =

tij,

получим

 

 

 

 

 

 

 

 

 

 

 

 

 

 

P ({*}„_, { 7 } „ _ ) < 2 " ^ + I ,

 

 

 

 

 

т. e.

((32))

 

 

 

 

X~Y.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Отсюда

согласно

(37)

получаем

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Д: е=ЯЯ + 1 > .

 

 

 

 

 

 

 

что,

ввиду X ф 2 ,

 

невозможно.

 

 

 

 

 

 

 

 

О п р е д е л е н и е

4.

1) Точку

X

назовем

 

предель­

ной

точкой

множества М\

точек

М,

если

 

невозможен

шар

с

центром

в

точке

X,

не

содержащий

 

точек

Л\,

14 Б. А. Кушнер

418

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

[ГЛ. 9

2) Множество

Ж\ назовем

замкнутым, если

оно

содер­

жит все

свои

предельные

точки.

 

 

Обращаем внимание читателя на отличие этого опре­

деления

от определений

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

предельной

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

казано ниже, можно опровергнуть на примере.

 

Л е м м а

6.

Множество

2

замкнуто.

 

 

2.

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

 

пусть

 

А' — предельная

точка

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

что X ф 2 .

Тогда по

лемме

5 найдется

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

не содержащий точек 2 .

Это,

однако,

невозможно.

 

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

выполняется

~]~\(Х

е

2),

 

что,

ввиду

 

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

2 ,

дает

1 е

<=2.

 

 

 

Для

каждого

PsS ? можно

построить

це­

Л е м м а

7.

почку

Р0,

 

..,

Ph

попарно

различных

элементов

так,

что Ро~

Х0,

Ph =т= Р и

 

 

 

 

 

 

 

 

 

 

 

Pk

k

Pk-i

„ Т ~ • • • Р\п^

1

 

 

 

 

 

 

 

 

 

rk—\

ri

 

 

 

Действительно, непосредственно из определения мно­ жества 91 ((36) — (37)) усматривается возможность по­ строения цепочки

Остается устранить

в этой

цепочке повторения.

Пусть

i ^ / — наименьшее

число,

при котором Qt =?= Q;.

Тогда

отбрасывая члены цепочки с номерами, большими i, по­

лучим

цепочку, начинающуюся

с

Р = F Qlt

в

которую Р

входит точно один раз. Пусть эта цепочка

имеет

вид

 

Найдем

наименьшее

i^im—

1,

при

котором

Qft~

=?=Qm-\- Выбрасывая

все члены

с номерами

k

та­

кими, что i<kKm—

1 (если

i = m—1,

то

ничего

не

выбрасывается), получим цепочку, содержащую свои последниедва члена точно один раз. Действуя таким образом и дальше, получим требуемую цепочку.

§ 3]

ВЫБОР

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

ПОКРЫТИЯ.

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

419

Выполним теперь некоторую оценку, показывающую,

что множество 9? достаточно

«редко».

 

 

 

 

 

 

Для упрощения изложения нам будет удобно счи­

тать, что алгорифм

v и фиксированный

элемент

Х0 вы­

браны так, что v(^o)=^0.

 

Для любого слова

Р в

алфа­

вите

число v(P) будем

называть номером

этого

сло­

ва.

(Различные слова

имеют

различные

номера.)

 

Л е м м а

8. Пусть Q0,

...,

 

Qlk — список

всех

элемен­

тов 31 с номерами,

не

большими

k.

Тогда

для

 

любого

Х<^2£

при

некотором

 

 

 

 

<=

и

X

принад­

лежит

шару

с центром

в точке {Qi}sik)

радиуса

 

2~8{к)+3

(см. (28)-(29)).

 

 

 

 

 

 

 

 

 

 

 

 

 

Х0.

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

 

Можно

считать, что Q0 =

Пусть

I G S " . Тогда 1 е й . Возможны

случаи:

 

 

 

а) Номер X не больше k. Тогда при некотором

i^lk

X==Qi.

Полагая в лемме 2 n = g(k),

получим

 

 

 

 

 

 

р(Шв <*>, Х ) < 2 - в № , - , < 2 - в № ) + \

 

 

 

что

и требуется.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

б) Номер X больше k.

 

Тогда,

пользуясь

леммой 7,

мы

сможем

найти

Qi(i^lk)

 

 

и элементы

Ри

 

,

Ps

из

31 так, что номера

всех Р, больше k, все слова X, Р ь .. .

 

Ps,

Qi попарно различны и

 

 

 

 

 

 

 

 

 

 

 

X—• р.—,

- — -

 

р

.—• о, *\

 

 

 

 

 

 

 

 

X

r i

 

 

r s - i

 

s

 

 

 

 

 

 

 

Так

как пр

> g(k)

и

Ps

 

 

Qt, то Q{ е= Жп

,

а

следо-

вательно, Qt е Же

 

Применяя

аксиому

треугольника,

получим

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

р ({*>,(*>,

{Qi}g(k)X

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

< р ( W e W, {X)nsr)

 

 

+ Р (ШпГ

 

 

 

+

 

 

 

 

t

+ Р ({Р,Ц,,

{Рх}Яр)

+

Р ({P.}„P i ,

{Р2}Пр)

 

+

 

 

( И )

(I)

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

+

Р ( { ^ 4 e _ i . { ^ } » P

 

)

+ Р ({Я.Цв ,

Ш « Р в )

 

+

 

 

E

 

 

 

 

 

 

 

 

 

 

+

Р ( Ш » Р Я .

 

№ * } * < * > ) .

 

 

*) Разумеется, возможен также случай, когда

написанная

це­

почка состоит лишь из X и Qt.

 

 

 

 

 

 

 

 

 

 

 

 

14*

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