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

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

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

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

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

Добавлен: 15.10.2024

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

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

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

 

ПРИМЕР ШПЕКЕРА

185

множество натуральных

чисел

М.

Искомую

ПРЧ а строим так, что

 

а

(п)

=

2 - р <">.

 

Псевдосходимость а

к

нулю, хотя и

очевидная интуитивно

(Р может разве лишь в конечном числе точек принимать значения, меньшие данного п), оказывается достаточно неудобным объектом для строго конструктивного доказательства. Поступим следующим образом. Предположим, что при некотором п

(5)

~ | Э т У / ( / > т = > | а ( 0 | < 2 - л ) .

 

Тогда

(6)

" 1 3 т У / ( / > т = э Р ( 0 > п ) .

 

При каждом k обозначим через i?& множество натуральных чи­

сел

такое, что

(7)

/ s ^ 4 a ( o * ) 4 ( ( i ( / ) < s ) .

Очевидно, все S'h разрешимы и, следовательно, перечислимы. Ввиду (6) ни одно из этих множеств не может быть пустым. По тео­ реме 8 § 3 гл. 1 можно построить арифметически полный алгорифм Y такой, что при любом k

(8)

Y ( * ) e ^

 

Построим далее алгорифм а так, что

(9)

CT(0)==y(0),

»((+l)=FK(a(0) .

 

Ввиду (8) при i< ]

(Ю)

a(i)<a{j).

Рассмотрим теперь натуральные числа Р(ст(0)), Р(а(1)),...

Р(а(л+1)) . Поскольку все они ((8) —(9)) не превосходят п, среди них есть по меньшей мере два одинаковых, что ввиду (10) не­ возможно. Таким образом, сделанное предположение неверно и мы получаем

 

 

 

Уя ~1 1

 

3mVr

(/ >т

=> | a (i)

| < 2 ~ п ) ,

 

 

 

 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

что

осуществим

регулятор

сходимости

6

ПРЧ a

к 0. Тогда при любых

 

i, п, если / ^

б(п),

то

a ( t ' ) < 2 _ п

и,

следова­

тельно, P(i)

>

п.

Из

этой оценки почти

дословно так

же,

как в

тео­

реме

1,

выводится

разрешимость

М.

Таким

образом,

а

не

схо­

дится

к

0.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приведем, предоставляя доказательства читателю, некоторые

дальнейшие

теоремы.

 

 

 

 

 

 

 

 

 

 

 

 

 

Т е о р е м а

5.

Если

монотонная

ПДЧ

псевдосходится

к

некото­

рому

КДЧ

х, то эта ПДЧ

сходится

к х.

 

 

 

 

 

 

 

 

Из теоремы 5 вытекает следующее

усиление

теоремы

2.

 

не­

Т е о р е м а

6.

Для

ПРЧ

©, построенной

согласно

теореме 1,

возможно

КДЧ,

к

которому

псевдосходилась

 

бы

эта

ПРЧ.

 

 

186

КОНСТРУКТИВНАЯ

с х о д и м о с т ь

[ГЛ. 3

 

Очевидно, © в теореме 6 может быть заменена любой шлеке-

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

 

 

 

Теорема 6 показывает, что одним ослаблением понятия сходимо­

сти

получить теорему, аналогичную

известной теореме

Вейерштрасса,

не удается. Некоторый аналог этой теоремы получается, если допу­ стить в качестве пределов последовательностей КДЧ псевдочисла.

Приведем необходимые определения.

 

 

 

 

 

 

 

 

 

Пусть

q — псевдочисло.

Обозначим

через

q алгорифм

р,

если

q имеет

вид q === SР3

О > и

алгорифм

 

Id^

(стр.

129),

если

q — ра­

циональное

число.

 

 

 

 

 

 

 

 

 

 

 

 

а.2 при

Построим алгорифм SB такой, что для любых П Д Ч

ось

любом га

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

S

(E«i3.

Еа2 3,

п) ^

 

а, (га) — а2 (га).

 

 

 

 

О п р е д е л е н и е

6.

Будем

говорить,

что

псевдочисло

 

q

равно

КДЧ х,

если

ПРЧ q псевдосходится

к

х.

 

 

 

 

 

 

 

О п р е д е л е н и е

7.

Будем

говорить, что ПДЧ

а

псевдосхо­

дится к

псевдочислу

 

q, если

Л Д У З З ^ ^

^псевдосходится

 

к

нулю.

Т е о р е м а

7.

Всякая

монотонная,

ограниченная

 

ПДЧ

 

является

псевдофундаментальной.

 

 

 

 

 

 

 

 

 

 

 

 

 

Из

теорем

6—7

вытекает

 

 

 

 

 

 

 

 

 

 

Т е о р е м а

8.

Слово

Е©3О» г&е

Ч5 — ПРЧ,

построенная

со­

гласно

теореме

1,

является

псевдочислом,

причем

это

псевдочисло

не равно

никакому

КДЧ.

 

 

 

 

 

 

 

 

 

 

 

 

Поскольку,

с

другой

стороны,

для

каждого

КДЧ,

как

легко

видеть, можно построить равное ему псевдочисло, теорема 8 пока­ зывает, что псевдочисел в некотором смысле «больше», чем кон­ структивных действительных чисел.

Т е о р е м а

9.

Для

всякой

псевдофундаментальной

последова­

тельности

КДЧ

можно

построить

псевдочисло,

к которому

псевдо­

сходится

эта

КДЧ.

 

 

 

 

 

 

Из теорем 7 и 9 вытекает следующий аналог теоремы Вейер­

штрасса.

 

 

Для

каждой

монотонной

ограниченной

ПДЧ

Т е о р е м а

10.

можно построить псевдочисло,

к которому псевдосходится эта ПДЧ.

Таким образом, использование псевдосходимости и псевдочисел позволяет в какой-то степени сохранить привычную картину тради­ ционной теории пределов, но очевидная громоздкость и удаленность этих понятий от интуитивной «вычислимости» сводит это преимуще­ ство на нет * ) .

*) В последнее время выявилась возможность плодотворного использования такого рода концепций для установления конструк­

тивных

вариантов

теорем

типа

теоремы

Бореля

о

покрытиях (см.

Л и ф ш и ц [4]). Читатель,

например, без

труда

докажет

следующее

утверждение.

Пусть

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

рациональных

интер­

валов

такая,

что

невозможно

псевдочисло из

единичного

сегмента,

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

ни

одному

из интервалов

Ф(га).

Тогда

можно

§ 4] НЕПЕРЕЧИСЛИМОСТЬ КОНСТРУКТИВНОГО КОНТИНУУМА

Jg7

§ 4. Эффективная несчетность конструктивного

 

континуума

 

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

ности классического

континуума.

 

 

 

О п р е д е л е н и е

1. Множество

КДЧ

Ж назовем

эф­

фективно

несчетным,

если

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

91,

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

запись

всякой

ПДЧ

а в КДЧ таким

образом,

что

 

 

 

 

 

1)

 

И(ЕаЗ)е=лГ;

 

 

2)

 

Чп(%(£аЪ)фа(п)).

 

 

 

 

 

з>

 

 

 

Скаждым промежутком естественно связывается

множество КДЧ, принадлежащих этому промежутку. В дальнейшем, там, где это не может привести к недо­ разумениям, мы будем использовать следующий сокра­ щенный оборот речи: вместо того чтобы говорить о мно­ жестве КДЧ, принадлежащих данному промежутку, бу­ дем говорить о самом этом промежутке.

Основным результатом этого параграфа является теорема об эффективной несчетности любого интервала или, говоря точнее, следующая

Т е о р е м а

1. Можно

построить алгорифм Z такой,

что для любого

интервала xV

у и ПДЧ а

1)

! £ (* V 0 ,

£«3) и t

(xv

У,

£а!)-КДЧ;

2)

1(х\7

У,

£ a 3 > e * v # " ,

 

 

3)

при любом п

 

 

 

 

 

 

Z(x v

У, с"а3) ^

<*(")•

 

 

 

 

 

з>

 

найти

k так,

что

уже интервалы

Ф(0),

Ф(&) покрывают еди­

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

188

КОНСТРУКТИВНАЯ

с х о д и м о с т ь

 

ГГЛ. 3

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

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

Ж1

такой,

что для любых КД Ч х,

у, z

 

 

 

 

%2{хАу,

z ) ~

 

 

 

 

 

 

 

j хАх

+ ±=-*-,

если Р з ( х +

- Ч ^ > У " S T "

' 2 ) =

2 '

| у — -^—^ Ау,

если Рз (х +

, у —

,

2 ) =

I.

Пусть

х < у. Тогда при любом z

 

 

 

и Рз перерабатывает

слово

 

 

 

 

 

 

.

ц — х

 

у — х

 

 

 

в 2 или в 1. В первом

случае

 

 

 

 

z>х +

Во втором

у 3

.

Таким образом, алгорифм 2I1 перерабатывает всякое слово х Ay, z, где х < г/, в сегмент длины У 3 * ,

входящий в х Л у и такой, что 2 не принадлежит этому сегменту.

Построим алгорифм 3I2 такой, что для любого интер­ вала х V у, любой ПДЧ а и любого п

%2(х^у,^,0)^%'(хАу,а(0)),

 

 

W(xx/y,

£al,n+\)~%l(W(x\7y,

£<хЗ, п), а (л + 1)).

Индукцией по л без труда доказывается, что для лю­

бого интервала х V у

и любой ПДЧ а

 

а) ЭДхугл №

е с т ь

вложенная последовательность сег­

ментов;

 

 

 

 

 

б) длина сегмента %2 (ху у, £аЗ, л) равна

Ъ~п~х-(у—х);

в) КДЧ а (л) не

принадлежит

сегменту

2 l 2 ( x V У>

л).

 

 

 

 

 

Кроме

того,

очевидно,

 

 

г) W{xyy,

£св,

0 ) д х Д ( / .

 

 

§ 4] НЕПЕРЕЧИСЛИМОСТЬ КОНСТРУКТИВНОГО

КОНТИНУУМА

189

Воспользовавшись леммой 1 § 5

гл. 2, можно

по­

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

у> перерабатывающий

всякий интер­

вал х V у в интервал длины, меньшей

1,

концы которого

принадлежат х V у.

 

 

 

Построим алгорифм 213 такой, что

 

 

 

W(xvy,

£a3,n)~W(y(xVy),

 

Ы.п).

 

Из пп. а) — г) получаем, что для любого интервала

хV у, ПДЧ а и любого п

а) — б ) %lvy, есть вложенная регулярная после­ довательность сегментов;

в ) КДЧ а(п) не принадлежит сегменту u x v y , Еаз («);

г ) сегмент

u x v y ,

£аз (0) включен

в интервал

 

х V У-

Искомый

алгорифм

£

строим,

пользуясь

теоремой

о вложенных

сегментах

(§ 2) так, чтобы

 

 

 

 

Z(xvy,

 

£ a 3 ) ^ H m ( 2 ) ( ^ v y ,

£ e 3 3 ) .

 

 

Алгорифм £ обладает требуемыми свойствами.

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

если

х V у — интервал,

то

 

по тео­

реме 2 § 2 lim(2> переработает

слово

£$L3xvy,

Е«зЗ в КДЧ,

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

всем

сегментам

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

Wive, Ш'

Из пп. в') и г')

вытекает

тогда, что это КДЧ

принадлежит

интервалу

xVу

и отлично от всех

а(п).

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

из

доказанной

теоремы

вытекают

следующие

предложения.

 

 

 

 

 

 

 

С л е д с т в и е

1. Множество 2)

(всех

КДЧ)

 

эффек­

тивно несчетно.

2. Всякий

невырожденный

сегмент эф­

С л е д с т в и е

фективно

несчетен.

 

 

 

 

 

 

 

 

 

Почти очевидна

следующая

 

 

 

 

 

 

Л е м м а

1. Всякое эффективно несчетное

множество

КДЧ не является

 

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

 

 

 

 

 

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

Пусть

Ж— эффективно

несчет­

ное множество КДЧ и алгорифм у перечисляет Ж. По

лемме

1 § 3 гл. 1 построим арифметически

полный

алго­

рифм

Y'> перечисляющий множество Ж' такое, что

 

 

Л <= Ж' £= Ж U {0}.

 

 

Поскольку Ж эффективно несчетно,

осуществимо

КДЧ

х, принадлежащее Ж и отличное от всех

у'(п).

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

 

 

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