Добавил:

ivanov666 Опубликованный материал нарушает ваши авторские права? Сообщите нам.

Вуз:

Башкирский Государственный Аграрный Университет

Предмет:

[НЕСОРТИРОВАННОЕ]

Файл:

книги из ГПНТБ / Кушнер, Б. А. Лекции по конструктивному математическому анализу

.pdf

Скачиваний:

Добавлен:

22.10.2023

Размер:

14.87 Mб

Скачать

☆

<<< < Предыдущая 7 8 9 10 11 12 13 14 15 16 17 1819 / 4519 20 21 22 23 24 25 26 27 28 29 30 31 > Следующая >>>

182

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

сходимость

[ГЛ. 3

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

что

р1 — регулятор

сходимости

а1

некоторому КДЧ х .

Построим ПНЧ

р2

такую, что

Р2(/г) =

Р(Р'(п)).

Покажем, что р2 является регулятором

сходимости

к х.

а — неубывающая

Пусть,

например,

ПДЧ.

Тогда,

очевидно, а 1 — также

неубывающая ПДЧ. Следователь

но, при любом i

а1 (г) <

х.

Пусть теперь при произвольном п натуральное число i

таково, что i ^

Р 2 (я) . Тогда

а(/)>а(р(р'(п))).

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

а (0 >

а1 (р1 («)).

Поскольку ПНЧ р возрастает, можно найти / такое,

что

Р ( / ) > * .

Тогда мы получим

и так

как

а' (Р'(я)Х а

О'Х «' ( / ) < * ,

(р1 (л)) <

то

х-а'

2~п,

U - a ( i ) r <

2"",

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

Из теоремы 2 и леммы

2 немедленно вытекает

Т е о р е м а

Никакая

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

ПРЧ

<& (построенной

согласно

теореме 1)

не

является

сходя

щейся.

ПДЧ

назовем

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

О п р е д е л е н и е

если

осуществимо

КДЧ

такое,

что при

всех i

\a(i)\^.x

(мы

будем

также

говорить,

что КДЧ

ограничивает

ПДЧ

а).

ПДЧ а такую, что

О п р е д е л е н и е

1)а монотонна,

2)а ограничена,

			ПРИМЕР ШПЕКЕРА			183
3)	а	не является		фундаментальной,
будем	называть		шпекероеюй.
Очевидно, в теоремах 2—3 вместо © может						фигури
ровать любая шпекерова последовательность.
Как будет показано в доказательстве теоремы 4 сле
дующего		пункта,	для	построенной нами	шпекеровой
ПРЧ	© последовательность рациональных				чисел	©(/г +
+ 1) — ©(п ) не			сходится к 0. Вместе с тем нетрудно,
вставляя		между ©(л) и ©(л + 1) «достаточно густо» ра

циональные числа, построить возрастающую шпекерову ПРЧ ©' такую, что

Vtt 3m

VZ (i >

m => (©' (i +

1) -

©' (i)) <

2~n).

Таким

образом,

существуют

как

шпекеровы

ПРЧ,

для которых

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

и шпекеровы

ПРЧ, для которых

это не имеет

места.

В гл. 8 будет приведено некоторое усиление

тео

ремы

1 (впервые

найденное

З а с л а в с к и м

[4]); именно,

будет построена

возрастающая шпекерова

ПРЧ у такая,

что для нее осуществим «понижающий»

алгорифм,

т. е.

алгорифм,

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

всякую

верхнюю

гра

ницу х этой ПРЧ в КДЧ, меньшее х

и также

ограничи

вающее сверху у *)•

Переформулируем полученные результаты в терми

нах рядов.

оо

О п р е д е л е н и е

4. Пусть

2а (0—неотрицатель-

ный

ряд.

Будем

называть

этот ряд

шпекеровым,

если

данный

ряд не сходится;

осуществимо

КДЧ х такое, что при

любом

2 a (i) ^

х.

Из теорем 1—2 немедленно вытекает существование шпекеровых рядов. Кроме того, из сделанного выше за мечания следует, что существуют как шпекеровы ряды

*) Этот результат может быть установлен	и с	помощью	кон
струкции Раиса (см. доказательство теоремы 1),	если	в качестве	Ж
взять креативное множество (ср. Ц е й т и н [10]).

184

КОНСТРУКТИВНАЯ с х о д и м о с т ь

[ГЛ. 3

со сходящимся к 0 общим членом, так и шпекеровы ряды, для которых это не имеет места.

Отметим также, что если у — возрастающая шпекерова ПРЧ и ^ — множество рациональных чисел, пере числяемое алгорифмом y (т. е. множество рациональных чисел «встречающихся в последовательности у»), то мно жество 3? ограничено и вместе с тем невозможно КДЧ, являющееся его точной верхней границей.

Результаты этого пункта устанавливают, таким об разом, существенные теоретические различия традицион ной и развиваемой нами конструктивной теории сходи мости. При принятом нами понятии действительного числа и сходимости не сохраняется теорема Вейерштрасса о сходимости монотонных ограниченных последова тельностей, теорема о выборе сходящейся последова тельности и теорема о существовании точных границ ограниченных множеств*). В следующем пункте мы ко ротко коснемся вопроса о том, как изменится положе ние, если использовать более общее понятие вычисли мого действительного числа — псевдочисла и более об щее понятие сходимости — псевдосходимости.

2.	О п р е д е л е н и е				5.	Будем	говорить, что ПДЧ			а	псевдосхо-
дится	к КДЧ		х,	если
		V« ~1 "1 3mVZ (l >m					=> \| * -		а (/) \| < 2~").
Имеет		место		следующая		теорема		(М а з у р [1]).
Т е о р е м а				4. Можно построить				ПРЧ,	псевдосходящуюся,		но не
сходящуюся		к	нулю.
Д о к а з а т е л ь с т в о .						Пусть	р — арифметически			полный алго
рифм,	перечисляющий				без	повторений			некоторое	неразрешимое

*) Чтобы устранить здесь и в дальнейшем возможные недора зумения, заметим, что с точки зрения традиционного анализа резуль таты этого пункта вовсе не противоречат только что упомянутым классическим теоремам. Результаты эти относятся к системе дей ствительных чисел, отличной от классического континуума, и к дру гому, более узкому, чем обычно, понятию сходимости. Более того, в некотором смысле полученные результаты дополняют рассматри ваемые теоремы традиционного анализа, выявляя их неэффективный характер. Так, например, теорема 1 показывает, что даже алгорифмически заданная монотонная ограниченная последовательность рацио нальных чисел может не допускать эффективной оценки скорости сходимости. Таким образом, потерю общих теорем типа теоремы Вейерштрасса можно в известном смысле считать «платой за эффек тивность».

	ПРИМЕР ШПЕКЕРА				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),
	(9)	»((+l)=FK(a(0) .
		»((+l)=FK(a(0) .
	Ввиду (8) при i< ]
	(Ю)	a(i)<a{j).

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

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

Уя ~1 1

3mVr

(/ >т

=> | a (i)

| < 2 ~ п ) ,

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

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

что

осуществим

регулятор

сходимости

ПРЧ a

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

i, п, если / ^

б(п),

то

a ( t ' ) < 2 _ п

и,

следова

тельно, P(i)

п.

Из

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

дословно так

же,

как в

тео

реме

выводится

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

М.

Таким

образом,

не

схо

дится

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

дальнейшие

теоремы.

Т е о р е м а

Если

монотонная

ПДЧ

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

некото

рому

КДЧ

х, то эта ПДЧ

сходится

к х.

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

усиление

теоремы

не

Т е о р е м а

Для

ПРЧ

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

согласно

теореме 1,

возможно

КДЧ,

которому

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

бы

эта

ПРЧ.

186	КОНСТРУКТИВНАЯ	с х о д и м о с т ь	[ГЛ. 3
	Очевидно, © в теореме 6 может быть заменена любой шлеке-
ровой последовательностью.
	Теорема 6 показывает, что одним ослаблением понятия сходимо
сти	получить теорему, аналогичную	известной теореме	Вейерштрасса,

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

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

Пусть

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

Обозначим

через

q алгорифм

р,

если

q имеет

вид q === SР3

О > и

алгорифм

Id^

(стр.

129),

если

q — ра

циональное

число.

а.2 при

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

ось

любом га

(E«i3.

Еа2 3,

п) ^

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

О п р е д е л е н и е

Будем

говорить,

что

псевдочисло

равно

КДЧ х,

если

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

х.

О п р е д е л е н и е

Будем

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

псевдосхо

дится к

псевдочислу

q, если

Л Д У З З ^ ^

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

нулю.

Т е о р е м а

Всякая

монотонная,

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

ПДЧ

является

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

Из

теорем

6—7

вытекает

Т е о р е м а

Слово

Е©3О» г&е

Ч5 — ПРЧ,

построенная

со

гласно

теореме

является

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

причем

это

псевдочисло

не равно

никакому

КДЧ.

Поскольку,

другой

стороны,

для

каждого

КДЧ,

как

легко

видеть, можно построить равное ему псевдочисло, теорема 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}.
Поскольку Ж эффективно несчетно,		осуществимо
КДЧ	х, принадлежащее Ж и отличное от всех		у'(п).
Это, однако, невозможно.


190	КОНСТРУКТИВНАЯ			с х о д и м о с т ь		[ГЛ. 3
Таким	образом, получаем			следующие теоремы.
Т е о р е м а 2. Каков		бы	ни был		интервал,	множе
ство КДЧ,	принадлежащих		этому интервалу,			неперечис-
лимо и, следовательно,		не	является		областью	примени

мости относительно

алфавита

Ч никакого

алгорифма.

Т е о р е м а

То же, что и

теорема

с заменой

ин

тервала

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

сегмент.

Т е о р е м а

Множество

(всех

КДЧ)

неперечис-

лимо

и,

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

не

является

областью

примени

мости относительно

Ч никакого

алгорифма.

Таким

образом,

невозможен

алгорифм,

применимый

к слову

Р е

Ч тогда

и только

тогда,

когда

является

КДЧ.

Из теорем 2—4 непосредственно получаем

С л е д с т в и е

Каков

бы

ни

был

интервал

(невы

рожденный

сегмент),

множество

КДЧ,

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

этому

интервалу

(сегменту),

не

является

разрешимым.

С л е д с т в и е

Множество

(всех

КДЧ)

не

яв

ляется

разрешимым.

В гл. 4 будет показано, что теорема 3

(а

следова

тельно, и следствие 3) сохраняется и

для

любого

вы

рожденного сегмента.

В заключение заметим, что изложенные

результаты

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

направлении.

Пусть

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

несчетное

множество КДЧ.

Тогда для всякого перечислимого множества КДЧ Ж' можно указать КДЧ, принадлежащее Ж, и отличное (в смысле отношения равенства КДЧ) от всех КДЧ, принадлежащих Ж'. Доказательство этого утверждения вполне аналогично доказательству леммы 1. Таким об разом, в теореме 1 (и в следствиях 1—2) вместо после довательностей КДЧ могли бы фигурировать любые пе речислимые множества КДЧ, т. е. алгорифмы типа (Жт>3)). Соответственно в теоремах 2—4 можно было бы утверждать продуктивность упоминаемых в них мно жеств*). (Отметим, что любой вырожденный сегмент также является продуктивным множеством.)

В п. 5 § 1 гл. 9 результаты этого параграфа будут обобщены на случай метрических пространств.

*) Множество Ж (слов в Ч) называется продуктивным, если для всякого перечислимого подмножества Ж' множества Ж можно указать элемент Ж, не принадлежащий Ж'. (Ср. М а л ь ц е в [1].)

Г Л А В А 4

НЕВОЗМОЖНОСТЬ НЕКОТОРЫХ АЛГОРИФМОВ, СВЯЗАННЫХ С КОНСТРУКТИВНЫМИ ДЕЙСТВИТЕЛЬНЫМИ ЧИСЛАМИ

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

задачи	(результаты этого типа уже приводились в § 4
гл. 3).	Все получаемые здесь теоремы невозможности

устанавливаются путем сведения к данной задаче либо проблемы распознавания применимости, либо проблемы пополнения некоторого алгорифма, для которого эти проблемы заведомо неразрешимы (см. § 2 гл. 1).

Мы будем использовать следующие обозначения. Че рез Ч0 обозначается алфавит {0|}. Буква Р используется для обозначения произвольных слов в этом алфавите. Через § и § мы обозначаем алгорифмы, построенные

согласно теоремам		4 и 6 § 2 гл. 1. Эти	алгорифмы обла
дают следующими		свойствами.
1)	Невозможен	алгорифм 21 над	такой, что при
любом	Р

т(Р)=-]\Ъ(Р)

(таким образом, для $ неразрешима проблема распо знавания применимости относительно Ч0).

2) Алгорифм Ъ принимает два значения 0 и 1 и не пополним относительно Ч0.

§ 1. Некоторые алгорифмические проблемы, связанные с отношениями равенства и порядка на конструктивном континууме.

Приложения к алгебре

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

<<< < Предыдущая 7 8 9 10 11 12 13 14 15 16 17 1819 / 4519 20 21 22 23 24 25 26 27 28 29 30 31 > Следующая >>>

Соседние файлы в папке книги из ГПНТБ

#
29.10.20235.79 Mб13Куцый П.Ф. Повелители молний.pdf
#
25.10.202312.79 Mб19Кучко А.С. Аэрофотография. Основы и метрология.pdf
#
25.10.202318.43 Mб47Кушманов И.В. Электронные приборы учеб. пособие.pdf
#
27.10.202319.55 Mб11Кушнарев Д.М. Использование энергии взрыва в строительстве.pdf
#
19.10.20232.48 Mб24Кушнарев, Ю. М. Авторулевой Печора учебное пособие для студентов судоводительского факультета.pdf
#
22.10.202314.87 Mб19Кушнер, Б. А. Лекции по конструктивному математическому анализу.pdf
#
24.10.202311.94 Mб20Кушнерев Н.Т. Программирование для ЭВМ Минск-32.pdf
#
25.10.202312.78 Mб21Кушнирская М.Ц. Крашение древесины в производстве мебели.pdf
#
27.10.202320 Mб7Кэтермоул К.В. Принципы импульсно-кодовой модуляции.pdf
#
23.10.20234.75 Mб13Лабинский Ю.В. Корабельные ядерные реакторы учеб. пособие.pdf
#
23.10.20238.6 Mб4Лабозин П.Г. Качество крупнопанельного домостроения.pdf